Doubly linked list data structure

In a double linked list, every list of the element has both a reference to the next element and reference to the prior element. Hence doubly linked list can be traversed in both directions and two pointers are used. Diagrammatically a node is represented as,

RLINK contains the address of the succeeding node and LLINK contains the address of the predecessor node. Data fields contain actual data.

The structure definition for each node is as follows:

struct node {
  struct node* rlink
  int data;
  struct node* llink;
};

The leftmost and rightmost nodes of doubly linked lists are pointed by L & R pointers respectively. 

doubly linked list Advantage

• A doubly linked list can be traversed in both directions. In some applications, it is desirable to traverse in both directions but efficient i.e time taking process in reverse traveling because the last node doesn’t maintain the first node address.

doubly linked list Disadvantages

• More memory is required by doubly linked list then singly linked list as each node has two links for its predecessor and successor respectively.
• the insertion or deletion of a node takes a bit longer.

Primitive Operations on a doubly linked list

Insertion and deletion are two primitive operations performed on the double list.

Inserting a Node at the Beginning

• If the list is empty, create a new node and assign NULL to its right link and left link and assign the address of a new node to pointers L and R.
• If the list I not empty then,
  • Assign NULL to link of the new node
  • newnode->  link=NULL
  • Assign address of the first node to rlink of a new node
  • newnode ->  rlink = L
  • Assign the address of the new node to llink of first node
  • L-> llink=newnode
  • Assign address of the new node to L

Example:

Inserting a Node at End

• If the list is empty then, create a new node and assign NULL to its left link and right link. Assign address of the new node to pointers L and R.
• Otherwise
  • traverse to the last node or use the address of the last node i.e.,R
  • assign the address  of a new node to rlink of last node
  • R -> rlink=newnode
  • Assign address of last node to llink pf new node
  • newnode -> link=R
  • Assign address of the new node to R
  • R=newnode
  • Assign NULL to rlink of new node
  • newnode -> rlink=NULL

 

Insert a Node at any Position

To insert a new node at any position i, traverse the linked list up to (i-1)th position and perform the following operations:

• newnode -> rlink=temp -> rlink;
• newnode -> llink=temp;
• temp -> rlink=newnode;
• temp -> rlink -> llink=newnode;

Deletion at the Beginning

• If there is no node in list, deletion is not possible.
• Otherwise, make L point to the second element and llink of second element point to NULL.
  • R=R -> llink
  • R -> rlink=NULL

Deleting a node in middle (at position i)

• If list is empty, then deletion is not possible.otherwise,
• traverse the linked list upto position (i-1) and make its rlink point to (i+1)th node, make (i+1)th node llink point to(i=1)th node.
  • temp -> rlink=temp -> rlink -> rlink
  • temp -> rlink -> llink=temp