List 간단 정의 성질 및 종류

list : 노드형 시퀀스 컨테이너

연결 리스트의 성질

1. K번째 원소를 확인/변경하기 위해 O(k)가 필요함
2. 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1)
3. 원소들이 메모리 상에 연속해있지 않아  Cache hit rate가 낮지만 할당이 다소 쉬움

---

연결 리스트 종류

1. 단일 연결 리스트(Singly Linked List)

2. 이중 연결 리스트(Doubly Linked List)

3. 원형 연결 리스트(Circular Linked List)

---

배열 vs 리스트

	배열	리스트
k번째 원소의 접근	O(1)	O(k)
임의 위치에 원소 추가 / 제거	O(N)	O(1)
메모리 상의 배치	연속	불연속
추가적으로  필요한 공간 (Overhead)	-	O(N)