Special Effects FX 스스로를 감동시켜야 최선을 다 한 것이다.

데이터를 저장할 때, 리스트의 머리와 꼬리에 각각 더미 노드가 존재하기 때문에 추가의 방법에 있어서 경우의 수가 나뉘지 않는다.

새 노드를 추가할 때의 과정

1. 새 노드를 생성하고 데이터를 저장

2. 새 노드와 새 노드의 왼쪽에 위치할 노드가 서로를 가리키게 한다.

3. 새 노드와 새 노드의 오른쪽에 위치할 노드가 서로를 가리키게 한다.

즉, 이렇게 된다.

               head                                                       tail

                 ↓                                                          ↓

NULL <-  dummy  ->  <-  data1 ->  <-  data2  ->  <-  dummy ->  NULL

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

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

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

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

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

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

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