연결 리스트.md

From 바킹독 사이트

• 연결 리스트의 성질

  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) (주소값)

  • 둘다 선형 자료구조

• 연결 리스트가 쓰이는 대표적인 상황 - text editor

  • 임의의 위치에 원소를 추가/제거를 많이 하는 경우에 연결 리스트를 사용!

• STL list

  • Doubly Linked List 구조를 가지고 있음!