단순연결 리스트
동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료구조.
연결리스트의 장점
1. 삽입이나 삭제 시, 항목들의 이동이 필요없다
2. 배열의 경우, 최초 배열의 크기를 예측해 선언해야 하므로 대부분의 경우
빈공간이 남는 반면, 빈공간이 존재하지 않음
(단, 항목을 접근/탐색하려면 항상 첫노드부터 원하는 노드를 찾을 때까지 차례로 방문하는 순차탐색을 해야만 한다.)
이중연결 리스트
각 노드가 두개의 레퍼런스를 가지고 각각 이전노드와 다음노드를 가리키는 연결리스트
역방향 탐색 가능. 노드마다 추가로 1개의 레퍼런스를 저장해야 함.
원형연결 리스트
마지막 노드가 첫 노드와 연결된 단순연결리스트.
마지막 노드의 레퍼런스가 저장된 last가 단순 연결리스트의 head와 유사한 역할을 한다.
=>마지막노드와 첫노드를 O(1)시간에 접근할 수 있는 장점
시간복잡도 비교
| 종류 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 1차원 배열 | O(1) | O(n) | O(n) | O(n) |
| 단순연결리스트 | O(n) | O(n) | O(1) | O(1) |
| 이중연결리스트 | O(n) | O(n) | O(1) | O(1) |
| 원형연결리스트 | O(n) | O(n) | O(1) | O(1) |
Recording...