[JAVA] Queue 인터페이스 구현하기 (2) LinkedList

Queue라는 인터페이스를 구현하는 방식 중 LinkedList에 대해서 알아본다.

 

LinkedList

LinkedList는 내부적으로 다음의 변수를 사용한다. 이 변수들은 transient를 사용해서 직렬화되지 않는다.

int size	크기
Node<E> first	첫번째 노드를 가리킨다.
Node<E> last	마지막 노드를 가리킨다.

modCount는 LinkedList가 상속받은 AbstractSequentialList 내부적으로 쓰이는 변수다. 객체의 구조적 변경 횟수를 추적하기 위해 사용된다.

 

Node

LinkedList에서 사용하는 Node 클래스다.

한 노드에는 아이템과 이전 노드 주소, 다음 노드 주소를 저장한다.

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

 

add

큐에서 사용하는 메서드라 노드 마지막에 추가한다.

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

 

이전 노드는 l(=last), 현재 요소는 e, 다음 요소는 null인 새로운 노드를 만들어서 last에 저장한다.

만약 l이 null이라면 아직 어떤 노드도 큐에 없다는 것이므로 first에 newNode를 저장한다.

l != null이라면 마지막(이었던) 노드의 다음 노드가 생긴 것이므로 l.next에 newNode를 저장한다.

요소가 하나 추가됐으므로 size를 1 늘리고, modCount도 1 늘린다.

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

 

offer

offer메서드는 내부적으로 add메서드를 호출하고 그 결과를 반환한다. 

하지만 add메서드는 요소를 추가한 뒤 항상 true를 반환한다. 따라서 offer메서드는 add메서드의 반환값을 무시하고 대신 항상 true를 반환하게 된다.

원래 Queue 인터페이스 규칙에서 offer은 큐에 요소를 추가할 수 없을 경우 false를 반환하게 되어있다. 하지만 LinkedList는 요소를 추가할 수 없는 제한이 없기 때문에 항상 true를 반환하도록 구현되었다.

public boolean offer(E e) {
    return add(e);
}

 

remove

맨 앞 요소를 삭제하고 반환한다.

public E remove() {
    return removeFirst();
}

 

현재 first노드를 f에 저장한 뒤, first노드가 없다면(=큐에 어떤 요소도 없다면) NoSuchElementException을 발생시킨다.

그 밖의 경우 unlinkFirst(f)를 호출하고 그 값을 반환한다.

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

 

null이 아닌 첫번째 요소를 연결해제한다.

 

첫번째 요소의 element와 next를 저장해둔다.

그 후 f.item, f.next에 null값을 저장한다. 가비지 컬렉션에 도움을 주기 위함이다. 가비지 컬렉션은 더 이상 참조되지 않는 객체를 메모리에서 해제하는 프로세스다. 이 첫번째 요소는 더이상 사용되지 않으므로 메모리에서 해제될 수 있도록 null값을 저장하는 것이다.

 

first를 next로 교체한다.

만약 next가 null이라면 빈 큐가 되는 것이므로 last에도 null을 저장한다.

이 외의 경우는 next(=이제 first)의 이전 값에 null을 저장한다.

 

사이즈를 하나 줄이고, modCount를 +1한다.

마지막으로 미리 저장해둔 element를 반환한다.

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

 

poll

f에 first를 저장해두고, f가 null이라면 NoSuchElementException가 발생되지 않도록 바로 null을 반환한다.

f가 null이 아닌 경우 unlinkFirst를 호출하고 그 값을 반환한다.

public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

 

element

첫번째 요소를 반환한다.

public E element() {
    return getFirst();
}

 

f에 first를 저장하고, f가 null이라면 NoSuchElementException을 발생시킨다.

그 외의 경우는 f.item을 반환한다.

public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

 

peek

f에 first를 저장해두고, 

f가 null이라면 NullPointException이 발생되지 않도록 바로 null을 반환한다.

f가 null이 아니라면 f.item을 반환한다.

public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}