[선형] Doubly-Linked List

❒ Description

---

이중 연결 리스트(Doubly-Linked List )에 대해서 알아보자.

 

 

 

❒ Doubly-Linked List 

---

실제 자바에서 제공하는 util 패키지의 LinkedList는 DL-List랑 같은 형식으로 되어있다. Singly LinkedList와의

차이라면 단일 연결리스트는 노드에 데이터와 다음 노드를 가리키는 노드 변수만을 갖고 있었다면 DL-List는

하나 더 추가되어 '이전 노드'를 가리키는 변수가 추가 된다. Singly LinkedList에 비해 검색(색인)능력이 좋아진다.

 

단방향으로 연결 된 Singly LinkedList의 경우 반드시 head부터 시작하여 탐색하였다. 만약 10개의 노드가 있고,

9번 째 노드를 탐색하려고 한다면, head부터 탐색했어야 했다.

하지만, Doubly LinkedList의 경우는 Previous Node 변수, 즉 이전 노드를 가리키는 변수를 갖고 있기 때문에

tail부터 탐색할 수 있어 찾으려는 노드가 tail에 가깝다면 tail부터, head에 가깝다면 head부터 탐색하면 되기 때문에

좀 더 효율적인 탐색이 가능하다.