[List] 이중 연결 리스트, Doubly Linked List

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

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

• 각 노드가 앞과 뒤를 가리키는 두 개의 레퍼런스를 가지는 연결 리스트
• 단순 연결 리스트는 삽입과 삭제 연산 시 반드시 이전 노드를 가리키는 레퍼런스를 추가로 알아내야 하고, 역방향으로 탐색이 불가능함
• 이중 연결 리스트는 이러한 단순 연결 리스트의 단점을 보완하지만 각 노드마다 추가로 한 개의 레퍼런스를 저장해야 한다는 공간적인 단점을 가짐
• 맨 앞의 노드는 Header, 맨 마지막의 노드는 Trailer라 칭함

 

- 연산

• 탐색 : 타겟을 매개변수로 받아 탐색에 성공할 때까지 순차적으로 탐색, 실패할 경우 None 반환
• 삽입
  • Insert front & last
  • Insert before & after
• 삭제
  • Delete front & last
  • Delete before & after

 

- 수행 시간

• 탐색은 연결 리스트의 노드들을 Header 또는 Trailer부터 순차적으로 방문해야 하므로 O(n) 소요
• 삽입과 삭제는 각각 O(1) 개의 레퍼런스만을 갱신하므로 O(1) 소요 (단, Insert before & after나 Delete before & after의 경우에 특정 노드의 레퍼런스가 주어지지 않으면 Header 또는 Trailer로부터 노드를 찾기 위하여 탐색을 수행하므로 O(n) 소요)