양방향 연결 리스트

'양방향 연결 리스트(doubly linked list)' 또는 '이중 연결 리스트' 라고도 불리는 이 자료구조는 그 이름이 의미하듯이 노드가 양쪽 방향으로 연결된 구조의 리스트이다.

즉, 왼쪽 노드가 오른쪽 노드를 가리킴과 동시에 오른쪽 노드도 왼쪽 노드를 가리키는 구조이다.

ex) data1-> <-data2 -> <-data3

더미 노드 양방향 연걸리스트도 있고, 원형 연결 기반의 양방향 연결 리스트 등등도 있다.

밑에 나오는 예제는 기본적인 양방향 연결 리스트이다.

서로 봐라보는 것이라 복잡하게 느껴진다. 하지만 실제로 코드를 비교해 보면 상대적으로 더 복잡하지 않음을 알 수 있다. 

양쪽 방향으로 이동할 수 있기 때문에 단방향 연결 리스트에서는 어렵게 구현했던 것이 쉽게 구현되기도 한다. 때문에 오히려 단순하게 느껴지는 측면도 있다.