<div id="readability-page-1" class="page"><div>
                                    <p><a href="/m/category/JAVA"><span>JAVA</span></a></p><h3>LinkedList와 ArrayList의 remove 연산</h3>
                                </div><p><cite>Berno</cite>
                                    <span> 2023. 6. 21. 16:48</span>
                                </p><div>
                                <h3 data-ke-size="size23"><span><b>0. 이 글을 쓰는 이유</b></span></h3>
<p data-ke-size="size16"><span>remove, add 등의 연산 속도가 LinkedList와 ArrayList의 구조에 따라 차이가 있는 것은 data structure를 공부하다보면 자연스레 알게된다. 그럼 java코드로는 어떻게 구현이 되어있을지 많이 깊게는 보지 않지만 그래도 좀 보면서 정리하기 위해 작성함</span></p>


<h3 data-ke-size="size23"><span><b>1. ArrayList의 remove</b></span></h3>
<pre id="code_1687332511595" data-ke-language="java" data-ke-type="codeblock"><code>    /**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *
     * @param index the index of the element to be removed
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
        Objects.checkIndex(index, size);
        final Object[] es = elementData;

        @SuppressWarnings("unchecked") E oldValue = (E) es[index];
        fastRemove(es, index);

        return oldValue;
    }
    
        public boolean remove(Object o) {
        final Object[] es = elementData;
        final int size = this.size;
        int i = 0;
        found: {
            if (o == null) {
                for (; i &lt; size; i++)
                    if (es[i] == null)
                        break found;
            } else {
                for (; i &lt; size; i++)
                    if (o.equals(es[i]))
                        break found;
            }
            return false;
        }
        fastRemove(es, i);
        return true;
    }
    
        /**
     * Private remove method that skips bounds checking and does not
     * return the value removed.
     */
    private void fastRemove(Object[] es, int i) {
        modCount++;
        final int newSize;
        if ((newSize = size - 1) &gt; i)
            System.arraycopy(es, i + 1, es, i, newSize - i);
        es[size = newSize] = null;
    }</code></pre>
<p data-ke-size="size16"><span>ArrayList에는 2개의 remove함수가 오버로딩 되어있다.&nbsp;</span></p>
<p data-ke-size="size16"><span>하나는 제거가 되었는지 여부(해당 오브젝트가 존재하는지 판단)를 반환해 주는 함수와 제거된 아이템을 반환해 주는 함수가 있다.</span></p>

<p data-ke-size="size16"><span>재미있는 건 boolan remove(Object o) 함수다.</span></p>
<p data-ke-size="size16"><span>일반적인 Object는 equals함수로 비교하는데</span></p>
<p data-ke-size="size16"><span>null값이 들어온 경우 정말로 null값마저도 존재하는지 찾는 것을 볼 수 있다.</span></p>
<pre id="code_1687332844294" data-ke-language="java" data-ke-type="codeblock"><code> found: {
            if (o == null) {
                for (; i &lt; size; i++)
                    if (es[i] == null)
                        break found;
            } else {
                for (; i &lt; size; i++)
                    if (o.equals(es[i]))
                        break found;
            }
            return false;
        }</code></pre>
<p data-ke-size="size16"><span>이후 fastRemove함수에서는 remove가 진행됨에 따라 기존 size가 이번에 제거되는 인덱스보다 큰 경우 새로운 Array를 deep copy 하면서&nbsp;진행한다.</span></p>
<pre id="code_1687332994285" data-ke-language="java" data-ke-type="codeblock"><code>       final int newSize;
        if ((newSize = size - 1) &gt; i)
            System.arraycopy(es, i + 1, es, i, newSize - i);
        es[size = newSize] = null;</code></pre>
<p data-ke-size="size16"><span>이후 공통적인 작업으로는 마지막 사이즈의 인덱스 부분을 null로 초기화한다.(array의 사이즈가 5인 경우 마지막 index는 4지만 5번째 index를 null로 초기화한다.)</span></p>


<h3 data-ke-size="size23"><span><b>2. LinkedList의 remove</b></span></h3>
<p data-ke-size="size16"><span>LinkedList에도 2개의 remove함수가 존재한다.</span></p>

<pre id="code_1687333252850" data-ke-language="java" data-ke-type="codeblock"><code>    /**
     * Removes the first occurrence of the specified element from this list,
     * if it is present.  If this list does not contain the element, it is
     * unchanged.  More formally, removes the element with the lowest index
     * {@code i} such that
     * {@code Objects.equals(o, get(i))}
     * (if such an element exists).  Returns {@code true} if this list
     * contained the specified element (or equivalently, if this list
     * changed as a result of the call).
     *
     * @param o element to be removed from this list, if present
     * @return {@code true} if this list contained the specified element
     */
    public boolean remove(Object o) {
        if (o == null) {
            for (Node&lt;E&gt; x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node&lt;E&gt; x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
    
    public E remove() {
        return removeFirst();
    }
    
     /**
     * Unlinks non-null node x.
     */
    E unlink(Node&lt;E&gt; x) {
        // assert x != null;
        final E element = x.item;
        final Node&lt;E&gt; next = x.next;
        final Node&lt;E&gt; prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }</code></pre>
<p data-ke-size="size16"><span>아마 가장 큰 차이는 unlink에서 발생하지 않을까 싶다.</span></p>

<h3 data-ke-size="size23"><span><b>3. 결론</b></span></h3>
<p data-ke-size="size16"><span>LinkedList와 <span>&nbsp;ArrayList 둘 다</span> 제거대상이 되는 Object를 찾기 위해 O(n)만큼 순회를 진행하는 점은 동일하다. 다만 LinkedList는 찾은 이후에 unlink를 통해 해당 Object를 null로 초기화하고 앞 뒤의 연결을 다시 맺어준다. 즉 deep copy의 시간이 줄어든다는 것이다.</span></p>


            
            
                </div></div>

흔한 컴공출신 개발자

bernoyoun

0. 이 글을 쓰는 이유
remove, add 등의 연산 속도가 LinkedList와 ArrayList의 구조에 따라 차이가 있는 것은 data structure를 공부하다보면 자연스레 알게된다. 그럼 java코드로는 어떻게 구현이 되어있을지 많이 깊게는 보지 않지만 그래도 좀 보면서 정리하기 위해 작성함
 
 
1. ArrayList의 remove
    /**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *
     * @param index the index of the element to be removed
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
        Objects.checkIndex(index, size);
        final Object[] es = elementData;
        @SuppressWarnings("unchecked") E oldValue = (E) es[index];
        fastRemove(es, index);
        return oldValue;
    }
    
        public boolean remove(Object o) {
        final Object[] es = elementData;
        final int size = this.size;
        int i = 0;
        found: {
            if (o == null) {
                for (; i < size; i++)
                    if (es[i] == null)
                        break found;
            } else {
                for (; i < size; i++)
                    if (o.equals(es[i]))
                        break found;
            }
            return false;
        }
        fastRemove(es, i);
        return true;
    }
    
        /**
     * Private remove method that skips bounds checking and does not
     * return the value removed.
     */
    private void fastRemove(Object[] es, int i) {
        modCount++;
        final int newSize;
        if ((newSize = size - 1) > i)
            System.arraycopy(es, i + 1, es, i, newSize - i);
        es[size = newSize] = null;
    }
ArrayList에는 2개의 remove함수가 오버로딩 되어있다. 
하나는 제거가 되었는지 여부(해당 오브젝트가 존재하는지 판단)를 반환해 주는 함수와 제거된 아이템을 반환해 주는 함수가 있다.
 
재미있는 건 boolan remove(Object o) 함수다.
일반적인 Object는 equals함수로 비교하는데
null값이 들어온 경우 정말로 null값마저도 존재하는지 찾는 것을 볼 수 있다.
 found: {
            if (o == null) {
                for (; i < size; i++)
                    if (es[i] == null)
                        break found;
            } else {
                for (; i < size; i++)
                    if (o.equals(es[i]))
                        break found;
            }
            return false;
        }
이후 fastRemove함수에서는 remove가 진행됨에 따라 기존 size가 이번에 제거되는 인덱스보다 큰 경우 새로운 Array를 deep copy 하면서 진행한다.
       final int newSize;
        if ((newSize = size - 1) > i)
            System.arraycopy(es, i + 1, es, i, newSize - i);
        es[size = newSize] = null;
이후 공통적인 작업으로는 마지막 사이즈의 인덱스 부분을 null로 초기화한다.(array의 사이즈가 5인 경우 마지막 index는 4지만 5번째 index를 null로 초기화한다.)
 
 
2. LinkedList의 remove
LinkedList에도 2개의 remove함수가 존재한다.
 
    /**
     * Removes the first occurrence of the specified element from this list,
     * if it is present.  If this list does not contain the element, it is
     * unchanged.  More formally, removes the element with the lowest index
     * {@code i} such that
     * {@code Objects.equals(o, get(i))}
     * (if such an element exists).  Returns {@code true} if this list
     * contained the specified element (or equivalently, if this list
     * changed as a result of the call).
     *
     * @param o element to be removed from this list, if present
     * @return {@code true} if this list contained the specified element
     */
    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
    
    public E remove() {
        return removeFirst();
    }
    
     /**
     * Unlinks non-null node x.
     */
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        x.item = null;
        size--;
        modCount++;
        return element;
    }
아마 가장 큰 차이는 unlink에서 발생하지 않을까 싶다.
 
3. 결론
LinkedList와  ArrayList 둘 다 제거대상이 되는 Object를 찾기 위해 O(n)만큼 순회를 진행하는 점은 동일하다. 다만 LinkedList는 찾은 이후에 unlink를 통해 해당 Object를 null로 초기화하고 앞 뒤의 연결을 다시 맺어준다. 즉 deep copy의 시간이 줄어든다는 것이다.

LinkedList와 ArrayList의 remove 연산

댓글