[자료구조] 연결 리스트(Linked List)

연결 리스트(Linked List)란?

연결 리스트(Linked List)는 데이터를 저장하는 노드(Node)들이 포인터를 통해 연결된 자료구조입니다.

 

순차 자료구조인 배열(array)은 탐색 속도는 빠르지만, 삽입이나 삭제 연산 시 기존 원소를 옮겨야 하므로 시간이 더 소요됩니다. 이러한 단점을 보완하기 위해, 데이터를 저장하는 노드(Node)들이 포인터로 연결된 자료구조인 연결 리스트(Linked List)가 사용됩니다.

 

예를 들어

연결 리스트는 기차에 비유할 수 있습니다. A, B, C라는 칸이 있고 다음칸을 나타내는 번호표가 있다면 A칸 다음 번호표가 B칸이라면 A칸과 B칸은 연결됩니다. 그리고 B칸은 C칸을 C칸은 X라는 번호표라면 B칸은 C칸과 연결되고 C칸은 마지막 칸이 됩니다.

 

기차의 칸을 연결 리스트의 노드라고 생각하면 A, B, C는 노드의 데이터 필드가 되고, 각 칸이 가지고 있는 번호표는 링크 필드가 됩니다.

 

연결 리스트의 구성 요소는 다음과 같습니다.

1. 노드(Node)
   1. 데이터 필드 (Data) : 노드가 저장하는 값
   2. 링크 필드 (link) : 다음 노드의 주소를 저장하는 포인터
2. 헤드(Head)
   1. 연결 리스트의 시작을 가리키는 포인터
   2. 리스트의 첫 번째 노드의 주소를 저장

---

연결 리스트의 종류

단순 연결 리스트 (Singly Linked List)

단순 연결 리스트는 노드의 링크 필드가 하나이며, 링크 필드는 다음 노드와 연결되는 구조입니다.

 

단순 연결 리스트의 구조는 다음과 같습니다.

[데이터 | 다음 노드의 주소] -> [데이터 | 다음 노드의 주소] -> NULL

 

원형 연결 리스트 (Circular Linked List)

단순 연결 리스트에서 마지막 노드가 첫 번째 노드를 가리키게 해서 리스트 구조를 원형으로 만든 연결 리스트를 원형 연결 리스트라고 합니다.

 

원형 연결 리스트의 구조는 다음과 같습니다.

[데이터 | 다음] -> [데이터 | 다음] -> ... -> [데이터 | 첫 번째 노드 주소]

 

이중 연결 리스트 (Doubly Linked List)

단순 연결 리스트와 원형 연결 리스트는 이전 노드에 접근하기 어려운 문제가 있습니다. 이런 문제는 한 방향으로만 순회하도록 설계되었기 때문으로 이를 개선하여 양쪽 방향으로 순회할 수 있도록 노드를 연결한 것을 이중 연결 리스트라고 합니다.

 

이중 연결 리스트의 구조는 다음과 같습니다.

NULL <- [이전 | 데이터 | 다음] <-> [이전 | 데이터 | 다음] -> NULL

---

단순 연결 리스트 (Singly Linked List)

단순 연결 리스트의 삽입 연산

단순 연결 리스트에 노드를 삽입하는 방법을 정리하면 다음과 같습니다.

1. 삽입할 노드를 생성
2. 생성된 노드의 데이터 필드에 값을 저장
3. 생성된 노드의 링크 필드에 링크를 저장
4. 생성된 노드에 앞 노드를 연결

 

예를 들어 설명하면

A, B, C 단순 연결 리스트가 존재하고 A와 B사이에 D를 삽입하는 과정

[ A | 200 ] → [ B | 300 ] → [ C | null ] 기존 단순 연결 리스트가 있습니다.

1. 삽입할 노드 준비 : 삽입할 새 노드로 만들 공백 노드를 메모리에 할당 받습니다 [ null | null ]
2. 새 노드의 데이터 필드에 값을 저장 : 새 노드의 데이터 필드에 D를 저장합니다. [ D | null ]
3. 생성된 노드의 링크 필드에 링크를 저장 : 새 노드를 삽입할 자리에서 앞 노드 즉 A 노드의 링크 필드 값을 새 노드 링크 필드에 복사합니다. [ A | 200 ] → [ B | 300 ] → [ C | null ], [ D | 200 ]
4. 생성된 노드에 앞 노드를 연결 : 삽입할 자리의 앞 노드, 즉 A 노드의 링크 필드에 새 노드의 주소를 저장하여 A 노드가 새 노드로 연결되게 합니다. [ A | 400 ] → [ D | 200 ] → [ B | 300 ] → [ C | null ]

단순 연결 리스트의 삭제 연산

단순 연결 리스트에서 노드를 삭제하는 방법은 다음과 같습니다.

1. 삭제할 노드의 앞 노드를 찾는다.
2. 앞 노드 링크 필드에 삭제할 노드의 링크 필드 값을 저장한다.
3. 삭제할 노드의 앞 노드와 다음 노드를 연결한다.

 

예를 들어 설명하면

A, D, B, C 단순 연결 리스트가 존재하고 A와 B사이에 D를 삭제하는 과정

1. 삭제할 노드의 앞 노드를 찾기 : 삭제할 노드의 앞 노드인 노드 A를 찾습니다. [ A | 400 ] → [ D | 200 ] → [ B | 300 ] → [ C | null ]에서 [ A | 400 ]
2. 앞 노드 링크 필드에 삭제할 노드의 링크 필드 값을 저장 : 노드 A 링크 필드에 삭제할 노드 D의 링크 필드 값을 저장합니다. [ A | 200 ] → [ D | 200 ] → [ B | 300 ] → [ C | null ]
3. 삭제할 노드의 앞 노드와 다음 노드를 연결 : 삭제할 노드 D의 앞 노드 A와 삭제할 노드 D의 다음 노드 B를 연결합니다.  [ A | 200 ] → [ B | 300 ] → [ C | null ]

그림에서 삭제한 노드 D가 계속 노드 B에 연결되어 있지만 노드 D는 앞에 연결된 노드가 없기 때문에 논리적으로 제외됩니다. 즉 노드 D의 링크 필드에 null을 넣지 않아도 링크 필드가 의미 없는 상태입니다.

---

원형 연결 리스트(Circular Linked List)

원형 연결 리스트의 삽입 연산

1. 공백 리스트인 경우 : 리스트가 공백이면 삽입하는 새 노드가 리스트의 첫 번째이자 마지막 노드로 삽입됩니다. (새 노드의 주소를 링크 필드에 저장하여 새 노드의 링크가 자기 자신으로 연결되도록 합니다.)
2. 첫 번째 노드로 삽입하는 경우 : 원형 연결 리스트는 다음과 같이 첫 번째 노드에 삽입하는 연산을 수행합니다.
   1. 첫 번째 노드를 노드 순회의 시작점으로 지정
   2. 반복문을 수행하여 마지막 노드까지 이동
   3. 마지막 노드의 링크 필드에 새 노드의 주소를 저장, 즉 마지막 노드와 새 노드 연결
   4. 새 노드의 링크 필드값을 첫 번째 노드의 주소값으로 저장
3. 리스트 중간에 삽입하는 경우
   1. 삽입할 노드의 링크 필드값을 이전 노드 링크 필드값으로 저장, 즉 다음 노드 주소로 저장
   2. 이전 노드 링크 필드에 새 노드 주소를 저장, 즉 이전 노드와 새 노드 연결

 

예를 들어 설명하면

A, B, C 원형 연결 리스트가 존재하고 A와 B사이에 D를 삽입하는 과정

1. 첫 번째 노드를 노드 순회의 시작점으로 지정 : 노드 A를 순회 시작점으로 지정합니다.
2. 반복문을 수행하여 마지막 노드까지 이동 : 노드 A를 시작으로 노드 B, 노드 C로 이동합니다.
3. 마지막 노드의 링크 필드에 새 노드의 주소를 저장 : 마지막 노드 즉, 노드 C의 링크 필드에 새 노드 D의 주소값을 저장합니다.
4. 새 노드의 링크 필드값을 첫 번째 노드의 주소값으로 저장 : 새 노드 D의 링크 필드 값을 첫 번째 노드 A의 주소값으로 저장합니다.

 

중간 노드에  삽입 연산과 삭제 연산은 단순 연결 리스트와 동일하기 때문에 생략합니다.

---

이중 연결 리스트(Doubly Linked List)

이중 연결 리스트의 삽입 연산

1. 삽입할 새 노드 생성
2. (삽입 하려는 위치)이전 노드의 오른쪽 링크 필드(rlink)에 있던 값을 새 노드의 오른쪽 링크 필드(rlink)에 저장
3. 이전 노드의 오른쪽 링크 필드값(rlink)에 새 노드의 주소값을 저장
4. 다음 노드의 왼쪽 링크 필드(llink)에 있던 값을 새 노드의 왼쪽 링크 필드(llink)에 저장
5. 다음 노드의 오른쪽 링크 필드값(llink)에 새 노드의 주소를 저장

예를 들어 설명하면

A, B, C 이중 연결 리스트가 존재하고 A와 B사이에 D를 삽입하는 과정

1. 삽입할 새 노드 생성 : 노드 D를 생성합니다.
2. 새 노드와 이전 노드의 오른쪽 링크 필드 : 새 노드 D의 오른쪽 링크 필드에 이전 노드 A의 오른쪽 링크 필드값 200을 저장 후, 이전 노드 A의 오른쪽 링크 필드값에 새 노드 D의 주소값 400을 저장
3. 새노드와 다음 노드의 왼쪽 링크 필드 지정 : 새 노드 D의 오른쪽 링크 필드에 다음 노드 B의 왼쪽 링크 필드값 100을 저장 후, 다음 노드 B의 오른쪽 링크 필드 값에 새노드 D의 주소값 400을 저장

 

이중 연결 리스트의 삭제 연산

1. 삭제할 노드의 이전 노드와 다음 노드를 찾는다.
2. 삭제할 노드의 오른쪽 링크 필드값을 를 이전 노드의 오른쪽 링크 필드에 저장
3. 삭제할 노드의 왼쪽 링크 필드값을 다음 노드의 왼쪽 링크 필드에 저장
4. 노드를 순서대로 연결한다.

 

예를 들어 설명하면

A, D, B, C 이중 연결 리스트가 존재하고 D를 삭제하는 과정

1. 삭제할 노드 D의 이전 노드 A와 다음 노드 B를 찾습니다.
2. 삭제할 노드 D의 오른쪽 링크 필드값(200) 노드 A의 오른쪽 링크 필드에 저장합니다.
3. 삭제할 노드 D의 왼쪽 링크 필드값(100)을 노드 B의 왼쪽 링크 필드에 저장합니다.

---

연결 리스트 구현

GitHub

DataStructure/List at main · hosunghyun/DataStructure

---

최종 수정일 : 2025-01-18