Link list is a collection of data elements called nodes. It is a linear data structure which means that elements of link list are arranged in sequential order.
A linked list can be perceived as a train or a sequence of nodes in which each node contains one or more data fields and a pointer to the next node.
- Data part or record
- Address part also known as link to next node
The right part of the node contains a pointer to the next node (or address of the next node in sequence).
Memory Allocation and De-Allocation for a Linked list
As memory management is a primary function of any OS and hence OS keeps track of the memory which is available as well as memory which is occupied.
The list of free memory blocks or available space is called the free pool.
In free pool, we have a pointer variable AVAIL which stores the address of the first free space.
In OS, garbage collection is the process of collecting all the memory blocks which are not being used and adds their address to the free pool.
Traversing Linked Lists
We can traverse the entire linked list using a single pointer variable called START.
The START node contains the address of the first node.
If START=NULL, this means that the linked list is empty and contains no nodes.
For traversing, we also make use of a pointer variable (PTR) which points to the node currently being assessed,
Singly Linked Lists
It is the simplest type of linked list in which every node contains data and a pointer to the next node of the same data type. START points to the first node and last node contains the NULL in the address part of the node.
ALGORITHM FOR TRAVERSING A LINKED LIST
Step 1: [INITIALIZE] SET PTR = START
Step 2: Repeat Steps 3 and 4 while PTR != NULL
Step 3: Apply Process to PTR->DATA
Step 4: SET PTR = PTR->NEXT
[END OF LOOP]
Step 5: EXIT
ALGORITHM TO SEARCH A LINKED LIST
Step 1: [INITIALIZE] SET PTR = START
Step 2: Repeat Step 3 while PTR != NULL
Step 3: IF VAL = PTR->DATA
SET POS = PTR
Go To Step 5
ELSE
SET PTR = PTR->NEXT
[END OF IF]
[END OF LOOP]
Step 4: SET POS = NULL
Step 5: EXIT
Circular Linked Lists
In a circular linked list, the last node contains a pointer to the first node of the list.
A circular linked list has no beginning and no ending.
These are widely used in operating systems for Task Maintenance.
Algorithm to insert a new node in the beginning of the circular
linked list
Step 1: IF AVAIL = NULL, then
Write OVERFLOW
Go to Step 11
[END OF IF]
Step 2: SET New_Node = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET New_Node->DATA = VAL
Step 5: SET PTR = START
Step 6: Repeat Step 7 while PTR->NEXT != START
Step 7: PTR = PTR->NEXT
Step 8: SET New_Node->Next = START
Step 9: SET PTR->NEXT = New_Node
Step 10: SET START = New_Node
Step 11: EXIT
Doubly Linked List
Doubly linked list is more complex type of linked list which contains a pointer to the next as well as previous node in the sequence.
It consists of three parts:
data part
a pointer to the next node
a pointer to the previous node
In doubly linked list, the previous part of the first node and the next part of the last node will contain NULL.
Main advantage of doubly linked list is that it makes searching twice as efficient as it provides the ease to manipulate the elements of the list as it maintains pointers to nodes in both the direction (forward and backward).
Algorithm to insert a new node in the beginning of the
doubly linked list
Step 1: IF AVAIL = NULL, then
Write OVERFLOW
Go to Step 9
[END OF IF]
Step 2: SET New_Node = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET New_Node->DATA = VAL
Step 5: SET New_Node->PREV = NULL
Step 6: SET New_Node->Next = START
Step 7: SET START->PREV = New_Node
Step 8: SET START = New_Node
Step 9: EXIT
Algorithm to delete the last node of the doubly linked
list
Step 1: IF START = NULL, then
Write UNDERFLOW
Go to Step 7
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Step 4 and 5 while PTR->NEXT != NULL
Step 4: SET PTR = PTR->NEXT
[END OF LOOP]
Step 5: SET PTR->PREV->NEXT = NULL
Step 6: FREE PTR
Step 7: EXIT
Circular Doubly Linked List
A circular doubly linked list or a circular two way linked list is a more complex type of linked list which contains a pointer to the next as well as previous node in the sequence.
Circular doubly linked list does not contain NULL in the previous field of the first node and the next field of the last node.
Rather, the next part of the last node stores the address of the first node of the list, i.e; START. Similarly, the previous part of the first field stores the address of the last node.
Circular doubly linked list contains three parts in its structure so it calls for more space per node and for more expensive basic operations.
While traversing a circular doubly linked list, we can begin at any node and traverse the list in any direction forward or backward until we reach the same node where we had started.
Algorithm to insert a new node in the beginning of the circular
doubly linked list
Step 1: IF AVAIL = NULL, then
Write OVERFLOW
Go to Step 13
[END OF IF]
Step 2: SET New_Node = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET New_Node->DATA = VAL
Step 5: SET PTR = START
Step 6: Repeat step 7 while PTR->NEXT != START
Step 7: SET PTR = PTR->NEXT
[END of LOOP]
Step 8: SET PTR->NEXT = new_node;
Step 9: SET New_Node->PREV = PTR;
Step 10: SET new_node->next = START;
Step 11: SET START->PREV = New_Node
Step 12: SET START = New_Node
Step 13: EXIT
Tags:
Data Structure