연결 리스트

1. k번째 원소를 확인/변경하기 위해 O(k)가 필요함.

    ㄴ 연결 리스트의 구조상 어쩔수 없음. 무조건 k를 거쳐야 하기 떄문.

2. 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1).

3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움.

 

연결 리스트의 종류

 

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

 

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

 

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

 

 

배열 vs 연결 리스트

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

STL List는 이중 연결 리스트 (Doubly Linked List) 이다.