[Dummy Node를 이용] 양방향 연결 리스트

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

새 노드를 추가할 때의 과정

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

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

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

즉, 이렇게 된다.

               head                                                       tail

                 ↓                                                          ↓

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