연결 리스트(Linked List)의 구조와 동작 원리

 

이 글은 매일메일 서비스에서 받은 면접 질문을 바탕으로 작성한 글입니다.

 

연결 리스트는 배열과 함께 가장 기본적인 선형 자료구조 중 하나다. 배열과 달리 메모리 상에 연속적으로 저장되지 않기 때문에, 삽입과 삭제에서 뚜렷한 장점을 가진다. 자료구조를 선택할 때 연결 리스트의 특성을 이해하고 있으면 더 적절한 선택을 할 수 있다.

---

연결 리스트란

연결 리스트는 노드(Node) 들을 포인터로 연결하여 구성하는 선형 자료구조다.

• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다
• 첫 번째 노드를 HEAD, 마지막 노드를 TAIL이라 한다
• 메모리 상에 연속적으로 저장되지 않아도 포인터로 연결이 가능하다

[HEAD: Node1] → [Node2] → [Node3] → [TAIL: Node4] → null
  data | next    data | next   data | next   data | null

---

시간 복잡도

연산	시간 복잡도
탐색	O(n)
삽입 (위치 알고 있을 때)	O(1)
삭제 (위치 알고 있을 때)	O(1)

• 탐색: HEAD부터 순차적으로 순회해야 하므로 최악의 경우 O(n)
• 삽입/삭제: 포인터 변경만으로 처리되므로 O(1)이지만, 위치를 먼저 탐색해야 한다면 O(n)이 소요된다

---

단일 연결 리스트의 주요 연산

탐색

HEAD에서 시작해 포인터를 따라 순차적으로 이동하며 원하는 데이터를 찾는다. 배열처럼 인덱스로 직접 접근이 불가능하기 때문에 최악의 경우 모든 노드를 순회한다.

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Node search(Node head, int target) {
    Node current = head;
    while (current != null) {
        if (current.data == target) return current;
        current = current.next;
    }
    return null;
}

삽입

새 노드를 삽입하려면 이전 노드의 포인터를 새 노드로 바꾸고, 새 노드의 포인터를 기존 다음 노드로 연결한다.

삽입 전: A → C
삽입 후: A → B → C

1. B.next = C
2. A.next = B

void insertAfter(Node prevNode, Node newNode) {
    newNode.next = prevNode.next;
    prevNode.next = newNode;
}

삭제

삭제할 노드의 이전 노드가 삭제 대상의 다음 노드를 직접 가리키도록 포인터를 변경한다.

삭제 전: A → B → C
삭제 후: A → C

A.next = B.next  (즉, A.next = C)

void deleteNode(Node prevNode) {
    prevNode.next = prevNode.next.next;
}

---

연결 리스트의 종류

• 단일 연결 리스트 (Singly Linked List): 다음 노드 방향으로만 이동 가능
• 이중 연결 리스트 (Doubly Linked List): 이전/다음 노드 양방향 이동 가능, 노드마다 포인터 두 개 보유
• 원형 연결 리스트 (Circular Linked List): TAIL이 HEAD를 가리켜 순환 구조를 형성

---

배열 vs 연결 리스트

구분	배열	연결 리스트
메모리 구조	연속적	비연속적
인덱스 접근	O(1)	O(n)
삽입/삭제	O(n)	O(1)
캐시 효율	높음	낮음

• 삽입/삭제가 빈번한 경우 → 연결 리스트
• 탐색이 빈번한 경우 → 배열

---

한 줄 정리

연결 리스트는 포인터로 노드를 연결하는 선형 자료구조로, 탐색은 O(n), 삽입/삭제는 O(1)이며 배열 대비 삽입/삭제에 강점을 가진다.