Table of Contents
Circular Linked list in Data Structure
In circular linked list, the link field in the last node contains a pointer back to the first node rather than the NULL pointer. Thus, the last node of list points to the first node.
Insertion of node in Circular linked list:
A. Insertion of node at the beginning
Algorithm: INSBEG (INFO, LINK, START, ITEM, TEMP, PTR)
This algorithm inserts TEMP as first node in the circular linked list. ITEM variable contains data of new node.
Step 1: Allocate memory for new node TEMP.
Step 2: [ Store the ITEM into INFO part of new node ]
TEMP → INFO := ITEM
Step 3: [ Check if list is empty. ]
If START = NULL, then
START := TEMP
TEMP → LINK := TEMP
and Return.
[ End of If structure ]
Step 4: [ Initialize the PTR variable. ]
PTR := START
Step 5: Repeat while PTR → LINK ≠ START
PTR := PTR → LINK
[ End of Loop structure ]
TEMP → LINK := START
START := TEMP
PTR → LINK := TEMP
Step 6: [ Exit ]
Return.
B. Insertion of node at the end
Algorithm: INSLAST (INFO, LINK, START, ITEM, TEMP, PTR)
This algorithm inserts TEMP as last node in the circular linked list. ITEM variable contains data of new node.
Step 1: Allocate memory for new node TEMP.
Step 2: [ Store the ITEM into INFO part of new node ]
TEMP → INFO := ITEM
Step 3: [ Make the TEMP node points to NULL. ]
TEMP → LINK := NULL
Step 4: [Check whether list is empty or not. ]
If START = NULL then
START := TEMP
TEMP → LINK := TEMP
and Return.
[ End of If structure ]
Step 5: [ Initialize the PTR variable. ]
PTR := START
Step 6: [ Increment the PTR variable ]
Repeat while PTR LINK ≠ START PTR := PTR LINK
[ End of Loop structure ]
Step 7: [ Insert the new node TEMP as last node. ]
PTR → LINK := TEMP
TEMP → LINK := START
Step 8: [ Exit ]
Return.
C. Insertion of node after specified position
Algorithm: INSPOS (INFO, LINK, START, ITEM, TEMP, POS, C, PTR, Q)
This algorithm inserts TEMP node after position POS in the circular linked list. ITEM variable contains data of new node.
Step 1: [Check whether list is empty or not. ]
If START = NULL then
Write (‘List is empty’)
and return.
[ End of If structure ]
Step 2: [ Initialize the PTR and C variable. ]
PTR := START
C := 0
Step 3: Repeat while PTR → LINK ≠ START and C ≠ POS
C := C+1
Q := PTR
PTR := PTR → LINK
[ End of Loop structure ]
Step 4: If PTR → LINK = START and C ≠ POS then
Write (‘Position not found’)
and Return.
Step 5: Allocate memory for new node TEMP.
Step 6: [ Store the ITEM into INFO part of new node ]
TEMP → INFO := ITEM
Step 7: [ Insert the new node TEMP. ]
TEMP → LINK := PTR
Q → LINK := TEMP
Step 8: [ Exit ]
Return.
Deletion of node from Circular linked list:
A. Deletion of first node
Algorithm: DELBEG (INFO, LINK, START, ITEM, TEMP, PTR)
This algorithm deletes the first node from the circular linked list and store it in TEMP. ITEM variable is used to store the data of deleted node.
Step 1: [Check whether list is empty or not. ]
If START = NULL then
Write (‘List is empty’)
and return.
[ End of If structure ]
Step 2: [ Store the data of first node into ITEM. ]
ITEM := START → INFO
Step 3: [ Remove the node ]
TEMP := START
START := START → LINK
PTR → LINK := START
Step 4: Free the TEMP node.
Step 5: [ Exit ]
Return.
B. Deletion of Last Node
Algorithm: DELLAST (INFO, LINK, START, ITEM, PTR, Q)
This algorithm deletes the last node from the circular linked list. ITEM variable is used to store the data of deleted node.
Step 1: [Check whether list is empty or not. ]
If START = NULL then
Write (‘List is empty’)
and return.
[ End of If structure ]
Step 2: [ Initialize the PTR variable. ] PTR := START
Step 3: Repeat while PTR LINK ≠ START
Q := PTR
PTR := PTR → LINK
[ End of Loop structure ]
Step 4: [ Store the data of last node into ITEM. ]
ITEM := PTR → INFO
Step 5: [ Deletes the node ]
Q → LINK := START
Step 6: Free the PTR node.
Step 7: [ Exit ]
Return.
C. Deletion of Node Containing Particular Data
Algorithm: DELETE (INFO, LINK, START, ITEM, PTR, Q)
This algorithm deletes the node containing the data ITEM from the circular linked list.
Step 1: [Check whether list is empty or not. ]
If START = NULL then
Write (‘List is empty’)
and return.
[ End of If structure ]
Step 2: [ Initialize the PTR variable. ]
PTR := START
Step 3: Repeat while PTR LINK ≠ START
If PTR → INFO = ITEM, then:
If PTR = START, then: [ First node is to be deleted ]
If START → LINK = START [ There is only one node ]
START := NULL
Free the PTR node and Return.
Else:
TEMP := PTR
Repeat while PTR → LINK ≠ START
PTR := PTR → LINK
[ End of Loop structure ]
START := START → LINK
PTR → LINK := START
Free the TEMP node and Return.
[ End of If structure ]
Else:
Q → LINK = PTR → LINK
Free the PTR node and Return.
[ End of If structure ]
Else:
Q := PTR [ Moving to next node. ]
PTR := PTR → LINK
[ End of If structure ]
Step 4: Write (‘ITEM not found’)
Step 5: [ Exit ]
Return.
Stack and Queue as Circular Linked List:
Insertion in a circular linked stack.
Algorithm: PUSH Circular (TOP, INFO, LINK, TEMP, PTR)
Step 1: Allocate memory for temp node.
Step 2: ITEM → TOP := INFO
Step 3: IF TOP := NULL Then
TOP := TEMP AND TEMP → LINK := TOP AND RETUN
Step 4: PTR := TOP
Step 5: While PTR → LINK /= TOP
PTR := PTR → LINK
Step 6: TEMP LINK := TOP
PTR → LINK := TEMP
TOP = TEMP
Step 7: Return.
Algorithm: POPCirList (TOP, TEMP, PTR)
Step 1: If TOP = NULL then
Write (‘Stack Underflow!’)
and return.
Step 2: IF TOP → LINK := TOP then
free temp and return
Step 3: PTR := TOP
Step 4: While PTR → LINK /= TOP
PTR := PTR → LINK
Step 5: TEMP := TOP
Step 6: PTR → LINK := TOP → LINK
Step 7: TOP := TOP → LINK
Step 8: TREE TEMP NODE AND Return.
Add new element in circular linked queue
Insetqlink : ADD (Q, INFO, TEMP, PTR)
Step 1: Allocate memory for new node.
Step 2: TEMP → INFO := ITEM
Step 3: IF Q = NULL then
Q := temp;
Q → LINK;
TEMP RETURN
Step 4: TEMP → LINK := Q → LINK
Step 5: Q → LINK := TEMP
Step 6: Return.
Delete element from circular linked queue
DeletecurQ(Q, PTR,Temp)
Step 1: If Q = NULL then
Write (‘Queue is empty !’)
and return.
Step 2: IF Q LINK:= Q then
free Q and return
Step 3: PTR := Q → LINK
Step 4: Q → LINK := PTR → LINK
Step 5: FREE PTR NODE AND Return.
Header Node
Sometimes it is desirable to keep an extra node at the front of a list. Such a node doesn’t represent an item in the list and is called a header node or a list header. The info portion of such a header node might be unused.
Use of Header node
The INFO portion of such a node could be used to keep global information about the entire list.
Example:- INFO portion of the header node contains the number of nodes (not including the header) in the list.
Advantage: The no. of items in the list may be obtained directly from the header node without traversing the entire list.
Header node used in Circular list
It is possible in the case of circular list to get into an infinite loop without taking care in processing. Since the last node of a list leads to the first node, the traversing of a list leads to the infinite looping.
To solve this problem, a header node can be placed as a first node in the circular list. This list header may be recognized by a special value in its info field that cannot be the valid contents of a list or it may contain a flag marking it as a header.
Application of Linked List:
- One application of linked list is to maintain directory of nomes.
- Another application is polynomial manipulation.
- Linked list are used to implement sparse matrices.
Sparse Matrices:- An m x n matrix is said to be sparse if many of its elements are zero. A matrix that is not sparse is dense.
Example: 4 x 8 Matrix
0 0 0 2 0 0 1 0
0 6 0 0 7 0 0 3
0 0 0 9 0 8 0 0
0 4 5 0 0 0 0 0
Array Representation:
Linked Representation:
Polynomial Representation:
P= 5x2 + 2x2 + 10x + 6
You May Like to Browers More
