[오늘의 문제] List

LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);

// 1. for

for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

// 2. for-each
for (Integer value : list) {
    System.out.println(value);
}

위 코드에서 더 빠른 성능을 보여주는 코드는 무엇인가요?

ArrayList

ArrayList는 이름 그대로 배열을 사용해서 데이터를 관리합니다.

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

    private static final int DEFAULT_CAPACITY = 10;

private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

}

기본 용량은 10이고, 기존 용량보다 초과해서 데이터를 추가(삭제) 시, 배열의 크기를 약 1.5배 증가시키는 특징이 있습니다.

ArraysSupport.newLength(oldLength, minGrowth, prefGrowth)

여기서

• oldLength: 현재 배열의 길이 (oldCapacity)
• minGrowth: 최소한으로 증가해야 할 길이. 즉, minCapacity - oldCapacity 입니다. minCapacity는 현재 작업(예: 요소 추가)을 위해 필요한 최소한의 용량입니다.
• prefGrowth: 선호하는 증가 길이. oldCapacity >> 1 입니다.

: 이 연산자는 시프트 연산자로 A >> B A에 대해 오른쪽으로 B만큼 비트이동하라는 의미이고,

oldCapacity / 2 와 같은 역할을 합니다.

원리는 다음과 같습니다.

• 10진수 10을 이진수로 표현하면 1010 (2진수)입니다.
• 1010을 오른쪽으로 1비트 시프트하면 0101 이 됩니다.

int newLength(int oldLength, int minGrowth, int prefGrowth) {
    // 선호하는 성장률을 먼저 계산
    int newCapacity = oldLength + prefGrowth; // oldCapacity + (oldCapacity / 2) = oldCapacity * 1.5

    // 하지만 최소한 필요한 용량(minGrowth)도 충족해야 함
    if (newCapacity < oldLength + minGrowth) { // 새 용량이 최소 성장치보다 작으면
        newCapacity = oldLength + minGrowth; // 최소 성장치만큼 늘림
    }

    // 최대 배열 크기 제한 등을 처리하는 로직 (ArrayList의 경우 Integer.MAX_VALUE - 8 등)
    // ...

    return newCapacity;
}

내부 원리는 다소 복잡해서 간소화 시키면

oldCapacity + (oldCapacity / 2) = oldCapacity * 1.5 이런 느낌이라 여기까지 알아보고 넘어가겠습니다.

배열의 특징 때문에 중간에 데이터를 삽입하게 되면 그 뒤에 있는 요소들에 대해 한칸씩 옮겨야하므로 성능이 떨어질 것 같지만 시스템 레벨에서 메모리 고속 복사 연산을 사용하여 한번에 옮겨서 나름 최적화 합니다.

LinkedList

노드라는 개념으로 데이터를 관리합니다.

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     */
    transient Node<E> last; 
}

첫번째 노드와 마지막 노드를 참조하고 있는 모습입니다.

void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

메서드 하나를 참고해보면 이전 노드와 다음노드를 참조해서 이동할 수 있는 이중연결리스트 구조임을 알 수 있습니다.

Iterable

public interface Iterable<T> {
    Iterator<T> iterator(); 
}

어떤 자료구조든 동일한 방법으로 순회할 수 있게 도와주는 인터페이스다.

해당 인터페이스를 상속받는 클래스는 순회가 가능하다고 알려주는 역할입니다. (반복가능한 친구라는 뜻)

Iterator

public interface Iterator<E> {
    boolean hasNext();
    E next();
 }

실제 순회는 Iterator가 담당합니다.

Iterator 객체에게 hasNext()를 물어보고 next()를 요청하는 방식으로 컬렉션의 내부를 순회합니다.

for-each

for(Integer i : list) {
    ...
}

while(iterator.hasNext()) {
    Integer value = iterator.next();
    ...
}

for-each 문, 향상된 for문을 Iterable 인터페이스를 구현한 객체에 사용하면,

컴파일러가 위와같이 변경해줍니다. (일반 배열은 fori문으로 변경)

이제 다시 문제로 돌아가봅시다.

LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);

// 1. for

for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

// 2. for-each
for (Integer value : list) {
    System.out.println(value);
}

배열은 메모리가 연속적으로 위치해 있어 단 한번의 연산을 통해서 접근가능한데에 반해,

LinkedList는 현재 노드(참조)로 부터 순차적으로 접근해야해서 O(1) +… = O(n) 시간이 걸립니다.

반면에 향상된 for문을 사용하면 Iterator.hasNext(), Iterable.next() 을 사용하게 되는데,

현재참조를 가지고 있는 Node의 값만 읽어오면 되므로 O(1) 시간이 걸립니다.

이제 LinkedList가 Iterator를 어떻게 구현했는지 살펴보고 마무리하겠습니다.

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{

일단은 LinkedList 클래스에서는 iterator() 메서드가 구현된게 없더라구요. 그래서 상속해준 클래스에서 찾게 되었습니다.

public abstract class AbstractSequentialList<E> extends AbstractList<E> {
    public Iterator<E> iterator() {
        return listIterator();
    }
}

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    public ListIterator<E> listIterator() {
        return listIterator(0);
    }

  public ListIterator<E> listIterator(final int index) {
        rangeCheckForAdd(index);

        return new ListItr(index);
    }
}

listIteraotr()라는걸 반환하고

쭉 따라가다보면 ListItr(0)를 호출하는걸 알 수 있습니다.

public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }

    private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;

        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }

        public boolean hasNext() {
            return nextIndex < size;
        }

        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }

LinkedList 내부 클래스에 ListItr 존재합니다. hasNext, next 메서드를 존재했고 Node로 움직이는걸 확인할 수 있습니다.