연결 리스트를 제대로 이해하려면 먼저 C 언어에서 배열의 단점과 포인터의 장점을 알아두는 것이 좋습니다. 이 두 가지 개념이 연결 리스트가 탄생한 배경이기 때문입니다.
배열의 단점
- 배열은 정적 메모리 할당(static memory allocation) 방식을 사용합니다.
- 선언 시 크기를 미리 정해야 하므로 실제 사용량보다 많이 선언하면 메모리 낭비가 발생합니다.
- 반대로 필요한 크기보다 작게 선언하면 메모리 부족 문제가 생기며, 실행 중에 크기를 늘릴 수 없습니다.
포인터의 장점
- 포인터를 활용하면 동적 메모리 할당(dynamic memory allocation)이 가능합니다.
- 필요한 만큼만 메모리를 확보하고 해제할 수 있어 메모리를 효율적으로 사용할 수 있습니다.
연결 리스트(Linked List)란?
연결 리스트는 동적 메모리 할당을 기반으로 하는 자료구조로, 데이터의 개수에 따라 크기가 자유롭게 늘어나고 줄어듭니다. 연결 리스트는 여러 개의 노드(node)가 모인 집합으로 정의되며, 각 노드는 두 부분으로 구성됩니다.
- 데이터(Data): 실제 저장하고자 하는 값
- 링크(Link): 다음 노드를 가리키는 포인터
즉, 각 노드는 데이터와 링크로 이루어져 있고, 링크를 통해 다음 노드와 연결되어 사슬처럼 이어진 구조를 형성합니다.
연결 리스트의 종류
연결 리스트는 크게 네 가지 유형으로 나눌 수 있습니다.
- 단일 연결 리스트(Single / Singly Linked List)
- 이중 연결 리스트(Double / Doubly Linked List)
- 원형 단일 연결 리스트(Circular Single Linked List)
- 원형 이중 연결 리스트(Circular Double Linked List)
1. 단일 연결 리스트(Singly Linked List)
단일 연결 리스트의 노드는 다음 두 부분으로 구성됩니다.
- 데이터(Data)
- 링크(Link)
링크 필드는 항상 리스트상의 다음 노드를 가리킵니다. 그리고 마지막 노드의 링크 필드는 다음 노드가 없으므로 NULL을 저장합니다. 한 방향으로만 순회할 수 있는 가장 기본적인 연결 리스트 형태입니다.
2. 이중 연결 리스트(Doubly Linked List)
이중 연결 리스트의 노드는 세 부분으로 구성됩니다.
- 데이터(Data)
- 왼쪽 링크(Left Link)
- 오른쪽 링크(Right Link)
왼쪽 링크는 항상 리스트에서 왼쪽(앞) 노드를 가리키고, 오른쪽 링크는 오른쪽(뒤) 노드를 가리킵니다. 첫 번째 노드의 왼쪽 링크와 마지막 노드의 오른쪽 링크는 반드시 NULL이 됩니다. 양방향 순회가 가능해 삽입·삭제 시 이전 노드를 쉽게 참조할 수 있다는 장점이 있습니다.
3. 원형 단일 연결 리스트(Circular Single Linked List)
원형 단일 연결 리스트의 노드는 두 부분으로 구성됩니다.
- 데이터(Data)
- 링크(Link)
링크 필드는 항상 리스트상의 다음 노드를 가리킨다는 점은 단일 연결 리스트와 같지만, 마지막 노드의 링크가 NULL이 아니라 첫 번째 노드를 가리킨다는 점이 다릅니다. 이러한 원형 구조 덕분에 리스트의 끝에 도달해도 처음으로 돌아가 계속 순회할 수 있습니다.
4. 원형 이중 연결 리스트(Circular Double Linked List)
원형 이중 연결 리스트의 노드는 세 부분으로 구성됩니다.
- 데이터(Data)
- 왼쪽 링크(Left Link)
- 오른쪽 링크(Right Link)
왼쪽 링크는 항상 왼쪽 노드를, 오른쪽 링크는 오른쪽 노드를 가리킵니다. 원형 구조의 특징상 첫 번째 노드의 왼쪽 링크는 마지막 노드를 가리키고, 마지막 노드의 오른쪽 링크는 첫 번째 노드를 가리킵니다. 따라서 어느 노드에서 시작하더라도 양방향으로 무한히 순환할 수 있습니다.
정리
배열은 정적 할당으로 인해 메모리 낭비나 부족 문제가 발생할 수 있지만, 포인터 기반의 연결 리스트는 동적 메모리 할당을 통해 효율적인 메모리 관리를 가능하게 합니다. 상황에 따라 단일, 이중, 원형 등 네 가지 연결 리스트 중 적합한 구조를 선택하면 되며, 순회 방향과 삽입· 삭제 빈도를 고려해 자료구조를 설계하는 것이 중요합니다.