연결리스트

1. 연결리스트의 성질

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

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

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

 

2. 연결리스트의 종류

 

3. 배열 vs 연결 리스트 (선형리스트의 비교)

-> 연결리스트는 각각의 원소가 다음 위치 값을 지니고 있기 때문에 추가적으로 O(N)의 공간이 필요함

 

4. 연결리스트의 연산