연결 리스트

TIL - 자료구조와 알고리즘: 연결 리스트

1. 연결 리스트란?

연결 리스트(Linked List)는 데이터를 Node(노드)라는 단위로 나누어 저장하고, 각 노드가 다음 노드를 가리키도록 연결한 자료구조이다.

가장 기본적인 형태인 단일 연결 리스트(Singly Linked List)는 다음과 같은 구조를 가진다.

Head
 ↓
[10 | 다음] → [20 | 다음] → [30 | nullptr]
                                  ↑
                                 Tail

각 Node는 크게 두 가지 정보를 가지고 있다.

[ 데이터 | 다음 Node의 주소 ]

예를 들어 다음과 같이 구성할 수 있다.

struct Node
{
    int Data;
    Node* Next;
};

Data는 실제 데이터를 저장하고, Next는 다음 Node의 주소를 저장한다.

예를 들어:

Node A;
Node B;

A.Data = 10;
A.Next = &B;

B.Data = 20;
B.Next = nullptr;

이렇게 하면 다음과 같은 연결이 만들어진다.

A
┌──────────────┐
│ Data = 10    │
│ Next ────────┼────→ B
└──────────────┘      ┌──────────────┐
                      │ Data = 20    │
                      │ Next = null  │
                      └──────────────┘

연결 리스트에서 중요한 점은 각 Node가 메모리상에서 반드시 붙어 있을 필요가 없다는 것이다.

배열은 일반적으로 데이터를 연속된 메모리 공간에 저장한다.

[10][20][30][40]

반면 연결 리스트는 Node들이 메모리상에서 떨어져 있더라도 서로의 주소를 저장하여 연결할 수 있다.

[10] ─────→ [20]
             │
             ↓
           [30] ─────→ [40]

즉, 연결 리스트의 핵심은 데이터와 다음 데이터의 위치를 함께 저장하여 Node들을 연결하는 것이다.

---

2. Node

Node는 연결 리스트를 구성하는 가장 기본적인 단위이다.

단일 연결 리스트의 Node는 일반적으로 다음과 같이 구성할 수 있다.

struct Node
{
    int Data;
    Node* Next;
};

각 멤버의 역할은 다음과 같다.

int Data;

실제 데이터를 저장한다.

Node* Next;

다음 Node의 메모리 주소를 저장한다.

따라서 Node 하나를 그림으로 나타내면:

┌───────────────┐
│ Data          │
├───────────────┤
│ Next          │
└───────────────┘

여러 Node가 연결되면:

[10 | Next] → [20 | Next] → [30 | nullptr]

와 같은 구조가 만들어진다.

여기서 마지막 Node는 더 이상 연결할 다음 Node가 없기 때문에 Next가 nullptr을 가리킨다.

---

3. Head와 Tail

연결 리스트를 관리하기 위해서는 최소한 첫 번째 Node가 어디에 있는지 알아야 한다.

이때 사용하는 것이 Head이다.

Head
 ↓
[10] → [20] → [30]

Head는 연결 리스트의 첫 번째 Node를 가리킨다.

그리고 마지막 Node를 쉽게 관리하기 위해 Tail을 사용할 수 있다.

[10] → [20] → [30]
                  ↑
                 Tail

Tail은 연결 리스트의 마지막 Node를 가리킨다.

따라서 다음과 같이 정리할 수 있다.

Head → 첫 번째 Node
Tail → 마지막 Node
마지막 Node → nullptr

예를 들어:

Head
 ↓
[10] → [20] → [30] → nullptr
                        ↑
                       Tail

연결 리스트를 구현할 때 Head와 Tail을 관리하면 처음과 끝에 데이터를 추가하는 작업 등을 효율적으로 처리할 수 있다.

---

4. 연결 리스트의 삽입

연결 리스트에서 중요한 연산 중 하나가 삽입(Insert)이다.

예를 들어 다음과 같은 연결 리스트가 있다고 하자.

[10] → [30]

여기에 20을 중간에 삽입해서 다음과 같이 만들고 싶다고 하자.

[10] → [20] → [30]

배열이라면 중간에 새로운 데이터를 넣기 위해 기존 데이터를 뒤로 이동시켜야 할 수 있다.

[10][30][40][50]

        ↓

[10][20][30][40][50]

하지만 연결 리스트에서는 Node 자체를 이동시키는 것이 아니라 Node 사이의 연결 관계를 변경하면 된다.

기존에는:

10 → 30

이었던 것을:

10 → 20 → 30

으로 변경한다.

따라서 삽입할 위치의 Node를 이미 알고 있다면 연결 리스트에서의 삽입은 매우 효율적이다.

시간 복잡도는:

O(1)

이다.

단, 여기서 중요한 조건이 있다.

삽입할 위치를 이미 알고 있어야 한다.

만약 20을 어디에 넣어야 하는지 찾는 과정부터 필요하다면 이야기가 달라진다.

예를 들어:

[10] → [20] → [30] → [40] → [50]

에서 특정 값을 찾아 그 뒤에 삽입한다면 먼저 Node를 탐색해야 한다.

탐색에는 O(N)이 필요할 수 있기 때문에 전체 작업은 O(N)이 될 수 있다.

---

5. 연결 리스트의 삭제

삭제(Delete) 역시 연결 리스트의 중요한 연산이다.

다음과 같은 연결 리스트가 있다고 하자.

[10] → [20] → [30]

여기서 20을 삭제하면:

[10] → [30]

이 되어야 한다.

기존에는:

10 → 20 → 30

이었던 연결을:

10 → 30

으로 변경하면 된다.

즉, 20이라는 Node를 연결 리스트에서 제외시키는 것이다.

삽입과 마찬가지로 삭제할 Node의 위치를 이미 알고 있다면 연결 관계만 변경하면 되므로:

O(1)

의 시간 복잡도를 가질 수 있다.

하지만 삭제할 Node를 찾는 과정이 필요하다면:

탐색 O(N)
+
삭제 O(1)
=
O(N)

이 된다.

따라서 연결 리스트에서 흔히 말하는:

삽입과 삭제가 O(1)이다.

라는 표현은 정확하게는 해당 위치의 Node를 이미 알고 있는 경우를 의미한다.

---

6. 연결 리스트의 탐색

연결 리스트의 대표적인 단점 중 하나가 특정 위치에 빠르게 접근하기 어렵다는 것이다.

배열은:

[10][20][30][40][50]

에서 Array[3]을 사용하면 바로 40에 접근할 수 있다.

배열은 데이터가 연속된 메모리 공간에 존재하기 때문에 시작 주소와 인덱스를 이용해서 원하는 위치를 바로 계산할 수 있다.

따라서 배열의 인덱스를 이용한 접근은:

O(1)

이다.

반면 연결 리스트는:

Head
 ↓
[10] → [20] → [30] → [40] → [50]

와 같은 구조이기 때문에 40을 찾으려면 처음부터 Node를 따라가야 한다.

10 확인
 ↓
20 확인
 ↓
30 확인
 ↓
40 확인

따라서 연결 리스트의 탐색은:

O(N)

이다.

즉, 연결 리스트에서는 배열처럼:

List[3]

과 같은 방식으로 원하는 위치에 바로 접근할 수 없다.

---

7. 배열과 연결 리스트의 차이

연결 리스트를 배우는 가장 중요한 이유 중 하나는 배열과 비교했을 때 각각 어떤 장단점을 가지는지 이해하는 것이다.

항목배열연결 리스트

메모리	연속적인 공간	Node가 떨어져 있어도 됨
특정 위치 접근	O(1)	O(N)
탐색	O(N)	O(N)
중간 삽입	O(N)	O(1)*
중간 삭제	O(N)	O(1)*
구현 난이도	비교적 쉬움	비교적 어려움
추가 메모리	상대적으로 적음	포인터 저장 공간 필요
캐시 효율	좋음	상대적으로 낮음

*는 삽입하거나 삭제할 위치의 Node를 이미 알고 있는 경우이다.

가장 중요한 차이는 다음과 같이 생각할 수 있다.

배열
→ 특정 위치에 빠르게 접근하는 것이 강점

연결 리스트
→ Node의 연결을 변경하는 삽입/삭제가 강점

---

8. 왜 배열이 있는데 연결 리스트가 필요한가?

연결 리스트를 공부하면서 가장 중요한 질문이다.

"배열이 있는데 굳이 연결 리스트를 왜 사용하는가?"

연결 리스트의 장점은 데이터가 메모리상에서 반드시 연속적으로 존재할 필요가 없고, 특정 Node의 위치를 알고 있다면 삽입과 삭제를 빠르게 처리할 수 있다는 것이다.

예를 들어 배열에서 중간에 데이터를 삽입하면 뒤쪽 데이터를 이동시켜야 할 수 있다.

[10][20][30][40]

20 뒤에 25 삽입

[10][20][25][30][40]

기존 데이터의 위치를 변경해야 하기 때문에 많은 데이터가 존재한다면 이동 비용이 발생할 수 있다.

반면 연결 리스트는:

[10] → [20] → [30] → [40]

에서:

[10] → [20] → [25] → [30] → [40]

처럼 Node 사이의 연결을 변경하는 방식으로 삽입할 수 있다.

하지만 그렇다고 해서 연결 리스트가 배열보다 항상 좋은 것은 아니다.

오히려 특정 위치에 자주 접근하거나 데이터를 많이 조회하는 상황에서는 배열이 더 유리할 수 있다.

---

9. 연결 리스트의 단점

연결 리스트에는 분명한 단점도 존재한다.

9-1. 인덱스로 빠르게 접근할 수 없다

배열:

Array[100]

은 O(1)에 접근할 수 있다.

연결 리스트에서 100번째 Node에 접근하려면 처음부터 하나씩 이동해야 하기 때문에:

O(N)

이 필요하다.

---

9-2. 포인터를 위한 추가 메모리가 필요하다

Node는 단순히 데이터만 저장하지 않는다.

[Data | Next]

처럼 다음 Node의 주소도 저장해야 한다.

이 때문에 데이터 외에 포인터를 저장하기 위한 추가 메모리가 필요하다.

이중 연결 리스트라면:

[Prev | Data | Next]

이므로 포인터가 두 개 필요하다.

---

9-3. 캐시 효율이 낮을 수 있다

배열은 데이터가 연속적으로 배치되는 특성 때문에 CPU 캐시를 활용하기 좋다.

[10][20][30][40][50]

처럼 데이터가 가까이 있기 때문이다.

반면 연결 리스트는 Node가 메모리 곳곳에 존재할 수 있다.

[10] ─────→ [20]

              ↓

         [30] ─────→ [40]

Node가 메모리상에서 떨어져 있을 수 있기 때문에 배열보다 캐시 효율이 떨어질 수 있다.

따라서 단순히 Big-O만 보고 자료구조의 성능을 판단하면 안 된다.

---

10. 단일 연결 리스트

지금까지 주로 살펴본 형태가 단일 연결 리스트이다.

구조는 다음과 같다.

[10] → [20] → [30] → nullptr

각 Node는 다음 Node만 알고 있다.

Node* Next;

따라서 앞으로 이동하는 것은 가능하다.

10 → 20 → 30

하지만 뒤로 이동할 수는 없다.

예를 들어 30에서 20으로 돌아가려면 30 자체가 20의 위치를 저장하고 있지 않기 때문에 처음부터 다시 탐색해야 할 수 있다.

장점

• 구조가 단순하다.
• Node 하나당 Next 포인터 하나만 필요하다.
• 이중 연결 리스트보다 메모리 사용량이 적다.

단점

• 뒤로 이동할 수 없다.
• 이전 Node를 알아야 하는 상황에서는 다시 탐색해야 할 수 있다.

---

11. 이중 연결 리스트

이중 연결 리스트(Doubly Linked List)는 각 Node가 이전 Node와 다음 Node를 모두 가리키는 구조이다.

nullptr ← [10] ⇄ [20] ⇄ [30] → nullptr

Node는 다음과 같이 만들 수 있다.

struct Node
{
    int Data;
    Node* Prev;
    Node* Next;
};

단일 연결 리스트에서는:

Node* Next;

만 존재했다.

하지만 이중 연결 리스트에서는:

Node* Prev;
Node* Next;

두 개의 포인터가 존재한다.

따라서 한 Node에서:

Prev ← Node → Next

와 같이 앞뒤 Node를 모두 알 수 있다.

예를 들어:

[10] ⇄ [20] ⇄ [30]

에서 20은:

Prev → 10
Next → 30

을 알고 있다.

따라서 앞으로도 이동할 수 있고:

10 → 20 → 30

뒤로도 이동할 수 있다.

30 → 20 → 10

장점

• 앞뒤 방향으로 이동할 수 있다.
• 특정 Node를 기준으로 앞뒤 연결을 관리하기 편하다.
• 삽입과 삭제를 구현하기 편리한 경우가 있다.

단점

• Prev와 Next 두 개의 포인터를 저장해야 한다.
• 단일 연결 리스트보다 메모리를 더 사용한다.
• 연결 관계를 변경할 때 관리해야 할 포인터가 더 많다.

---

12. 시간 복잡도에서 가장 중요한 부분

연결 리스트에서 가장 헷갈리기 쉬운 부분이다.

예를 들어:

10 → 20 → 30 → 40 → 50

에서 30을 삭제한다고 생각해보자.

30의 위치를 이미 알고 있는 경우

현재:

20 → 30 → 40

이라는 연결을:

20 → 40

으로 변경하면 된다.

따라서 삭제 자체는:

O(1)

이다.

하지만 30이라는 Node를 찾는 것부터 해야 한다면:

10 확인
 ↓
20 확인
 ↓
30 발견

이라는 탐색 과정이 필요하다.

탐색:

O(N)

삭제:

O(1)

따라서 전체 작업은:

O(N) + O(1) = O(N)

이 된다.

즉, 연결 리스트의 시간 복잡도를 이해할 때는 연산 자체의 복잡도와 해당 Node를 찾는 데 필요한 복잡도를 구분해야 한다.

---

13. 핵심 시간 복잡도 정리

배열

특정 위치 접근

O(1)

인덱스를 이용해 바로 접근할 수 있다.

탐색

O(N)

정렬되지 않은 배열에서 원하는 값을 찾으려면 하나씩 확인해야 할 수 있다.

중간 삽입

O(N)

뒤쪽 데이터를 이동해야 할 수 있다.

중간 삭제

O(N)

삭제한 공간을 채우기 위해 뒤쪽 데이터를 이동해야 할 수 있다.

---

단일 연결 리스트

특정 위치 접근

O(N)

처음부터 Node를 따라가야 한다.

탐색

O(N)

Node를 하나씩 확인해야 한다.

삽입

O(1)*

삭제

O(1)*

여기서 *는 해당 위치의 Node를 이미 알고 있는 경우이다.

---

14. 연결 리스트를 공부하며 얻어야 하는 핵심 개념

연결 리스트를 단순히 코드로 구현할 수 있는 것보다 중요한 것은 자료구조를 선택하는 이유를 이해하는 것이다.

배열은:

빠른 접근

이 강점이다.

연결 리스트는:

Node의 연결을 이용한 효율적인 삽입/삭제

가 강점이다.

하지만 연결 리스트의 삽입/삭제가 무조건 빠른 것은 아니다.

Node 찾기
→ O(N)

찾은 Node에서 삽입/삭제
→ O(1)

이므로 실제 상황에서는 전체 작업이 O(N)이 될 수도 있다.

따라서 자료구조를 선택할 때는 단순히:

"연결 리스트는 삽입이 O(1)이니까 배열보다 좋다."

라고 판단하면 안 된다.

어떤 연산을 자주 수행하는지에 따라 적절한 자료구조가 달라진다.

---

15. 최종 정리

연결 리스트의 기본 구조는:

Head
 ↓
[Data | Next] → [Data | Next] → [Data | Next]
                                      ↓
                                   nullptr
                                      ↑
                                     Tail

단일 연결 리스트는:

Node → Node → Node

형태로 다음 Node만 가리킨다.

이중 연결 리스트는:

Node ⇄ Node ⇄ Node

형태로 이전 Node와 다음 Node를 모두 가리킨다.

핵심 시간 복잡도는 다음과 같다.

연산배열연결 리스트

특정 위치 접근	O(1)	O(N)
탐색	O(N)	O(N)
중간 삽입	O(N)	O(1)*
중간 삭제	O(N)	O(1)*

* 연결할 위치의 Node를 이미 알고 있는 경우.

결국 이번 단원에서 가장 중요하게 기억할 내용은 다음과 같다.

배열은 빠른 접근에 유리하고, 연결 리스트는 Node의 연결을 이용한 삽입과 삭제에 유리하다.

그리고 연결 리스트를 이해하기 위해서는 다음 네 가지를 확실하게 이해해야 한다.

1. Node
2. Head / Tail
3. Node와 Node를 연결하는 포인터
4. 배열과 연결 리스트의 시간 복잡도 차이