Data Structures and Algorithms - Old Questions
2. Explain the structure of Doubly Linked List (DLL). Differentiate the difference between DLL and Doubly Circular Linked List (DCLL). Explain the procedures to insert a node in DLL at the beginning and at the last.
Doubly linked list is a sequence of elements in which every element has links to its previous element and next element in the sequence.
In double linked list, every node has link to its previous node and next node. So, we can traverse forward by using next field and can traverse backward by using previous field. Every node in a double linked list contains three fields and they are shown in the following figure...
Here, 'link1' field is used to store the address of the previous node in the sequence, 'link2' field is used to store the address of the next node in the sequence and 'data' field is used to store the actual value of that node.
Example:
1.Allocate memory for the new node as,
newnode=(NodeType*)malloc(sizeof(NodeType))
2. Assign value to info field of a new node
set newnode->info=item
3. set newnode->prev=newnode->next=NULL
4. set newnode->next=head
5. set head->prev=newnode
6. set head=newnode
7. End
Procedure for inserting a node at the end of a doubly linked list:
1. Allocate memory for the new node as,
newnode=(NodeType*)malloc(sizeof(NodeType))
2. Assign value to info field of a new node
set newnode->info=item
3. set newnode->next=NULL
4. if head==NULL
set newnode->prev=NULL;
set head=newnode;
5. if head!=NULL
set temp=head
while(temp->next!=NULL)
temp=temp->next;
end while
set temp->next=newnode;
set newnode->prev=temp
6. End