LinkedList와 ArrayList의 remove 연산

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의 시간이 줄어든다는 것이다.