더블 링크드리스트

Head, Tail은 struct node형이 struct node* 형보다 더 좋다. 이유는 삭제 코드의 예외 상황(노드가 한 개인 경우)이 없어지기 때문이다.

초기화 시 head.next = &tail, tail.prev = &head; 를 하면, 추가 코드의 예외 상황(노드가 없는 경우)이 없어진다.

다음 코드는 head의 next가 가장 최근에 추가된 노드 구조(tail이 없을 때 추가 O(1))의 링크드리스트 구현이다. 

struct node{
	... // data
    struct node* prev;
    struct node* next;
}
struct node head, tail;

void init(){
    head.next = &tail;
    tail.prev = &head;
}

void add(struct node* p){
    p->next = head.next;
    head.next->prev = p; // tail이 없는 경우 if(head.next) 필요
    head.next = p;
    p->prev = &head;
}
void delete(struct node* p){
    p->next->prev = p->prev; // tail이 없는 경우 if(p.next) 필요
    p->prev->next = p->next;
}