더블링크드리스트

1. 정의

• 노드와 노드가 서로 연결되어 있는 자료구조로, 링크드 리스트와 다르게 이전, 다음 노드의 레퍼런스를 포함하여 구성.
• 장점: 양방향 탐색 가능

2, 파이썬 더블 링크드 리스트 구현 예시

• 예시
  

3. 추가연산

• 예시
  

4. 삽입연산

• 구현내용
  

• 예시
  
• 맨 앞에 삽입 예시
  

시간복잡도

[접근&탐색]

접근 및 탐색 시 head 노드부터 하나씩 다음 노드로 이동하면서 원하는 위치에 있거나 데이터를 갖는 노드를 찾는다. => O(n) 소요

[삽입&삭제]

삽입 연산은 특정 노드가 주어졌을 때 그 다음 위치에 새로운 노드를 삽입. 총 리스트 길이와 상관없이 항상 일정하게 노드를 삽입 할 수 있다 => O(1)