Search

Sunday, February 23, 2014
0 comments

Doubly Linked List for Data Structure in C Programming

6:12 AMSunday, February 23, 2014
Doubly Linked List:

 A little more variation to linear linked list gives another type of linked list called as doubly linked list. You might have observed in the linear list that every node contains two parts. One part contains the information and the other part contains the address of the next node in the list. If another pointer part is added to the node, to contain the address of previous node then the linear linked list becomes doubly linked list. In such lists you can traverse only in one direction. In the middle of traverse if you want to come back to the previous node it is not possible. The movement is one-way. It is possible to move in both the directions in doubly linked list. You can traverse in both the directions. This application of variation is very simple. The node in doubly linked list looks as follows:


If the node is the first node of the list been previous pointer contains a NULL address because there are no previous nodes. If the node is the last node then next pointer contains a NULL address because there are no next nodes. A simple representation of doubly linked list is as follows:


In the above doubly linked list, ROOT, the external pointer points to the first node with information 12. The first node’s previous pointer points to NULL. The first node’s next pointer points to the second node with information 15. The second node’s previous pointer points to the previous node containing information 15. The last node’s next pointer points to NULL address. Creation of doubly linked list is almost similar to singly linked list. Only addition is assigning the previous pointer of every node except the first node, with the address of the previous node. The operations like traversing, searching, insertion and deletion are almost similar to singly linked list. While traversing the operation can be reversed from any point in the doubly linked list. While insertion and deletion the operations are similar to singly linked list except the change in previous as well as next pointer values.

Algorithm to create a doubly linked list:

CREATEDLL
ROOT<--NULL; CHOICE<--‘Y’
Repeat While CHOICE=’Y’
 If AVAIL = NULL Then:
  Write: ’Memory Allocation Error’ 
  Exit.
Else 
NEW<--AVAIL;   NEW-->LINK<--NULL
NEW-->PREV<--NULL;   NEW-->INFO<--Information
[Information is the data to be stored in linked list]
AVAIL<--AVAIL-->LINK
[End of it]
If ROOT=NULL Then:
   ROOT<--NEW;   TEMP<--NEW
Else 
TEMP-->LINK<--NEW;     NEW-->PREV<--TEMP
TEMP<--NEW
[End of If]
Write: ‘Do you want to add another node?(Y/N)’
 Read: CHOICE
[End of while]
Protected by Copyscape Online Copyright Protection Software

0 comments :

Post a Comment

 
Toggle Footer
Top