단순 연결리스트 직접 구현하기

[10, 30] 사이에 20을 넣는다고 해 보자. 배열 기반 리스트는 뒤쪽 값을 한 칸씩 옮겨 자리를 만들지만, 연결리스트는 10 → 30이라는 연결을 10 → 20 → 30으로 바꾼다. 이 차이를 이해하려면 데이터뿐 아니라 다음 노드를 가리키는 참조를 함께 봐야 한다. 아래에서는 Java로 단방향 연결리스트를 구현하고, 삽입·삭제 때 어떤 참조가 바뀌는지 따라간다.

이 구현은 학습용 SinglyLinkedList다. Java 표준 java.util.LinkedList는 양방향 연결리스트이며 List와 Deque를 구현한다. 같은 이름을 사용하면 표준 클래스와 혼동하기 쉬워 별도 이름을 사용한다(Java LinkedList 문서).

노드와 리스트가 유지해야 하는 상태

노드 하나에는 값 value와 다음 노드 next가 있다. 마지막 노드의 next는 null이다. 배열 인덱스처럼 세 번째 노드로 바로 점프할 수는 없고, 앞에서부터 next를 따라가야 한다.

flowchart LR
    H[header: 더미 노드] --> A[10]
    A --> B[20]
    B --> C[30]
    C --> N[null]
    T[tail] --> C

header는 데이터를 저장하지 않는 더미 노드다. 첫 데이터가 header.next에 있으므로 첫 원소를 삽입하거나 삭제할 때도 “이전 노드의 next를 바꾼다”는 동일한 규칙을 적용할 수 있다. 더미 노드 자체는 생성 후 사라지지 않는다. 따라서 빈 리스트 판정은 header == null이 아니라 size == 0 또는 header.next == null이다.

끝에 넣는 작업을 빠르게 하려고 tail도 저장한다. 빈 리스트에서는 tail == header이고, 원소가 있으면 실제 마지막 노드를 가리킨다. 다음 세 조건을 모든 연산 뒤에 유지해야 한다.

• size는 더미 노드를 제외한 실제 데이터 노드 수다.
• header.next에서 출발해 도달한 노드 수는 size와 같다.
• tail.next는 항상 null이며, 마지막 원소를 삭제하면 tail을 이전 노드로 되돌린다.

이 조건을 불변식(invariant)이라고 한다. 연결리스트 구현의 오류는 대개 값 계산보다 이 불변식을 깨뜨리는 참조 변경에서 발생한다.

인덱스의 유효 범위가 다른 이유

원소가 세 개라면 읽거나 삭제할 수 있는 위치는 0, 1, 2다. 반면 삽입은 기존 원소 뒤에 붙이는 위치 3도 허용해야 한다. 그래서 조회·삭제는 0 <= index < size, 삽입은 0 <= index <= size로 검사한다. remove(size)를 허용하면 마지막 노드 다음의 null을 삭제하려다가 예외가 난다.

이 구분은 표준 List의 인덱스 연산 계약과도 같다. 범위 밖 요청은 내부 순회를 시작하기 전에 IndexOutOfBoundsException으로 거절한다. 잘못된 요청 때문에 size나 참조 일부만 변경되는 상태를 만들지 않는 것이 목적이다.

전체 구현

아래 코드는 SinglyLinkedList.java에 저장한다. 노드는 외부에 공개하지 않는다. 호출자가 next를 직접 바꾸면 원소 개수와 실제 연결이 달라지거나 순환 연결이 생길 수 있기 때문이다. 값으로 null을 저장하는 것은 허용하되, 원소 존재 여부는 size로 판단한다.

public final class SinglyLinkedList<E> {
    private static final class Node<E> {
        private final E value;
        private Node<E> next;

        private Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }

    private final Node<E> header = new Node<>(null, null);
    private Node<E> tail = header;
    private int size;

    public int size() {
        return size;
    }

    public void addFirst(E value) {
        add(0, value);
    }

    public void addLast(E value) {
        Node<E> node = new Node<>(value, null);
        tail.next = node;
        tail = node;
        size++;
    }

    public void add(int index, E value) {
        checkPosition(index);
        if (index == size) {
            addLast(value);
            return;
        }
        Node<E> previous = predecessor(index);
        previous.next = new Node<>(value, previous.next);
        size++;
    }

    public E get(int index) {
        checkElement(index);
        return predecessor(index).next.value;
    }

    public E remove(int index) {
        checkElement(index);
        Node<E> previous = predecessor(index);
        Node<E> removed = previous.next;
        previous.next = removed.next;
        if (removed == tail) {
            tail = previous;
        }
        size--;
        return removed.value;
    }

    // 삽입하거나 읽을 위치의 바로 앞 노드를 반환한다.
    // index == 0이면 더미 노드가 그 역할을 한다.
    private Node<E> predecessor(int index) {
        Node<E> current = header;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current;
    }

    private void checkPosition(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
        }
    }

    private void checkElement(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
        }
    }

    @Override
    public String toString() {
        StringBuilder result = new StringBuilder("[");
        for (Node<E> node = header.next; node != null; node = node.next) {
            if (node != header.next) result.append(", ");
            result.append(node.value);
        }
        return result.append(']').toString();
    }
}

중간 삽입에서 기존 연결을 보존하기

[10, 30]에서 add(1, 20)을 호출하면 predecessor(1)은 10 노드를 반환한다. new Node<>(20, previous.next)를 만드는 순간 새 노드의 next에 기존 30 노드가 저장된다. 그 뒤 previous.next를 새 노드로 바꾸므로 뒷부분을 잃지 않는다.

두 줄로 나눠 구현한다면 newNode.next = previous.next를 먼저 하고 previous.next = newNode를 나중에 해야 한다. 순서를 반대로 한 뒤 변경된 previous.next를 새 노드에 넣으면 자기 자신을 가리키는 순환이 생길 수 있다. 그러면 toString() 같은 끝을 찾는 순회가 종료되지 않는다.

마지막 삭제에서 tail을 함께 옮기기

remove(2)로 [10, 20, 30]의 마지막 값을 지우면 20.next를 null로 바꾸는 것으로 연결은 끊긴다. 하지만 tail이 계속 30을 가리키면 다음 addLast(40)은 리스트에서 떨어진 30 뒤에 붙는다. size는 늘지만 실제 목록에서는 40을 볼 수 없는 상태가 된다.

그래서 removed == tail이면 tail = previous를 실행한다. 원소가 하나일 때 remove(0)을 해도 previous가 header이므로 빈 리스트의 tail == header 조건이 자연스럽게 복구된다. 이 경우를 별도 분기로 복잡하게 처리하지 않아도 되는 것이 더미 노드의 장점이다.

호출 순서와 예상 결과

public class ListExample {
    public static void main(String[] args) {
        SinglyLinkedList<Integer> values = new SinglyLinkedList<>();
        values.addLast(10);
        values.addLast(30);
        values.add(1, 20);
        System.out.println(values);       // [10, 20, 30]
        System.out.println(values.get(1)); // 20
        System.out.println(values.remove(2)); // 30
        values.addLast(40);
        System.out.println(values);       // [10, 20, 40]
        values.remove(0);
        values.remove(0);
        values.remove(0);
        values.addFirst(99);
        System.out.println(values);       // [99]
    }
}

마지막 세 번의 삭제와 재삽입은 빈 상태로 돌아갔다가 다시 사용하는 경로다. 중간 삽입만 성공하는지 확인하면 tail 갱신 오류를 놓치기 쉽다. 경계 조건은 아래처럼 데이터 상태와 연산을 같이 놓고 생각한다.

시작 상태	연산	확인할 결과
빈 리스트	add(0, 10)	첫 노드와 마지막 노드가 같다
빈 리스트	get(0)	원소가 없으므로 범위 예외
원소 1개	remove(0)	크기 0, 이후 다시 추가 가능
원소 3개	add(3, 40)	뒤에 추가 가능
원소 3개	remove(3)	변경 전에 범위 예외
원소 여러 개	중간 삭제	앞과 뒤가 직접 연결됨

연결 변경 비용과 탐색 비용 구분

“연결리스트 삽입은 O(1)”이라는 문장은 삽입 위치의 이전 노드를 이미 알고 있을 때에만 맞는다. 이 예제처럼 인덱스로 요청하면 해당 위치까지 순회하는 비용이 먼저 발생한다.

연산	시간 복잡도	이유
size()	O(1)	저장한 원소 수 반환
addFirst()	O(1)	더미 노드 다음 연결 변경
addLast()	O(1)	tail을 직접 사용
get(i) / add(i, value)	O(n), 마지막 추가 예외	앞에서 i번 이동
remove(i)	O(n)	이전 노드를 찾아야 함
toString()	O(n)	각 노드를 한 번씩 방문

단방향 리스트는 tail이 있어도 마지막 노드의 이전 노드를 알 수 없으므로 마지막 삭제는 O(n)이다. 양방향 연결을 추가하면 뒤로 갈 수 있지만 노드마다 참조 한 개가 더 필요하고 삽입·삭제 때 맞출 연결도 늘어난다.

또한 for (int i = 0; i < size; i++) get(i)처럼 순회하면 매번 맨 앞에서 다시 출발해 총 O(n²)이 된다. 전체 처리는 위 toString()처럼 한 번의 노드 순회로 수행하거나 iterator를 제공하는 방식으로 설계한다. 실제 애플리케이션에서 인덱스 접근과 순차 읽기가 많다면 배열 기반 리스트가 더 자연스러운 경우가 많다. 노드별 객체 할당, 참조 추적, 캐시 접근 특성까지 고려해야 하므로 점근적 복잡도 하나로 속도를 단정하지 않는다.

마지막으로 이 구현은 여러 스레드가 동시에 수정하는 상황을 지원하지 않는다. next, tail, size 변경은 하나의 연산으로 관찰되어야 하지만 현재 코드는 그 동기화를 제공하지 않는다. 실무에서는 사용 목적에 맞는 표준 컬렉션과 동시성 자료구조를 먼저 선택하고, 직접 구현은 연결과 경계 조건을 이해하는 학습 예제로 사용한다.