연결 리스트의 변형
연결 리스트는 다양한 형태로의 변형으로 발전되었다.
| 연결 리스트 | 영문명칭 | 설명 |
|---|---|---|
| 단순 연결 리스트 | singly linked list | - 각각의 노드별로 링크(포인터) 부분이 하나만 있고 - 각각의 후행 노드만을 가리키는 - 단순한 연결 리스트 구조. |
| 이중 연결 리스트 | doubly linked list | - 노드는 링크 두개를 가지며 - 각각은 선행 노드를 가리키는 링크와 후행 노드를 가리키는 링크로 구성됨 |
| (단순) 원형 연결 리스트 | circular linked list | - 마지막 노드의 링크를 NULL 대신 특정 노드에 대한 링크를 가지게 함 - 통상적으로 마지막 노드의 링크가 가리키는 건 첫 노드 |
| 원형 이중 연결 리스트 | doubly circular linked list | - 이중 연결 리스트와 원형 연결 리스트의 결합 형태 |
단순 연결 리스트의 한계와 변형 연결 리스트의 등장
단순 연결 리스트는 여러 한계를 가지고 있고, 그런 단점들을 보완하고 하고 효율적인 프로그래밍이 가능케 하기 위해 여러 가지 연결 리스트의 변형이 생겨나게 되었다.
| 한계(단점) | 설명 | 변형 |
|---|---|---|
| 역방향 탐색 불가 | - 선행 노드에서 후행 노드는 쉽게 접근 가능 - 후행 노드에서 선행 노드는 접근 어려움 |
> 이중 연결 리스트 |
| 무한 및 순환구조 구현 불가 | - 끝을 알 수 없는 데이터 구조나 순환 데이터 구조 처리 불가 - 마지막에 등장하는 NULL 부분을 충분히 활용하지 못함 |
> 원형 연결 리스트 |
원형 연결 리스트
원형 연결 리스트의 개념
- 단순 연결 리스트의 마지막 노드의 링크를 첫 노드로 연결시킨 구조
- 한 방향으로 모든 노드가 원형으로 연결된 구조.
- NULL 값을 갖는 마지막 노드의 링크 부분을 활용하면서도, 프로그램의 성능에 도움을 주기 위해 제안됨.
- 한 노드로부터 다른 어떤 노드로도 접근이 가능한 구조.
이중 연결 리스트
특정 노드에서는 선행 노드와 후행 노드에 대해 간단한 프로그램 코드를 통해 접근할 수 있는 구조.
이중 연결 리스트의 개념
- 연결 리스트의 각 노드가 두 개의 링크 부분을 가짐
- 두 개의 링크 중 하나는 기존과 같이 후행 노드를 가리키며
- 나머지 하나의 노드는 선행 링크를 가리킴
- 이로써 기존 단순 연결 리스트에서 “선행 노드”로의 연결이 어렵던 점을 극복