ArrayList VS LinkedList -addOn(1)

학습목표

• ArrayList의 시간복잡도
• LinkedList의 시간복잡도

ArrayList의 구현방식과 그에따른 시간복잡도

ArrayList는 내부적으로 배열을 이용해 List를 구현하므로 배열의 특징을 그대로 지니고 있다.

이점을 명심하고 생각해보자!

데이터 조회

ArrayList클래스의 데이터 조회 코드를 살펴보자. 인덱스를 알고있다는 가정하에...

 public E get(int index) {
        Objects.checkIndex(index, size);
        return elementData(index);
    }

데이터 추가

단순 add()는 생략하도록 한다. 배열에 원소를 추가하는 작업일 뿐으로, O(1)이다.

 public void add(int index, E element) {
        rangeCheckForAdd(index);
        modCount++;
        final int s;
        Object[] elementData;
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);
        elementData[index] = element;
        size = s + 1;
    }

데이터 삭제

삭제는 데이터 추가와 마찬가지다. 한칸씩 앞으로 당겨주면 되므로, 역시 O(N)의 시간복잡도를 보여준다.

LinkedList

LinkedList는 ArrayList와 다르게 구현되어있다. LinkedList를 이루는 원소들을 '노드'라 표기하는데, 이 노드들은 노드자체의 값과, 자기자신 다음순서의 노드 주소값을 가지고 있다. 그러므로 데이터 조회를 할때는 가장 맨처음 노드부터 순차적으로 접근할 수 밖에 없다. 자연스럽게 시간복잡도는 O(N)이 나오겠다. ArrayList와 마찬가지로 코드를 보며 이해해보자.

데이터 조회

public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

데이터 추가

마지막이나 처음에 데이터를 추가하는 코드는 생략한다. LinkedList는 head와 tail로 선언한 변수에 처음노드와 마지막 노드를 저장해두고 있다. 그러므로 인덱스를 모를지라도, 바로 접근이 가능하다.

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

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++;
    }

Node<E> node(int index) {
        // assert isElementIndex(index);
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

데이터 삭제

삭제는 추가와 마찬가지로 O(1)이다.

알게된 점

• ArrayList의 시간복잡도
• LinkedList의 시간복잡도
• ArrayList와 LinkedList의 시간복잡도 표기는 다르지만, LinkedList도 추가/삭제를 위해서는 특정 위치의 노드를 찾아가야하기 때문에, 실제로는 O(N)이 더 추가적으로 소요된다.

Reference

TIL #4 // Time Complexity