[Java] LinkedList 구현

출처

ChatGPT

자바 1.8 소스 코드

---

자바의 LinkedList 클래스는 List, Deque, Queue 인터페이스를 구현하는 이중 연결 리스트(doubly linked list) 자료구조이다. 이중 연결 리스트는 각 노드가 두 개의 참조를 가지며, 하나는 이전 노드를 가리키고, 다른 하나는 다음 노드를 가리키는 구조를 가지고 있다. 이로 인해 삽입과 삭제 작업이 빠륵 수행될 수 있다.

 

1. LinkedLists 주요 특징

이중 연결 리스트

LinkedList는 이중 연결 리스트로 구현되어 있어 삽입과 삭제가 빠르다. 리스트이 중간에 있는 요소를 추가하거나 삭제할 때, 인덱스를 찾아가는 시간이 필요하지만 요소의 추가/삭제 작업 자체를 빠르게 이루어진다.

양방향 탐색 가능

이중 연결 리스트는 리스트의 앞에서부터 또는 뒤에서부터 탐색할 수 있다. 따라서 앞쪽이나 뒤쪽에 새로운 요소를 추가하거나 제거하는 작업이 빠르다.

동기화되지 않음

LinkedList는 기본적으로 동기화되지 않으므로 멀티스레드 환경에서 사용하기 위해서는 외부적으로 동기화 처리해야 한다.

중간 삽입/삭제에 유리

배열 기반 자료구조인 ArrayList와 달리, LinkedList는 중간에 삽입 또는 삭제하는 작업이 효율저거이다. 하지만 특정 인덱스에 접근할 때는 탐색 시간이 필요하다.

 

2. LinkedList의 클래스 선언

public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    // LinkedList의 크기를 나타내는 변수
    transient int size = 0;

    // 첫 번째 노드를 가리키는 참조
    transient Node<E> first;

    // 마지막 노드를 가리키는 참조
    transient Node<E> last;

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

    // 기타 메서드 생략...
}

 

LinkedList는 List와 Deque 인터페이스를 구현하고 있으며, 이중 연결 리스트 구조로 되어 있다. 리스트의 각 요소는 Node 객체로 표현되며, Node는 item, next, prev 세 개의 필드를 가진다.

• first : 리스트의 첫 번째 요소를 가리키는 참조이다.
• last : 리스트의 마지막 요소를 가리키는 참조이다.

 

3. 주요 메소드의 구현

1. add(E e)

LinkedList에서 요소를 추가하는 add 메소드는 리스트의 끝에 요소를 추가하는 작업이다. 새로운 노드를 생성하고, 이를 리스트의 끝에 연결한다.

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

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

 

• linkLast(E e) 메소드는 새로운 요소를 마지막 노드로 추가한다.
• last 참조가 null이면 리스트가 비어 있음을 의미하므로, 새 노드를 first로 설정한다. 그렇지 않으면 마지막 노드의 next 필드에 새 노드를 연결한다.

2. remove(Object o)

remove 메소드는 리스트에서 특정 객체를 삭제하는 역할을 한다. 객체가 리스트에 존재하는지 확인한 후, 해당 객체를 가리키는 노드를 제거한다.

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

E unlink(Node<E> x) {
    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(Node<E> x) 메소드를 사용해, 대상 노드를 연결 리스트에서 제거한다. 노드의 이전 노드와 다음 노드를 서로 연결하고, 현재 노드를 null로 만든다.

3. get(int index)

get 메소드는 주어진 인덱스에 있는 요소를 반환한다. 인덱스에 따라 리스트의 앞 또는 뒤에서부터 순회하여 해당 요소를 찾는다.

public E get(int index) {
    checkElementIndex(index);  // 인덱스가 유효한지 확인
    return node(index).item;
}

Node<E> node(int 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;
    }
}

 

• 탐색 최적화 : 인덱스가 리스트의 중간보다 앞에 있으면 first부터, 중간보다 뒤에 있으면 last부터 탐색해 효율적으로 요소를 찾는다.
• 시간 복잡도 : 최악의 경우 O(n) 시간이 걸리며, 리스트의 중간에 가까운 인덱스일수록 탐색 시간이 길어진다.

4. addFirst(E e), addLast(E e), removeFirsts(), removeLast()

LinkedList는 Deque 인터페이스를 구현하므로, 리스트의 앞과 뒤에서 요소를 삽입하거나 제거하는 메소드도 제공한다.

public void addFirst(E e) {
    linkFirst(e);
}

public void addLast(E e) {
    linkLast(e);
}

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

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

 

이 메소드들은 리스트의 양 끝에서 삽입과 삭제를 지원하며, O(1) 시간 복잡도로 실행된다.

 

4. 시간 복잡도

삽입과 삭제

리스트의 양 끝에서 삽입과 삭제는 O(1) 시간 복잡도를 가진다. 리스트의 중간에서 삽입이나 삭제는 특정 인덱슬르 찾기 위해 탐색 시간이 필요하므로 O(n) 시간 복잡도가 발생한다.

탐색

인덱스를 통해 요소를 찾는 작업은 O(n) 시간이 걸린다. 배열 기반인 ArrayList와 달리, LinkedList는 임의 접근이 빠르지 않다.

 

5. LinkedList vs ArrayList

• LinkedList는 요소의 중간에 삽입 및 삭제가 빈번할 때 유리하다. 특히 리스트 앞 뒤에 요소를 추가하거나 제거하는 경우 빠른 성능을 발휘한다.
• ArrayList는 임의 접근이 필요한 경우에 더 적합하다. 배열 기반이므로 인덱스 기반의 요소 접근이 빠르며, 메모리 효율성 면에서도 더 좋을 수 있다.

 

결론

자바의 LinkedList는 이중 연결 리스트로 구현되어 있으며, 양방향 탐색이 가능하고 삽입과 삭제가 빠르다. List, Deque, Queue 인터페이스를 구현해 다양하나 자료구조로 활용할 수 있으며, 요소의 중간 삽입/삭제 작업이 많은 경우에 유용합니다. 하지만 임의 접근 속도가 느리므로, 자주 사용되는 작업에 맞는 자료구조를 선택하는 것이 중요하다.