What is Doubly linked list? Advantages and Disadvantages
A doubly linked list is one in which all nodes are linked together by multiple numbers of links, therefore these help to accessing both predecessor node and successor node from the given node position. hence, the doubly linked list provides bi-directional traversing.
you know, one of the most striking disadvantages is that these lists are an inability to traverse the list in the backward direction. the most important thing is that it is necessary to traverse the list both in the backward direction and the forward direction.
therefore, In doubly linked list each node has two link fields. these are used for the purpose of to point to the successor node and predecessor nodes. the given below figure shows the structure of a node in the doubly linked list.
If you see a diagram, therefore the LEFT link points indicate to the predecessor node and the RIGHT link points indicate to the successor node.
there are the following the structure definition for the above node on C is like given below as follows:
typedef struct node NODE;
you know very well, you have already seen above also the doubly linked list has two link fields. the one link field for the previous pointer and the other link field for the next pointer. hence then the typical structure for each node is doubly linked list looks like this:
‘C’ structure of doubly linked list looks like as follows:
The Linked Representation of a Doubly Linked List
therefore, as you have seen the above figure the linked representation of doubly linked list is that it can traverse in both directions, forward as well as backward.
I hope in your mind one question will arise that how do the empty circular linked list look? see the below figure on how to represent.
Doubly Linked List | Basic Operation
Insertion at beginning
Adding an element or node at the beginning of the linked list
Insertion at end
Adding an element or node at the end of the linked list
Insertion after specified node
Adding an element or node after an item of the linked list.
Deletion at beginning
Removing the node or element at the beginning of the linked list.
Deletion at the end
Removing the node or element from the end of the Linked list.
Removing of the node having given data
Removing the those node or element which is present just after the node containing the given data.
first, Visiting every node of the linked list at least once in order to perform few specific operation like sorting, dispaly, searching
the Comparing of each node data with the item to be searched and return the location of the item in the Linked list if the item found else then return null.
Inserting a Node at the Beginning
there is an algorithm program to insert a new node at the beginning of a doubly linked list is given below.
1) First, Allocate the memory for the ned node.
2) Second, assign the value to the data field at the new node.
3) third, assign the LEFT and RIGHT links to NULL
4) fourth, Make the RIGHT link of the new node to the point to the head node of the list and make the LEFT link of the head node to the point to the new node.
5) fifth, Finally reset the head pointer, i.e. make it to the new node which has inserted at the beginning.
lets us look the given below the following figure
Inserting a Node at the End
there are the following an alogorithm program to insert a node at the end of a doubly linked list at the given below:-
1) first, allocate the memory for the new node
2) Second, Assign the value to the data field of the new node.
3) third, Set the LEFT and RIGHT links to the new node.
4) Fourth, if the list is not empty the traverse the list till the last and make the RIGHT link of the node to point to the new node and LEFT link of the new node to point to the last node.