1. 정의
- 데이터와 포인트로 구성된 노드 간의 연결을 이용해서 리스트를 구현한 자료구조
- 배열의 고정크기 단점을 보완하기 위해 만들어짐.
Head 는 리스트의 처음을 나타냄.노드는 데이터와 다음 노드를 가리키는 Next 포인터로 구성됨.- 각 노드는 next 포인터를 사용하여 다음 노드와 연결됨.
- 마지막 노드는
null을 가리켜 리스트의 끝을 나타냄.
2. 연결리스트의 시간 복잡도
| operation |
worst time |
| insert |
O(1) |
| delete |
O(1) |
| search |
O(n) |
| read |
O(n) |
| operation |
worst time |
| space |
O(n) |
| 시작/끝 위치 삽입/삭제 |
O(1) |
| 중간 위치 삽입/삭제 |
search time + O(1) |
3. 특징
- 노드의 next부분에 다음 노드의 위치를 저장함으로써 선형적 데이터 자료구조를 가짐.
- 연결되어있는 구조이기 때문에 특정 위치의 데이터를 탐색하기 위해서는 첫 노드부터 탐색을 시작하여 순차 접근만 가능.
- 주소만 연결하면 되기 때문에 삽입 삭제가 배열에 비해 빠르고 쉬움.
- 불연속적 단위로 저장되기 때문에 조회에 불리하며 포인터로 인해 추가 저장공간이 필요함.
4. 장점