CS학습
연결 리스트 Linked List: 노드 기반의 비연속적 자료 구조
연결 리스트는 데이터를 메모리의 연속적인 공간이 아닌, 각 노드가 데이터와 다음 노드를 가리키는 포인터로 구성된 선형 자료구조이다. 배열과 달리 삽입/삭제 연산에서 메모리 이동 비용을 줄일 수 있지만, 특정 요소에 접근하는 데에는 더 많은 시간이 소요될 수 있다. 이 글에서는 연결 리스트의 개념, 원리, 구현 방법 및 실제 활용 사례를 자세히 살펴본다.
송민성3분 읽기
1. 개념
연결 리스트(Linked List)는 데이터를 노드(Node)라는 단위로 저장하는 선형 자료구조이다. 각 노드는 실제 데이터와 다음 노드를 가리키는 포인터(Pointer) 또는 참조(Reference)를 포함한다. 배열과는 달리 메모리에 연속적으로 저장될 필요가 없으며, 유연하게 크기를 조절할 수 있다는 특징이 있다.
2. 왜 사용하는가
- 동적 크기 조정: 배열은 크기를 미리 정해야 하지만, 연결 리스트는 필요한 만큼 노드를 추가하거나 제거하여 동적으로 크기를 조정할 수 있다.
- 삽입/삭제 효율성: 특정 위치에 데이터를 삽입하거나 삭제하는 연산이 배열보다 효율적이다. 배열의 경우, 삽입/삭제 시 뒤쪽 요소들을 모두 이동시켜야 하지만 연결 리스트는 포인터만 변경하면 되기 때문이다. (단, 특정 노드를 찾는데 시간이 더 걸릴 수 있다.)
- 메모리 활용: 필요한 만큼만 메모리를 할당하므로 메모리 낭비를 줄일 수 있다.
3. 동작 원리
연결 리스트는 크게 세 가지 유형으로 나뉜다:
- 단일 연결 리스트(Singly Linked List): 각 노드가 다음 노드만을 가리키는 가장 기본적인 형태이다.
- 이중 연결 리스트(Doubly Linked List): 각 노드가 이전 노드와 다음 노드를 모두 가리킨다. 삭제 연산 시 이전 노드에 대한 정보가 있어 편리하다.
- 원형 연결 리스트(Circular Linked List): 마지막 노드가 첫 번째 노드를 가리키는 형태로, 순환적인 구조를 갖는다.
4. 코드 예제
python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def print_list(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# 사용 예시
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.print_list() # 출력: 1 -> 2 -> 3 -> None5. 시간 복잡도 또는 성능 특성
| 연산 | 시간 복잡도 | | ---------- | --------- | | 삽입 (head) | O(1) | | 삽입 (tail) | O(n) | | 삭제 (head) | O(1) | | 삭제 (node) | O(n) | | 탐색 | O(n) |
- 삽입/삭제: head 노드에 대한 연산은 O(1)의 시간 복잡도를 갖지만, 특정 위치나 값을 기준으로 삽입/삭제하는 경우에는 O(n)이 소요될 수 있다.
- 탐색: 배열처럼 인덱스를 통한 직접 접근이 불가능하므로, 탐색 시 연결 리스트를 순회해야 하며, 최악의 경우 O(n)의 시간 복잡도를 갖는다.
6. 실무 사용 사례
- 스택(Stack), 큐(Queue): 연결 리스트는 스택과 큐와 같은 추상 데이터 자료구조를 구현하는 데 유용하게 활용될 수 있다.
- 해시 테이블: 충돌 해결을 위한 Chaining 방식에서 연결 리스트를 사용할 수 있다.
- 메모리 관리: 동적 메모리 할당 및 해제에 사용되는 자유 목록(Free List) 구현에 적용할 수 있다.
7. 주의할 점
- 포인터 관리: 포인터를 잘못 다루면 메모리 누수(Memory Leak) 또는 프로그램 오류가 발생할 수 있으므로, 신중하게 관리해야 한다.
- 순환 참조: 연결 리스트의 노드가 순환적으로 자신을 가리키는 경우 무한 루프에 빠질 수 있다.
8. 핵심 정리
연결 리스트는 유연한 크기 조정과 효율적인 삽입/삭제 연산을 제공하는 강력한 자료구조이다. 그러나 특정 요소에 접근하는 데에는 더 많은 시간이 소요될 수 있으므로, 사용 목적에 따라 적절한 자료구조를 선택해야 한다. 또한 포인터 관리에 주의하여 메모리 누수 및 프로그램 오류를 방지해야 한다.