Linked List
- Node라는 구조체로 이루어져 있는데, Node는 데이터 값과 다음 Node의 address를 저장
- 물리적인 메모리상에서는 비연속적으로 저장이 되지만 Node가 next Node의 address를 가리킴으로써 논리적인 연속성을 가진 자료구조
논리적 연속성
- 각 Node들은 next address 정보를 가지고 있기 때문에 논리적으로 연속성을 유지하면서 연결
- Array의 경우 연속성을 유지하기 위해 물리적 메모리 상에서 순차적으로 저장하는 방법을 사용
- Linked list에는 메모리에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이 좀 더 자유로운 대신, Next address를 추가적으로 저장해야 하기 때문에 데이터 하나당 차지하는 메모리가 더 큼
논리적 연속성
물리적 불 연속성
시간 복잡도
| Linked list | |
|---|---|
| access | O(n) |
| search | O(n) |
| insertion | O(1) |
| deletion | O(1) |
