cpppro

Double Linked List With Out Using Special Head or Tail Node

In C Tidbits, Data Structures in C/C++ on December 10, 2006 at 3:27 pm

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…

 double linked list - 1

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

double linked list - insertion

 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

 

double linked list - deletion

 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…

 

double linked list - broken links

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]

Advertisements
  1. […] 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. […]

  2. but how i sort adoubly linked list?

  3. Cant understand what is meant by–

    if(!before)

    what does it aim at?

    Its present in your ” insertion” code

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: