[자료구조] 연결 리스트 (Linked list)
연결 리스트는 데이터와 포인트로 구성된 노드 간의 연결(link)을 이용해서 리스트를 구현한 자료구조입니다.
연결 리스트는 배열의 고정크기의 단점을 보완하기 위해 만들어졌으며 배열과 달리 연속적인 메모리 공간에 저장되어 있지 않기 때문에 연결이 필요합니다.
연결 리스트 표현
연결 리스트는 아래 그림과 같이 포인터를 사용하여 각 노드를 연결합니다.
그림에서 알 수 있는 사실은 아래와 같습니다.
Head는 리스트의 처음을 나타냅니다.노드는데이터와 다음 노드를 가리키는Next 포인터로 구성돼 있습니다.- 각 노드는 next 포인터를 사용하여 다음 노드와 연결됩니다.
- 마지막 노드는
null을 가리켜 리스트의 끝을 나타냅니다.
시간 복잡도(Time complexity)
| operation | time |
| 시작 위치에 대한 삽입/삭제 | Θ(1) |
| 마지막 위치에 대한 삽입/삭제 | Θ(1) ; 마지막 요소 위치를 아는 경우 Θ(n) ; 마지막 요소 위치를 모르는 경우 |
| 중간 위치에 대한 삽입/삭제 | search time + Θ(1) |
| 인덱싱 | Θ(n) |
| 공간 낭비 | Θ(n) |
특징
- 노드의 next부분에 다음 노드의 위치를 저장함으로써 선형적 데이터 자료구조를 가집니다.
- 연결되어있는 구조이기 때문에 특정 위치의 데이터를 탐색하기 위해서는 첫 노드부터 탐색을 시작하여 순차 접근만 가능합니다.
- 주소만 연결하면 되기 때문에 삽입 삭제가 배열에 비해 빠르고 쉽습니다.
- 불연속적 단위로 저장되기 때문에 조회에 불리하며 포인터로 인해 추가 저장공간이 필요합니다.
장점
- 크기가 가변적임
- 메모리가 허용하는 만큼 커질 수 있음
- 삽입 삭제가 쉬움
- 삽입 삭제 시에 데이터 이동이 필요 없음
단점
- 래덤액세스가 불가능함 요소에 접근하려면 첫 번째 노드부터 순차적으로 접근해야 함.
- 포인터를 위한 추가 메모리 공간이 필요함.
연결 리스트의 구분
연결 리스트는 연결 방향에 따라 단일 연결 리스트, 연결 리스트, 이중 연결 리스트, 환형 연결 리스트가 있습니다.
단순 연결 리스트 (Singly Linked Linear List)
단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킵니다.
이중 연결 리스트 (Doubly Linked Linear List)
이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킵니다.
원형 연결 리스트 (Circularly Linked Linear List)
원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조입니다.
