이중 링크드 리스트 [doubly linked list]

정의

- 양방향 연결 리스트

- Data 와 Next pointer, Prev Pointer 로 구성

헤더와 꼬리가 초기에 주어진다는 점은 단순연결 리스트와 동일

초기화는

헤더는 의 prev 는 자기자신 이고 next 는 테일을 가르킨다

테일에서는 next 가 자기자신을 가르키고 prev 가 헤드를 가르키도록 한다

각 노드에는 데이터를 답을 수 있는 templte< typename T > 인 T 로 정의 한다

Tip : insert 시 기준이 되는 노드와 멀리떨어져 있는 노드와 새로운 노드와의 연결을 먼저 연결한다

because 기준이 되는 노드와 새로운 노드를 먼저 연결하면 기존에 연결 되어 있던 노드의 포인터를 잃어버리기 때문

1. 삽입

이전 삽입 :

define void* POS

- 다음삽입( Insert Next) 도 InsertBefore 와 유사하게 마들어 질 수 있다

*삭제

이중리스트는 양쪽의 포인터 정보를 알기 때문에 자기 자신을 지울 수 있다

삭제할 노드의 양쪽 노드들이 삭제 할 노드를 가르키지 않고 기준 노드의 양쪽노드들을 서로가 가르키게 한다

그런 후 삭제기준 노드를 삭제