Java.util.List Interface(2) LinkedList

저번에 확인했던 ArrayList이후로 LinkedList를 확인하려 합니다.

 

이번에도 ArrayList와 동일하게 GET, ADD, REMOVE 연산에 대해 확인해보려 합니다.

 

 

1. GET

public E get(int index) {
    this.checkElementIndex(index);
    return this.node(index).item;
}

private void checkElementIndex(int index) {
    if (!this.isElementIndex(index)) {
        throw new IndexOutOfBoundsException(this.outOfBoundsMsg(index));
    }
}

// checkElementIndex함수에서 호출
private boolean isElementIndex(int index) {
    return index >= 0 && index < this.size;
}

LinkedList.Node<E> node(int index) {
     LinkedList.Node x;
     int i;
     if (index < this.size >> 1) {
         x = this.first;

         for(i = 0; i < index; ++i) {
             x = x.next;
         }

         return x;
     } else {
         x = this.last;

         for(i = this.size - 1; i > index; --i) {
             x = x.prev;
         }

         return x;
     }
}

//결과 리턴

순서를 살펴보면 GET을 진행할 때, 먼저 index가 해당 list의 사이즈 안에 포함되는지를 먼저 확인합니다.

그 다음 this.node(index) 로직을 통해서 해당 Node를 가져오게 됩니다.

여기서 한가지 차이점이 있다면. Array와는 다르게 get연산이 list전체를 순회하다가 해당 인덱스에 맞는 값을 리턴해주게 됩니다.

 

그나마 if ,else문을 통해서 index가 시작점, 끝점과의 길이를 비료하여 어느 점이 더 가까운지 확인후 list를 순회하므로 최악의 경우 절반정도의 list순회가 필요합니다.

 

 

 

2. ADD

add연산은 ArrayList보다 훨씬 간단하다.

public boolean add(E e) {
    this.linkLast(e);
    return true;
}

void linkLast(E e) {
    LinkedList.Node<E> l = this.last;
    LinkedList.Node<E> newNode = new LinkedList.Node(l, e, (LinkedList.Node)null);
    this.last = newNode;
    if (l == null) {
        this.first = newNode;
    } else {
        l.next = newNode;
    }

    ++this.size;
    ++this.modCount;
}

newNode를 통해서 node를 생성해주고, last값이 null이냐 아니냐에 따라 fisrt갱신, 그리고 this.last = newNode;를 통해 마지막 node를 갱신한다. 즉 ArrayList만큼 copy하는 작업이 없기에 add연산의 경우 훨씬 가볍게 동작하게 됩니다.

 

 

3. remove

public boolean remove(Object o) {
    LinkedList.Node x;
    if (o == null) {
        for(x = this.first; x != null; x = x.next) {
            if (x.item == null) {
                this.unlink(x);
                return true;
            }
        }
    } else {
        for(x = this.first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                this.unlink(x);
                return true;
            }
        }
    }

    return false;
}

제거하려는 부분은 또한 간단하게 처리됩니다. null일 경우엔 별도의 로직을 태우는것 외에는 list의 index를 돌면서 해당부분을 unlink ( double linkedlist 의 특징 활용) 하여 list에서 제거해줍니다.

 

 

빅오를 한번 정리해보면 다음과 같습니다.

GET	O(n/2)
INSERT	O(1)
REMOVE	O(n)

 

다음 포스팅에서 stack을 정리하고 list를 마무리하려합니다.