Spread the post

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

Example 1:

head8070605040302010

Visualize doubly linked list

Stack Areamainhead(pointer)insert_datahead(pointer)value (int) =10 Heap Areastruct Nodedata (int)= 80next (pointer) prev (pointer)= NULLstruct Nodedata (int)= 70next (pointer) prev (pointer) struct Nodedata (int)= 60next (pointer) prev (pointer) struct Nodedata (int)= 50next (pointer) prev (pointer) struct Nodedata (int)= 40next (pointer) prev (pointer) struct Nodedata (int)= 30next (pointer) prev (pointer) struct Nodedata (int)= 20next (pointer) prev (pointer) struct Nodedata (int)= 10next (pointer)= NULLprev (pointer)

When use head and tail pointer.

headTail87654321

Try it yourself

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)

Spread the post

Recommended Posts: