연결 리스트 (Linked List)

연결 리스트(Linked List)는 값과 다음 노드를 가리키는 포인터(pointer)를 묶은 노드(node)들을 사슬처럼 이어서 데이터를 순서대로 저장하는 선형 자료구조다. 연결 리스트는 메모리의 연속성을 요구하지 않기 때문에 크기를 자유롭게 늘릴 수 있고, 노드의 연결만 바꾸면 되므로 삽입과 삭제가 가볍다는 특징이 있다. 대신 원하는 위치에 접근하려면 머리부터 포인터를 따라가야 하므로 임의 접근이 느리다.

구조와 종류

가장 단순한 형태인 단일 연결 리스트(singly linked list)는 각 노드가 값과 다음 노드의 참조 하나만 가진다. 리스트 전체는 첫 노드를 가리키는 머리(head) 포인터로 표현되며, 마지막 노드의 다음 참조는 널(null)이다.

이중 연결 리스트(doubly linked list)는 각 노드가 이전 노드의 참조까지 갖는다. 양방향 순회가 가능하고, 어떤 노드를 쥐고 있을 때 그 노드 자신을 O(1)에 삭제할 수 있다는 것이 큰 장점이다. 단일 연결 리스트에서는 삭제할 노드의 이전 노드를 알아야 하므로 같은 작업에 탐색이 필요하다. 대신 포인터가 하나 더 붙어 메모리를 더 쓴다.

원형 연결 리스트(circular linked list)는 마지막 노드가 다시 첫 노드를 가리켜 끝이 없는 고리를 이룬다. 라운드 로빈(round robin) 방식의 스케줄링처럼 순환 구조가 자연스러운 문제에 쓰인다.

주요 연산과 시간 복잡도

연산	시간 복잡도	비고
머리에 삽입/삭제	O(1)	head 포인터만 바꾼다
꼬리에 삽입	O(1)	tail 포인터를 유지할 때
인덱스 접근	O(n)	머리부터 순차 이동한다
값 탐색	O(n)	정렬 여부와 무관하게 순차 탐색만 가능하다
노드 참조를 쥔 상태의 삽입/삭제	O(1)	포인터 연결만 바꾼다(이중 연결 기준)

핵심은 "위치를 이미 알고 있는가"이다. 노드 참조를 쥐고 있다면 삽입과 삭제는 포인터 두어 개를 고쳐 쓰는 것으로 끝나지만, 위치를 찾는 것부터 시작해야 한다면 탐색 비용 O(n)이 앞에 붙는다. 정렬된 연결 리스트라도 이진 탐색(binary search)을 쓸 수 없다는 점도 배열과의 중요한 차이다. 중간 지점으로 한 번에 점프할 방법이 없기 때문이다.

코드 예시

다음은 단일 연결 리스트의 노드 정의와 머리 삽입, 그리고 특정 값을 가진 노드를 삭제하는 자바(Java) 예시다. 삭제는 이전 노드의 next를 건너뛰게 만드는 것이 전부다.

class Node {
    int value;
    Node next;
    Node(int value) { this.value = value; }
}

// 머리에 삽입: O(1)
Node insertFirst(Node head, int value) {
    Node node = new Node(value);
    node.next = head;
    return node; // 새 head
}

// 값으로 삭제: 탐색 O(n) + 연결 변경 O(1)
Node delete(Node head, int target) {
    if (head == null) return null;
    if (head.value == target) return head.next;
    Node prev = head;
    while (prev.next != null && prev.next.value != target) {
        prev = prev.next;
    }
    if (prev.next != null) prev.next = prev.next.next;
    return head;
}