연결 리스트 (Linked List)

정의

연결 리스트 (Linked List) 는 노드 + 포인터로 구성된 선형 자료구조. 각 노드는 데이터 + 다음 노드 포인터.

종류:

• Singly Linked List: 노드가 next 포인터 1개. 한 방향 순회.
• Doubly Linked List: 노드가 prev, next 포인터 2개. 양방향 순회.
• Circular Linked List: 마지막 노드의 next 가 head. 순환.

C++ STL std::list 는 doubly linked list, Java LinkedList 도 doubly. Python 표준 라이브러리에는 linked list 없음 (대신 collections.deque 나 직접 구현).

문제 상황과 동기

배열은 랜덤 접근 O(1), 삽입/삭제 O(N) (shift). 연결 리스트는 랜덤 접근 O(N), 삽입/삭제 O(1) (포인터 조작만).

• naive (배열): 중간 삽입 시 뒤 원소를 모두 shift. O(N).
• linked list: 중간 삽입 시 포인터 2개만 바꾸면 됨. O(1) (삽입 위치를 이미 알 때).

핵심 통찰: 메모리는 불연속, 포인터로 순서 유지. 캐시 locality 는 나쁘지만, 삽입/삭제가 잦으면 유리.

시각화

핵심 아이디어

Singly Linked List

struct Node {
    int data;
    Node* next;
};

invariant: head 에서 시작, next 를 따라가면 모든 노드 방문. 끝 노드의 next 는 nullptr.

Doubly Linked List

struct Node {
    int data;
    Node* prev;
    Node* next;
};

양방향 순회 가능. 삭제 시 prev 만 알아도 이전 노드에 접근 가능.

연산

1. 삽입 (insertion):

   • 삽입 위치 노드 cur 를 찾는다 (O(N) 순회).
   • 새 노드 new 를 만든다.
   • new->next = cur->next, cur->next = new. (singly)
   • doubly 는 new->prev = cur, new->next = cur->next, cur->next->prev = new, cur->next = new.
   • 포인터 조작만 O(1), 위치 찾는 게 O(N).

2. 삭제 (deletion):

   • 삭제할 노드 del 을 찾는다 (O(N) 순회).
   • singly: 이전 노드 prev 를 찾아 prev->next = del->next. (이전 노드 찾기 O(N)).
   • doubly: del->prev->next = del->next, del->next->prev = del->prev. 이전 노드 찾기 불필요.
   • 노드 free. 포인터 조작 O(1).

3. 탐색 (search): head 에서 순회. O(N).

캐시 locality: 배열은 연속 메모리, 캐시 친화. 연결 리스트는 노드가 흩어져 있음, 캐시 miss 많음. 큰 N 에서 배열이 더 빠를 수 있다.

알고리즘

Singly Linked List 삽입 (head 에 삽입)

insert_front(head, data):
    new = new Node(data)
    new->next = head
    head = new
    return head

Doubly Linked List 삭제 (노드 del 삭제)

delete_node(del):
    if del->prev:
        del->prev->next = del->next
    if del->next:
        del->next->prev = del->prev
    free(del)

순회 (singly)

traverse(head):
    cur = head
    while cur != nullptr:
        process(cur->data)
        cur = cur->next

구현

// Singly Linked List, head 에 삽입 후 순회
#include <bits/stdc++.h>
using namespace std;
struct Node {
  int data;
  Node* next;
  Node(int d) : data(d), next(nullptr) {}
};
int main() {
  int n; cin >> n;
  Node* head = nullptr;
  for (int i = 0; i < n; i++) {
      int x; cin >> x;
      Node* newNode = new Node(x);
      newNode->next = head;
      head = newNode;
  }
  // 순회
  Node* cur = head;
  while (cur) {
      cout << cur->data << " ";
      cur = cur->next;
  }
}

# Python 직접 구현 (singly linked list)
class Node:
  def __init__(self, data):
      self.data = data
      self.next = None
​
n = int(input())
head = None
for _ in range(n):
  x = int(input())
  new_node = Node(x)
  new_node.next = head
  head = new_node
​
# 순회
cur = head
ans = []
while cur:
  ans.append(str(cur.data))
  cur = cur.next
print(" ".join(ans))

// Java LinkedList (STL, doubly linked list)
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      LinkedList<Integer> list = new LinkedList<>();
      for (int i = 0; i < n; i++) {
          list.addFirst(Integer.parseInt(br.readLine())); // head 에 삽입
      }
      StringBuilder sb = new StringBuilder();
      for (int x : list) {
          sb.append(x).append(" ");
      }
      System.out.println(sb);
  }
}

5
1
2
3
4
5

5 4 3 2 1

복잡도

변형 / 활용

함정

1. 메모리 누수 (memory leak)

C++ 에서 delete 안 하면 메모리 누수. Python / Java 는 GC.

2. 이전 노드 찾기 (singly)

singly linked list 에서 노드 삭제 시, 이전 노드를 찾아야 한다. O(N) 순회. doubly 는 prev 포인터로 O(1).

3. 포인터 null 체크

cur->next 를 쓰기 전에 cur != nullptr 체크. segfault 조심.

4. 순환 리스트 무한 루프

circular linked list 에서 종료 조건 잘못 쓰면 무한 루프. head 로 돌아왔는지 체크.

5. Cache locality

배열보다 캐시 miss 많다. 큰 N + 순회 많으면 배열이 더 빠를 수 있다. Linked list 는 삽입/삭제가 지배적일 때만 유리.

BOJ 연습 문제

참고

• 배열
• 덱
• LRU Cache
• Skip List