Double linked list is a chain of nodes, each node’s next pointer point to next object and previous pointer points to previous node, here it is graphically…

here is a c structure for double linked list’s node

struct Node { void* info; //data Node* next; //used to point to next node Node* prev; //used to point to previous node };

double linked list can be implemented using a special head node or without it. Special nodes act as header and tail, every time we perform an operation on list we give the special nodes. The disadvantage of using special nodes is extra space consumed by these nodes. Without special nodes, whenever we perform operations double linked list, we should be bit more careful.

This implementation deosn’t use special nodes.

Lets see how to insert a node in double linked list

here is the code for inserting a node before a known node

//insert before a known node and return the inserted node Node *insertbefore(Node *before, void *data) { Node* n; n = (Node *) malloc (sizeof(Node)); n->info = data; //incase header node is not created if (!before) { n->prev = NULL; n->next = NULL; return n; } n->prev = before->prev; n->next = before; if (before->prev) { before->prev->next = n; } before->prev = n; return n; }

the below code segment inserts after a known node in double linked list

//insert after a known node and return the inserted node Node *insertafter(Node *after, void *data) { Node* n; n = (Node *) malloc (sizeof(Node)); n->info = data; //incase header node is not created if (!after) { n->prev = NULL; n->next = NULL; return n; } n->prev = after; n->next = after->next; if (after->next) { after->next->prev = n; } after->next = n; return n; }

now lets see how to delete a node in double linked list

here is the code deleteting a node before and after a known node…

//delete before a known node and return the node before deleted node Node *deletebefore(Node *before) { Node* tmp; tmp = before->prev; before->prev = tmp->prev; if (tmp->prev) { tmp->prev->next = before; } free(tmp); return before->prev; } //delete after a known node and return the node after deleted node Node *deleteafter(Node *after) { Node* tmp; tmp = after->next; after->next = tmp->next; if (tmp->next) { tmp->next->prev = after; } free(tmp); return after->next; }

here is the routine for deleting entire double linked list, we can give any node in double linked list to delete entire list

//given any node in list, deletes entire double linked list int deletelist(Node *n) { Node *tmp; Node* after = n; Node* before = n->prev; //delete all nodes after n (if any) while(after) { tmp = after->next; free(after); after = tmp; } //delete all nodes before n (if any) while(before) { tmp = before->prev; free(before); before = tmp; } return 0; }

the below routine searches entire double linked list given any node (not necessarily head node or tail node)

//given any node in list, search entire list Node *searchlist(Node *h, void *info) { Node* n = h; Node* after = h; Node* before = h->prev; //search all nodes after n (if any) while(after) { if (after->info == info) { return after; } after = after->next; } //search all nodes before n (if any) while(before) { if (before->info == info) { return n; } before = before->prev; } return NULL; }

printing double linked list

//given any node in list, prints entire list int printlist(Node *h) { Node* t = h; //check we have any nodes before the node given while(t && t->prev) { t = t->prev; } while(t) { printf(" %d ", t->info); t = t->next; } printf(" NULL\n"); return 0; }

finally here is a routine which does find out broken links in double linked list, wondering what is a broken link…

here is the code snippet for detecting broken links in double linked list…

int detecbrokentlist(Node *n) { int brokenlinks = 0; Node *tmp = n; Node* after = n->next; Node* before = n->prev; //detect abnormalities in the list (broken links) after n (if any) while(after && tmp) { if ((after->prev != tmp) || (tmp->next != after)) { brokenlinks++; } after = after->next; tmp = tmp->next; } //detect abnormalities in the list (broken links) before n (if any) tmp = n; while(before && tmp) { if ((before->next != tmp) || (tmp->prev != before)) { brokenlinks++; } before = before->prev; tmp = tmp->prev; } return brokenlinks; }

download full code for double linked list program [doublelinkedlist.c]

[…] refer double linked list post for information about double linked list. Here in this post we will be discussing about reversing a double linked list. […]

30 March 2007at5pmbut how i sort adoubly linked list?

12 April 2008at9pmCant understand what is meant by–

if(!before)

what does it aim at?

Its present in your ” insertion” code

2 November 2009at12am