연결 리스트

연결 리스트는 값을 메모리 여기저기에 흩어 둔 채로 한 줄로 이어 쓰는 그릇입니다. 값마다 다음 값이 어디 있는지를 같이 적어 두기 때문에, 가운데에 값을 끼우거나 빼도 나머지 값을 밀거나 당기지 않습니다. 대신 몇 번째 값인지로 바로 집을 수 없습니다. 맨 앞에서부터 하나씩 따라가야 합니다.

쉽고 빠른 이해

연결 리스트는 값을 한 줄로 이어 담는 자료구조입니다. 보물찾기 쪽지와 같습니다. 쪽지 하나에 값 하나와 「다음 쪽지는 저기」라는 안내가 같이 적혀 있습니다.

값을 나란히 붙여 담으면 가운데에 하나를 끼워 넣을 때마다 뒤쪽 값을 전부 한 칸씩 밀어야 합니다. 연결 리스트는 안내만 고쳐 쓰면 되니 밀 것이 없습니다.

어떻게 도나:

값 하나와 「다음은 저기」라는 안내, 곧 다음 값의 주소를 한 덩어리로 묶습니다
덩어리끼리 주소로 이어 붙여 줄을 만듭니다
줄의 맨 앞이 어디인지만 따로 들고 다닙니다

대가는 몇 번째 값인지로 바로 못 집는다는 것입니다. 세 번째 값을 보려면 맨 앞에서 안내를 두 번 따라가야 합니다.

그래서 넣고 빼는 일이 잦을 때 씁니다. 번호로 자주 꺼내야 한다면 배열이 낫습니다.

상세

연결 리스트는 값 하나와 「다음은 저기」라는 주소를 한 덩어리로 묶어 줄을 만듭니다. 이 절은 그 덩어리 하나의 꼴에서 시작합니다. 그다음 끼우고 빼는 일, 드는 시간과 메모리, 방향을 하나 더 둔 꼴, 고르는 때를 차례로 봅니다. 사과와 포도와 귤을 담은 줄 하나를 끝까지 들고 갑니다.

값과 주소를 묶은 노드

연결 리스트는 값을 하나씩 따로 담습니다. 그 하나하나가 노드입니다.

노드는 칸을 둘 가집니다. 하나는 담으려는 값입니다. 다른 하나는 다음 노드가 메모리 어디에 있는지를 적은 주소입니다.

이 주소를 포인터라고 부릅니다. 포인터가 있어야 흩어져 있는 노드를 차례로 따라갈 수 있습니다. 줄의 마지막 노드는 다음이 없다는 표시를 담습니다. 따라가던 것이 거기서 끝난다는 뜻입니다.

줄의 첫 노드를 가리키는 포인터는 노드 바깥에 따로 들고 다닙니다. 이것을 머리라고 부릅니다. 머리 하나만 있으면 나머지 노드는 전부 따라가서 찾습니다. 머리를 잃으면 줄 전체를 잃습니다.

flowchart TD
    H["머리 포인터"]
    subgraph A["노드"]
        A1["값 · 사과"]
        A2["다음 · 주소"]
    end
    subgraph B["노드"]
        B1["값 · 포도"]
        B2["다음 · 주소"]
    end
    subgraph C["노드"]
        C1["값 · 귤"]
        C2["다음 · 없음"]
    end
    H --> A1
    A2 --> B1
    B2 --> C1

그림에서 화살표는 전부 포인터입니다. 화살표는 노드의 다음 칸에서 나가 다음 노드로 들어갑니다. 귤은 다음이 없으니 줄은 거기서 끝납니다.

가운데에 값을 끼워 넣기

값을 메모리에 나란히 붙여 담는 배열은 가운데에 값 하나를 끼워 넣을 때마다 그 뒤의 값을 전부 한 칸씩 밀어야 합니다. 담긴 값이 백만 개라면, 맨 앞에 하나를 끼워 넣을 때 백만 개를 전부 밉니다. 연결 리스트는 이 밀기를 없앤 구조입니다.

block-beta
columns 6
  t1["넣기 전"] a1["사과"] a2["포도"] a3["귤"] a4["감"] space
  t2["넣은 뒤"] b1["새 값"] b2["사과"] b3["포도"] b4["귤"] b5["감"]
  t3["앞에 하나를 넣으면 뒤의 값이 전부 한 칸씩 옮겨 앉는다"]:6

윗줄은 값을 붙여 담은 배열입니다. 아랫줄은 맨 앞에 새 값 하나를 넣은 뒤입니다. 값 넷이 전부 옆 칸으로 옮겨 앉았습니다.

사과와 포도 사이에 멜론을 넣는다고 해 보겠습니다. 먼저 멜론을 담은 노드를 하나 만들고, 그 노드의 다음 주소에 포도를 적습니다. 그다음 사과의 다음 주소를 멜론으로 고쳐 씁니다.

flowchart TD
    H2["머리 포인터"] --> A3["사과"]
    A3 -. "고쳐 쓰기 전 주소" .-> B3["포도"]
    A3 -->|"② 고쳐 씀"| M3["멜론"]
    M3 -->|"① 새로 적음"| B3
    B3 --> C3["귤"]

고쳐 쓴 주소는 둘뿐입니다. 점선은 고쳐 쓰기 전 사과의 다음 주소입니다. 실선 둘이 이번에 손댄 주소입니다.

포도와 귤은 원래 있던 곳에 그대로 있습니다. 줄에 값이 백만 개 더 달려 있었어도 고쳐 쓸 주소는 여전히 둘입니다.

빼는 일도 같은 식입니다. 포도를 빼려면 사과의 다음 주소를 귤로 고쳐 쓰면 됩니다. 이제 포도 노드는 아무도 가리키지 않습니다. 그 메모리는 가비지 컬렉션이 거두거나 프로그램이 직접 돌려줍니다.

다만 주소를 고쳐 쓰려면 그 앞 노드를 먼저 손에 쥐고 있어야 합니다. 앞 노드를 찾으려면 머리부터 훑어야 합니다. 「끼우고 빼는 것이 싸다」는 말은 넣고 뺄 곳을 이미 잡고 있을 때의 이야기입니다.

드는 시간과 메모리

담긴 값이 n 개라고 해 보겠습니다. 걸리는 시간이 개수와 상관없이 일정하면 O(1) 이라고 적습니다. 개수에 비례해 늘어나면 O(n) 이라고 적습니다. 이렇게 적는 방법이 시간 복잡도입니다.

하는 일	걸리는 시간	까닭
맨 앞에 넣기·빼기	O(1)	머리 포인터 하나만 고쳐 씁니다
잡고 있는 곳에 끼우기·빼기	O(1)	앞뒤 주소 둘만 고쳐 씁니다
몇 번째 값 꺼내기	O(n)	머리에서부터 하나씩 따라갑니다
값으로 찾기	O(n)	앞에서부터 하나씩 견줍니다

표의 아래 두 줄이 연결 리스트가 치르는 대가입니다. 배열은 몇 번째 값이든 주소를 계산해서 한 번에 가지만, 연결 리스트는 노드가 흩어져 있어 계산할 거리가 없습니다.

메모리도 더 듭니다. 노드마다 값 말고 주소가 하나씩 붙으니 값 n 개를 담으면 주소도 n 개입니다. 담는 값이 작을수록 이 부담이 두드러집니다. 값 하나가 주소 하나보다 작으면 담은 것보다 이어 붙이는 데 메모리를 더 씁니다.

훑는 시간도 배열과 갈립니다. 프로세서는 메모리에서 값 하나를 읽을 때 그 값만이 아니라 그 값이 놓인 메모리 한 토막을 함께 가져옵니다. 배열은 값이 붙어 있어 다음 값이 이미 따라와 있습니다. 연결 리스트는 노드가 흩어져 있어 대개 매번 새로 가져와야 합니다.

block-beta
columns 7
  ax["메모리 주소가 커지는 방향 →"]:7
  t4["배열"] d1["사과"] d2["포도"] d3["귤"] d4["감"] d5["배"] space
  space g1["한 번에 딸려온 한 토막"]:3 space:3
  t5["연결 리스트"] e1["사과"] f1["다른 값"] e2["포도"] f2["다른 값"] f3["다른 값"] e3["귤"]

윗줄은 배열이라 값 다섯이 붙어 있습니다. 아랫줄은 같은 축 위에 노드가 흩어져 있습니다. 노드 사이사이에는 다른 값이 들어 있습니다.

가까운 메모리를 이어 읽는 이 경향이 참조 지역성입니다. 연결 리스트는 그 덕을 덜 봅니다. 그래서 같은 O(n) 훑기라도 배열보다 느릴 때가 많습니다.

한 방향과 양 방향

지금까지 본 것은 노드마다 다음 주소 하나만 두는 꼴입니다. 이것이 단일 연결 리스트입니다. 앞으로만 갈 수 있어서 어떤 노드의 앞 노드를 알려면 머리부터 다시 훑어야 합니다.

노드마다 앞 노드의 주소를 하나 더 두면 양쪽으로 갈 수 있습니다. 이것이 이중 연결 리스트입니다. 주소를 하나 더 담는 대신 뒤로 돌아가는 일이 싸집니다. 마지막 노드의 다음을 첫 노드로 이어 붙여 고리로 만든 것은 원형 연결 리스트입니다.

flowchart TD
    subgraph S["단일 · 다음 주소 하나"]
        direction TB
        S1["사과"] --> S2["포도"] --> S3["귤"]
    end
    subgraph D["이중 · 앞 주소를 하나 더"]
        direction TB
        D1["사과"] <--> D2["포도"] <--> D3["귤"]
    end
    subgraph R["원형 · 마지막이 첫 노드로"]
        direction TB
        R1["사과"] --> R2["포도"] --> R3["귤"]
        R3 --> R1
    end
    S ~~~ D
    D ~~~ R

세 꼴 모두 노드 하나의 생김새는 같습니다. 달라지는 것은 주소를 몇 개 두고 어디로 잇느냐뿐입니다.