Doubly Linked List
Concept of Header Node:
Sometimes it is desirable to keep an extra node at the front of the list and does
not represent any linked list node’s data and is called header node or list header.
Functions of a header node
– To point to the start of the first node of a linked list.
– The information part of the node can keep any special symbol / keywords
that shows that the node is a header node.
– Header node may contain information about the whole linked list
e-g. count of total nodes.
Doubly Linked List
Doubly Linked List has pointers to both next node and previous node.
Each node has therefore two pointers along with information parts.
, Why we need Doubly Linked List?
1. Moving forward in a singly-linked list is easy; but moving backwards is not.
– If we have a situation in which moving in both direction is needed, then
singly-linked list is not appropriate.
– To avoid this we can use two pointers in a node: one to point to next
node and another to point to the previous node:
2. Recall that the deletion of an element at the Rear or End is not easy
because we have to find the node before the tail (the last node) by link
hopping.
These two pointers help in accessing both the successor (next) and predecessor
(previous) node for any node within the list.
Every node in a doubly linked list has at least three fields:
1. LeftPointer (or previous)
– Pointer to the previous node
2. RightPointer (or next)
– Pointer to the next node
3. DATA.
Concept of Header Node:
Sometimes it is desirable to keep an extra node at the front of the list and does
not represent any linked list node’s data and is called header node or list header.
Functions of a header node
– To point to the start of the first node of a linked list.
– The information part of the node can keep any special symbol / keywords
that shows that the node is a header node.
– Header node may contain information about the whole linked list
e-g. count of total nodes.
Doubly Linked List
Doubly Linked List has pointers to both next node and previous node.
Each node has therefore two pointers along with information parts.
, Why we need Doubly Linked List?
1. Moving forward in a singly-linked list is easy; but moving backwards is not.
– If we have a situation in which moving in both direction is needed, then
singly-linked list is not appropriate.
– To avoid this we can use two pointers in a node: one to point to next
node and another to point to the previous node:
2. Recall that the deletion of an element at the Rear or End is not easy
because we have to find the node before the tail (the last node) by link
hopping.
These two pointers help in accessing both the successor (next) and predecessor
(previous) node for any node within the list.
Every node in a doubly linked list has at least three fields:
1. LeftPointer (or previous)
– Pointer to the previous node
2. RightPointer (or next)
– Pointer to the next node
3. DATA.
