Double LinkedList

List 의 종류 (3가지)

• ArrayList
• LinkedList
  • Single LinkedList
  • Double LinkedList

Double LinkedList 만의 특징

1. single 방식과 달리 double 은 Node 에 Preview point 가 있다. 각 Node가 서로를 가리키고 있다.

 

각 노드가 preview point , next point 모두 가지고 있음

 

 

2. Dummy Head, Dummy tail 노드를 가지고 있다.

 

---

 

- Double LinkedList 의 처음 생성 모습 (Head 와 Tail 만 존재한다)

 

 

 

실제로 데이터가 들어오게 되면 아래와 같은 모양이다.

 

 

---

Double LinkedList 의 시간복잡도

추가 : add : O(1)

Single 방식에서는 맨 끝에 데이터를 추가하기 위해서는 N번 만큼 이동한 뒤에 데이터를 추가 했어야 했다.

하지만, Double LinkedList 첫 생성과 동시에 Dummy Tail 노드를 만들었엇고, 해당 Dummy Tail 노드의 메모리 주소값을 가지고 있으면, 단번에{O(1)} Double LinkedList 끝 부분(Tail)으로 이동할 수 있다.

(Double LinkedList 에서는 Head 와 Tail 모두의 메모리 주소값을 가지고 있다.)

이동 후에 Tail의 preview point 에 새로운 데이터를 추가한다.

 

 

검색 : get(index) : O(N)

Dummy tail 노드에 주목.

Single LinkedList 에서는 Head 메모리 주소값만 가지고 있지만,

Double LinkedList 에서는 Head 와 Tail 모두의 메모리 주소값을 가지고 있다.

그래서 리스트를 반으로 나눠서 양 사이드에서 가까운 쪽으로 접근하여 데이터를 검색한다.

 

이로써 N/2[O(N/2)] 로 검색하지만 /2 역시 N이 무한대에 접근할때, 상수항은 무의미 해 지므로 ⇒ O(N) 시간복잡도를 갖는다.

 

삽입 : insert(index) : O(N)

Head 와 Tail 중에서 가까운 쪽에서 부터 출발 하여 O(N/2), 인덱스(curr)를 찾는다. ⇒ O(N)

• (맨 앞이나 맨 뒤에 원소를 삭제 하거나 삽입 한다면 O(1)의 시간 복잡도를 갖는다.)

 

 

새로운 노드를 생성하고, curr 의 preview point 연결 부분을 해제 한다.

 

 

새로 새로 생된된 노드와 각각 연결을 지어준다.

 

 

완성

 

 

삭제 : delete(index) : O(N)

Head 와 Tail 중에서 가까운 쪽에서 부터 출발 하여 O(N/2), 인덱스를 찾는다. ⇒ O(N)

 

 

curr의 앞뒤 부분 연결을 해제하고 prev 와 next 를 연결 한다.