Introduction of doubly linked list
Doubly linked list is collection of nodes. each node contain two fields. pointer and data.
Basic structure of a doubly linked list.
Note that doubly linked list requires at least two pointer field. This pointer are store the information of next and previous nodes of linked list.
C doubly linked list example
Visualize doubly linked list
When use head and tail pointer.
Doubly linked list advantages
1) Traversal are possible both direction backward and forward
2) Possible to backtrack sibling nodes.
Doubly linked list Dis-advantages
Every node of DLL Require extra space for an previous pointer.
Doubly linked list complexity
Insert node at beginning Time complexity O(1).
Insertion Time complexity
Insert node at end Time complexity O(n).
Deletion Time complexity
Deletion at start O(1)
Deletion between nodes O(n).
Note : If used two pointer head and tail. head are pointed first node of linked list. and tail are point to end of linked list then insertion at end time complexity is O(1). And deletion at end of linked list Time complexity are O(1)