[자료구조] Doubly Linked List

Doubly Linked List

Singly Linked List가 단방향 연결 리스트로, 다음 노드를 가리키는 포인터를 갖고있다면

Doubly Linked List는 양방향(이중) 연결 리스트로, 다음 노드와 이전 노드를 가리키는 포인터를 갖는 자료구조이다.

 

 

---

Java Collection Library 에서 사용가능한 LinkedList는 Doubly Linked List 이다

 

---

Singly Linked List와 비교했을 때 다음과 같은 장단점이 있다

 

장점

탐색이 비교적 빠르다

Singly Linked List는 다음노드의 포인터만을 갖고있어 노드 탐색 시 순방향으로 탐색만이 가능

Doubly Linked List는 이전노드의 포인터를 갖고있어 마지막 노드(tail)부터 역방향 탐색이 가능하다

 

단점

이전노드의 포인터를 추가적으로 저장하는만큼 메모리 사용이 추가됨

 

 

---

reference

https://st-lab.tistory.com/169?category=856997 

https://www.youtube.com/watch?v=SCdd9SzOk9Q