Related Blog Items

• Circular Doubly Linked List With Out Using Special Head or Tail Node
• Reversing a double linked list
• Reversing a circular single linked list using pointers
• Sorting A Linked List with Bubble Sort
• Circular Linked Lists

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]

Popularity: 19%

You need to log on to convert this article into PDF

Related Blog Items

• Circular Doubly Linked List With Out Using Special Head or Tail Node
• Reversing a double linked list
• Reversing a circular single linked list using pointers
• Sorting A Linked List with Bubble Sort
• Circular Linked Lists

This entry was written by ponnada and posted on December 10, 2006 at 3:27 pm and filed under C Tidbits, C++ Tidbits, Data Structures in C/C++. Bookmark the permalink. Follow any comments here with the RSS feed for this post. Post a comment or leave a trackback: Trackback URL.