Double Linked List

struct Node

typedef struct Node{
	int v;
	struct Node *next;
	struct Node *prev;
}Node;
Double Linked List

struct DoubleLinkedList

typedef struct DoubleLinkedList{
	Node *head, *tail;
}DoubleLinkedList;
Double Linked List

function DoubleLinkedList

void initial(DoubleLinkedList *l){
	l->head = NULL;
	l->tail = NULL;
}
Double Linked List

function isEmpty

bool isEmpty(const DoubleLinkedList *l){
	//return l->head == NULL;
	return l->tail == NULL;
}	
Double Linked List

function getNode

Node* getNode(int v){
	Node *p = (Node*)malloc(sizeof(Node));
	if (p == NULL){
		exit(0);
	}
	p->v = v;
	p->next = NULL;
	p->prev = NULL;
	return p;
}	
Double Linked List

addTail

void addTail(DoubleLinkedList *l, Node* p){
	if (isEmpty(l)){
		l->head = l->tail = p;
	}else{
		l->tail->next = p;
		p->prev = l->tail;
		l->tail = p;
	}
}	
Double Linked List

function insertTail

void insertTail(DoubleLinkedList *l, int v){
	Node *p = getNode(v);
	addTail(l, p);
}
Double Linked List

addHead

void addHead(DoubleLinkedList *l, Node *p){
	if (isEmpty(l)){
		l->head = l->tail = p;
	}else{
		p->next = l->head;
		l->head->prev = p;
		l->head = p;
	}
}	
Double Linked List

function insertHead

void insertHead(DoubleLinkedList *l, int v){
	Node *p = getNode(v);
	addHead(l, p);
}
Double Linked List

function traverse

void traverse(const DoubleLinkedList *l){
	Node* p = l -> head;
	while(p != NULL){
		printf("%d ", p -> v);
		p = p -> next;
	}
	printf("\n");
}
Double Linked List

function removeHead

Node* removeHead(DoubleLinkedList *l){
	if (isEmpty(l)){
		return NULL;
	}
	Node* saved = l->head;
	l->head = saved->next;
	l->head->prev = NULL;
	if (saved == l->tail){
		l->tail = NULL;
	}
	return saved;
}
Double Linked List

function removeTail

Node* removeTail(DoubleLinkedList *l){
	if (isEmpty(l)){
		return NULL;
	}
	Node *saved = l->tail;
	l->tail = saved->prev;
	l->tail->next = NULL;
	if (saved == l->head){
		l->head = NULL;
	}
	return saved;
}
Double Linked List

addHead