Header Linked List:
It has two types: Circular header linked list and grounded header linked list.
In circular, the last node is linked to the header node and in grounded, the last node is linked to the NULL.
Traversing in a circular header linked list
- Set PTR = LINK [START] //initializing a pointer
- Repeat step 3 and 4, while PTR ≠ START //PTR ≠ NULL for grounded list
- Apply PROCESS to INFO [PTR]
- Set PTR = LINK [PTR] //PTR points to the next node
[End of while loop]
Two way linked list
Insertion (INFO, NEXT, PREV, AVAIL, LOCA, LOCB, ITEM)
- If AVAIL = NULL, then write: Overflow and Exit //checking for overflow
- Set NEW = AVAIL, AVAIL = NEXT [AVAIL], INFO [NEW] = ITEM.
//removing node from AVAIL list and copy the ITEM into it
- Set NEXT [LOCA] = NEW, NEXT [NEW] = LOCB,
PREV [LOCB] = NEW, PREV [NEW] = LOCA //inserting node into the list
//INFO: Data part of the node
//NEXT: Next pointer of the node
//PREV: Previous pointer of the node
//AVAIL: First node of the AVAIL list
//LOCA and LOCB: Locations in which the new node is to be inserted.
Deletion (INFO, NEXT, PREV, AVAIL, LOC)
- Set NEXT [PREV [LOC]] = NEXT [LOC] and PREV [NEXT [LOC]] = PREV [LOC]
- Set NEXT [LOC] = AVAIL and AVAIL = LOC //inserting node to the AVAIL list
Author: Indrajeet Gupta