UNIT- 4
Linked Lists
Linked List
Uses of Linked List
Why use linked list over array?
Till now, we were using array data structure to organize the group of elements that are to be stored individually in the memory. However, Array has several advantages and disadvantages which must be known in order to decide the data structure which will be used throughout the program.
Array contains following limitations:
Linked list is the data structure which can overcome all the limitations of an array. Using linked list is useful because,
Singly linked list or one way chain
Singly linked list can be defined as the collection of ordered set of elements. The number of elements may vary according to need of the program. A node in the singly, linked list consist of two parts: data part and link part. Data part of the node stores actual information that is to be represented by the node while the link part of the node stores the address of its immediate successor.
One way chain or singly linked list can be traversed only in one direction. In other words, we can say that each node contains only next pointer, therefore we cannot traverse the list in the reverse direction.
Consider an example where the marks obtained by the student in three subjects are stored in a linked list as shown in the figure.
In the above figure, the arrow represents the links. The data part of every node contains the marks obtained by the student in the different subject. The last node in the list is identified by the null pointer which is present in the address part of the last node. We can have as many elements we require, in the data part of the list.
Complexity
Data Structure | Time Complexity | Space Compleity | |||||||
| Average | Worst | Worst | ||||||
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion |
|
Singly Linked List | θ(n) | θ(n) | θ(1) | θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
Operations on Singly Linked List
There are various operations which can be performed on singly linked list. A list of all such operations is given below.
Node Creation
Insertion
The insertion into a singly linked list can be performed at different positions. Based on the position of the new node being inserted, the insertion is categorized into the following categories.
SN | Operation | Description |
1 | Insertion at beginning | It involves inserting any element at the front of the list. We just need to a few link adjustments to make the new node as the head of the list. |
2 | Insertion at end of the list | It involves insertion at the last of the linked list. The new node can be inserted as the only node in the list or it can be inserted as the last one. Different logics are implemented in each scenario. |
3 | Insertion after specified node | It involves insertion after the specified node of the linked list. We need to skip the desired number of nodes in order to reach the node after which the new node will be inserted. . |
Deletion and Traversing
The Deletion of a node from a singly linked list can be performed at different positions. Based on the position of the node being deleted, the operation is categorized into the following categories.
SN | Operation | Description |
1 | Deletion at beginning | It involves deletion of a node from the beginning of the list. This is the simplest operation among all. It just need a few adjustments in the node pointers. |
2 | It involves deleting the last node of the list. The list can either be empty or full. Different logic is implemented for the different scenarios. | |
3 | Deletion after specified node | It involves deleting the node after the specified node in the list. we need to skip the desired number of nodes to reach the node after which the node will be deleted. This requires traversing through the list. |
4 | Traversing | In traversing, we simply visit each node of the list at least once in order to perform some specific operation on it, for example, printing data part of each node present in the list. |
5 | Searching | In searching, we match each element of the list with the given element. If the element is found on any of the location then location of that element is returned otherwise null is returned. . |
Linked List in C: Menu Driven Program
Output:
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete node after specified location
7. Search for an element
8. Show
9. Exit
Enter your choice?
1
Enter value
1
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete node after specified location
7. Search for an element
8. Show
9. Exit
Enter your choice?
2
Enter value?
2
Node inserted
*********Main Menu*********
Choose one option from the following list .
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete node after specified location
7. Search for an element
8. Show
9. Exit
Enter your choice?
3
Enter element value1
Enter the location after which you want to insert 1
Node inserted
*********Main Menu*********
Choose one option from the following list.
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete node after specified location
7. Search for an element
8. Show
9. Exit
Enter your choice?
8
printing values . . . . .
1
2
1
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete node after specified location
7. Search for an element
8. Show
9. Exit
Enter your choice?
2
Enter value?
123
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete node after specified location
7. Search for an element
8. Show
9. Exit
Enter your choice?
1
Enter value
1234
Node inserted
*********Main Menu*********
Choose one option from the following list.
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete node after specified location
7. Search for an element
8. Show
9. Exit
Enter your choice?
4
Node deleted from the beginning ...
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete node after specified location
7. Search for an element
8. Show
9. Exit
Enter your choice?
5
Deleted Node from the last ...
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete node after specified location
7. Search for an element
8. Show
9. Exit
Enter your choice?
6
Enter the location of the node after which you want to perform deletion
1
Deleted node 2
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete node after specified location
7. Search for an element
8. Show
9. Exit
Enter your choice?
8
printing values . . . . .
1
1
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete node after specified location
7. Search for an element
8. Show
9. Exit
Enter your choice?
7
Enter item which you want to search?
1
item found at location 1
item found at location 2
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete node after specified location
7. Search for an element
8. Show
9. Exit
Enter your choice?
9
A linked list is a sequence of data structures, which are connected together via links.
Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array. Following are the important terms to understand the concept of Linked List.
Linked List Representation
Linked list can be visualized as a chain of nodes, where every node points to the next node.
As per the above illustration, following are the important points to be considered.
Types of Linked List
Following are the various types of linked list.
Basic Operations
Following are the basic operations supported by a list.
Insertion Operation
Adding a new node in linked list is a more than one step activity. We shall learn this with diagrams here. First, create a node using the same structure and find the location where it has to be inserted.
Imagine that we are inserting a node B (NewNode), between A (LeftNode) and C (RightNode). Then point B.next to C −
NewNode.next −> RightNode;
It should look like this −
Now, the next node at the left should point to the new node.
LeftNode.next −> NewNode;
This will put the new node in the middle of the two. The new list should look like this −
Similar steps should be taken if the node is being inserted at the beginning of the list. While inserting it at the end, the second last node of the list should point to the new node and the new node will point to NULL.
Deletion Operation
Deletion is also a more than one step process. We shall learn with pictorial representation. First, locate the target node to be removed, by using searching algorithms.
The left (previous) node of the target node now should point to the next node of the target node −
LeftNode.next −> TargetNode.next;
This will remove the link that was pointing to the target node. Now, using the following code, we will remove what the target node is pointing at.
TargetNode.next −> NULL;
We need to use the deleted node. We can keep that in memory otherwise we can simply deallocate memory and wipe off the target node completely.
Reverse Operation
This operation is a thorough one. We need to make the last node to be pointed by the head node and reverse the whole linked list.
First, we traverse to the end of the list. It should be pointing to NULL. Now, we shall make it point to its previous node −
We have to make sure that the last node is not the last node. So we'll have some temp node, which looks like the head node pointing to the last node. Now, we shall make all left side nodes point to their previous nodes one by one.
Except the node (first node) pointed by the head node, all nodes should point to their predecessor, making them their new successor. The first node will point to NULL.
We'll make the head node point to the new first node by using the temp node.
The linked list is now reversed. To see linked list implementation in C, programming language.
A linked list is a sequence of data structures, which are connected together via links. Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array.
Implementation in C
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
struct node {
int data;
int key;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
//display the list
void printList(){
struct node *ptr = head;
printf("\n[ ");
//start from the beginning
while(ptr != NULL){
printf("(%d,%d) ",ptr->key,ptr->data);
ptr= ptr->next;
}
printf(" ]");
}
//insert link at the first location
void insertFirst(int key,int data){
//create a link
struct node *link =(struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
//point it to old first node
link->next= head;
//point first to new first node
head= link;
}
//delete first item
struct node* deleteFirst(){
//save reference to first link
struct node *tempLink = head;
//mark next to first link as first
head= head->next;
//return the deleted link
return tempLink;
}
//is list empty
bool isEmpty(){
return head == NULL;
}
int length(){
int length =0;
struct node *current;
for(current = head; current != NULL; current = current->next){
length++;
}
return length;
}
//find a link with given key
struct node* find(int key){
//start from the first link
struct node* current = head;
//if list is empty
if(head == NULL){
return NULL;
}
//navigate through list
while(current->key != key){
//if it is last node
if(current->next== NULL){
return NULL;
}else{
//go to next link
current= current->next;
}
}
//if data found, return the current Link
return current;
}
//delete a link with given key
struct node*delete(int key){
//start from the first link
struct node* current = head;
struct node* previous = NULL;
//if list is empty
if(head == NULL){
return NULL;
}
//navigate through list
while(current->key != key){
//if it is last node
if(current->next== NULL){
return NULL;
}else{
//store reference to current link
previous= current;
//move to next link
current= current->next;
}
}
//found a match, update the link
if(current == head){
//change first to point to next link
head= head->next;
}else{
//bypass the current link
previous->next= current->next;
}
return current;
}
void sort(){
int i, j, k, tempKey, tempData;
struct node *current;
struct node *next;
int size = length();
k =size ;
for( i =0; i < size -1; i++, k--){
current= head;
next= head->next;
for( j =1; j < k ; j++){
if( current->data >next->data ){
tempData= current->data;
current->data =next->data;
next->data = tempData;
tempKey= current->key;
current->key =next->key;
next->key = tempKey;
}
current= current->next;
next=next->next;
}
}
}
void reverse(struct node** head_ref){
struct node* prev = NULL;
struct node* current =*head_ref;
struct node*next;
while(current != NULL){
next= current->next;
current->next= prev;
prev= current;
current=next;
}
*head_ref = prev;
}
void main(){
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("Original List: ");
//print list
printList();
while(!isEmpty()){
struct node *temp = deleteFirst();
printf("\nDeleted value:");
printf("(%d,%d) ",temp->key,temp->data);
}
printf("\nList after deleting all items: ");
printList();
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("\nRestored List: ");
printList();
printf("\n");
struct node *foundLink = find(4);
if(foundLink != NULL){
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
}else{
printf("Element not found.");
}
delete(4);
printf("List after deleting an item: ");
printList();
printf("\n");
foundLink= find(4);
if(foundLink != NULL){
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
}else{
printf("Element not found.");
}
printf("\n");
sort();
printf("List after sorting the data: ");
printList();
reverse(&head);
printf("\nList after reversing the data: ");
printList();
}
If we compile and run the above program, it will produce the following result −
Output
Original List:
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Deleted value:(6,56)
Deleted value:(5,40)
Deleted value:(4,1)
Deleted value:(3,30)
Deleted value:(2,20)
Deleted value:(1,10)
List after deleting all items:
[ ]
Restored List:
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Element found: (4,1)
List after deleting an item:
[ (6,56) (5,40) (3,30) (2,20) (1,10) ]
Element not found.
List after sorting the data:
[ (1,10) (2,20) (3,30) (5,40) (6,56) ]
List after reversing the data:
[ (6,56) (5,40) (3,30) (2,20) (1,10) ]
Doubly linked list
Doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence. Therefore, in a doubly linked list, a node consists of three parts: node data, pointer to the next node in sequence (next pointer) , pointer to the previous node (previous pointer). A sample node in a doubly linked list is shown in the figure.
A doubly linked list containing three nodes having numbers from 1 to 3 in their data part, is shown in the following image.
In C, structure of a node in doubly linked list can be given as :
The prev part of the first node and the next part of the last node will always contain null indicating end in each direction.
In a singly linked list, we could traverse only in one direction, because each node contains address of the next node and it doesn't have any record of its previous nodes. However, doubly linked list overcome this limitation of singly linked list. Due to the fact that, each node of the list contains the address of its previous node, we can find all the details about the previous node as well by using the previous address stored inside the previous part of each node.
Memory Representation of a doubly linked list
Memory Representation of a doubly linked list is shown in the following image. Generally, doubly linked list consumes more space for every node and therefore, causes more expansive basic operations such as insertion and deletion. However, we can easily manipulate the elements of the list since the list maintains pointers in both the directions (forward and backward).
In the following image, the first element of the list that is i.e. 13 stored at address 1. The head pointer points to the starting address 1. Since this is the first element being added to the list therefore the prev of the list contains null. The next node of the list resides at address 4 therefore the first node contains 4 in its next pointer.
We can traverse the list in this way until we find any node containing null or -1 in its next part.
Operations on doubly linked list
Node Creation
All the remaining operations regarding doubly linked list are described in the following table.
SN | Operation | Description |
1 | Insertion at beginning | Adding the node into the linked list at beginning. |
2 | Insertion at end | Adding the node into the linked list to the end. |
3 | Insertion after specified node | Adding the node into the linked list after the specified node. |
4 | Deletion at beginning | Removing the node from beginning of the list |
5 | Deletion at the end | Removing the node from end of the list. |
6 | Deletion of the node having given data | Removing the node which is present just after the node containing the given data. |
7 | Searching | Comparing each node data with the item to be searched and return the location of the item in the list if the item found else return null. |
8 | Traversing | Visiting each node of the list at least once in order to perform some specific operation like searching, sorting, display, etc. |
Menu Driven Program in C to implement all the operations of doubly linked list
Output
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit
Enter your choice?
8
printing values...
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit
Enter your choice?
1
Enter Item value12
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit
Enter your choice?
1
Enter Item value123
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit
Enter your choice?
1
Enter Item value1234
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit
Enter your choice?
8
printing values...
1234
123
12
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit
Enter your choice?
2
Enter value89
node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit
Enter your choice?
3
Enter the location1
Enter value12345
node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit
Enter your choice?
8
printing values...
1234
123
12345
12
89
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit
Enter your choice?
4
node deleted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit
Enter your choice?
5
node deleted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit
Enter your choice?
8
printing values...
123
12345
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit
Enter your choice?
6
Enter the data after which the node is to be deleted : 123
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit
Enter your choice?
8
printing values...
123
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit
Enter your choice?
7
Enter item which you want to search?
123
item found at location 1
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit
Enter your choice?
6
Enter the data after which the node is to be deleted: 123
Can't delete
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Insert at any random location
4. Delete from Beginning
5. Delete from last
6. Delete the node after the given data
7. Search
8. Show
9. Exit
Enter your choice?
9
Exited..
Circular Singly Linked List
In a circular Singly linked list, the last node of the list contains a pointer to the first node of the list. We can have circular singly linked list as well as circular doubly linked list.
We traverse a circular singly linked list until we reach the same node where we started. The circular singly liked list has no beginning and no ending. There is no null value present in the next part of any of the nodes.
The following image shows a circular singly linked list.
Circular linked list are mostly used in task maintenance in operating systems. There are many examples where circular linked list are being used in computer science including browser surfing where a record of pages visited in the past by the user, is maintained in the form of circular linked lists and can be accessed again on clicking the previous button.
Memory Representation of circular linked list:
In the following image, memory representation of a circular linked list containing marks of a student in 4 subjects. However, the image shows a glimpse of how the circular list is being stored in the memory. The start or head of the list is pointing to the element with the index 1 and containing 13 marks in the data part and 4 in the next part. Which means that it is linked with the node, that is being stored at 4th index of the list.
However, due to the fact that we are considering circular linked list in the memory therefore the last node of the list contains the address of the first node of the list.
We can also have more than one number of linked list in the memory with the different start pointers pointing to the different start nodes in the list. The last node is identified by its next part which contains the address of the start node of the list. We must be able to identify the last node of any linked list so that we can find out the number of iterations which need to be performed while traversing the list.
Operations on Circular Singly linked list:
Insertion
SN | Operation | Description |
1 | Insertion at beginning | Adding a node into circular singly linked list at the beginning. |
2 | Insertion at the end | Adding a node into circular singly linked list at the end. |
Deletion & Traversing
SN | Operation | Description |
1 | Deletion at beginning | Removing the node from circular singly linked list at the beginning. |
2 | Deletion at the end | Removing the node from circular singly linked list at the end. |
3 | Searching | Compare each element of the node with the given item and return the location at which the item is present in the list otherwise return null. |
4 | Traversing | Visiting each element of the list at least once in order to perform some specific operation. |
Menu-driven program in C implementing all operations
on circular singly linked list
Output:
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice?
1
Enter the node data? 10
node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice?
2
Enter Data? 20
node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice?
2
Enter Data? 30
node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice?
3
node deleted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice?
4
node deleted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice?
5
Enter item which you want to search?
20
item found at location 1
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice?
6
printing values ...
20
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice?
7
Circular Doubly Linked List
Circular doubly linked list is a more complexed type of data structure in which a node contain pointers to its previous node as well as the next node. Circular doubly linked list doesn't contain NULL in any of the node. The last node of the list contains the address of the first node of the list. The first node of the list also contain address of the last node in its previous pointer.
A circular doubly linked list is shown in the following figure.
Due to the fact that a circular doubly linked list contains three parts in its structure therefore, it demands more space per node and more expensive basic operations. However, a circular doubly linked list provides easy manipulation of the pointers and the searching becomes twice as efficient.
Memory Management of Circular Doubly linked list
The following figure shows the way in which the memory is allocated for a circular doubly linked list. The variable head contains the address of the first element of the list i.e. 1 hence the starting node of the list contains data A is stored at address 1. Since, each node of the list is supposed to have three parts therefore, the starting node of the list contains address of the last node i.e. 8 and the next node i.e. 4. The last node of the list that is stored at address 8 and containing data as 6, contains address of the first node of the list as shown in the image i.e. 1. In circular doubly linked list, the last node is identified by the address of the first node which is stored in the next part of the last node therefore the node which contains the address of the first node, is actually the last node of the list.
Operations on circular doubly linked list :
There are various operations which can be performed on circular doubly linked list. The node structure of a circular doubly linked list is similar to doubly linked list. However, the operations on circular doubly linked list is described in the following table.
SN | Operation | Description |
1 | Insertion at beginning | Adding a node in circular doubly linked list at the beginning. |
2 | Insertion at end | Adding a node in circular doubly linked list at the end. |
3 | Deletion at beginning | Removing a node in circular doubly linked list from beginning. |
4 | Deletion at end | Removing a node in circular doubly linked list at the end. |
Traversing and searching in circular doubly linked list is similar to that in the circular singly linked list.
C program to implement all the operations on circular doubly linked list
Output:
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit
Enter your choice?
1
Enter Item value123
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit
Enter your choice?
2
Enter value234
node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit
Enter your choice?
1
Enter Item value90
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit
Enter your choice?
2
Enter value80
node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit
Enter your choice?
3
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit
Enter your choice?
4
node deleted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit
Enter your choice?
6
printing values ...
123
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit
Enter your choice?
5
Enter item which you want to search?
123
item found at location 1
*********Main Menu*********
Choose one option from the following list ...
============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit
Enter your choice?
7
Linked list implementation of stack
Instead of using array, we can also use linked list to implement stack. Linked list allocates the memory dynamically. However, time complexity in both the scenario is same for all the operations i.e. push, pop and peek.
In linked list implementation of stack, the nodes are maintained non-contiguously in the memory. Each node contains a pointer to its immediate successor node in the stack. Stack is said to be overflown if the space left in the memory heap is not enough to create a node.
The top most node in the stack always contains null in its address field. Lets discuss the way in which, each operation is performed in linked list implementation of stack.
Adding a node to the stack (Push operation)
Adding a node to the stack is referred to as push operation. Pushing an element to a stack in linked list implementation is different from that of an array implementation. In order to push an element onto the stack, the following steps are involved.
Time Complexity : o(1)
C implementation :
Deleting a node from the stack (POP operation)
Deleting a node from the top of stack is referred to as pop operation. Deleting a node from the linked list implementation of stack is different from that in the array implementation. In order to pop an element from the stack, we need to follow the following steps :
30. Check for the underflow condition: The underflow condition occurs when we try to pop from an already empty stack. The stack will be empty if the head pointer of the list points to null.
31. Adjust the head pointer accordingly: In stack, the elements are popped only from one end, therefore, the value stored in the head pointer must be deleted and the node must be freed. The next node of the head node now becomes the head node.
Time Complexity : o(n)
C implementation
Display the nodes (Traversing)
Displaying all the nodes of a stack needs traversing all the nodes of the linked list organized in the form of stack. For this purpose, we need to follow the following steps.
19. Copy the head pointer into a temporary pointer.
20. Move the temporary pointer through all the nodes of the list and print the value field attached to every node.
Time Complexity : o(n)
C Implementation
Menu Driven program in C implementing all the stack operations using linked list :
Linked List implementation of Queue
Due to the drawbacks discussed in the previous section of this tutorial, the array implementation can not be used for the large scale applications where the queues are implemented. One of the alternative of array implementation is linked list implementation of queue.
The storage requirement of linked representation of a queue with n elements is o(n) while the time requirement for operations is o(1).
In a linked queue, each node of the queue consists of two parts i.e. data part and the link part. Each element of the queue points to its immediate next element in the memory.
In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear pointer. The front pointer contains the address of the starting element of the queue while the rear pointer contains the address of the last element of the queue.
Insertion and deletions are performed at rear and front end respectively. If front and rear both are NULL, it indicates that the queue is empty.
The linked representation of queue is shown in the following figure.
Operation on Linked Queue
There are two basic operations which can be implemented on the linked queues. The operations are Insertion and Deletion.
Insert operation
The insert operation append the queue by adding an element to the end of the queue. The new element will be the last element of the queue.
Firstly, allocate the memory for the new node ptr by using the following statement.
There can be the two scenario of inserting this new node ptr into the linked queue.
In the first scenario, we insert element into an empty queue. In this case, the condition front = NULL becomes true. Now, the new element will be added as the only element of the queue and the next pointer of front and rear pointer both, will point to NULL.
In the second case, the queue contains more than one element. The condition front = NULL becomes false. In this scenario, we need to update the end pointer rear so that the next pointer of rear will point to the new node ptr. Since, this is a linked queue, hence we also need to make the rear pointer point to the newly added node ptr. We also need to make the next pointer of rear point to NULL.
In this way, the element is inserted into the queue. The algorithm and the C implementation is given as follows.
Algorithm
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
SET REAR -> NEXT = NULL
[END OF IF]
C Function
Deletion
Deletion operation removes the element that is first inserted among all the queue elements. Firstly, we need to check either the list is empty or not. The condition front == NULL becomes true if the list is empty, in this case , we simply write underflow on the console and make exit.
Otherwise, we will delete the element that is pointed by the pointer front. For this purpose, copy the node pointed by the front pointer into the pointer ptr. Now, shift the front pointer, point to its next node and free the node pointed by the node ptr. This is done by using the following statements.
The algorithm and C function is given as follows.
Algorithm
Write " Underflow "
Go to Step 5
[END OF IF]
C Function
Menu-Driven Program implementing all the operations on Linked Queue
Output:
***********Main Menu**********
==============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?1
Enter value?
123
***********Main Menu**********
==============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?1
Enter value?
90
***********Main Menu**********
==============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?3
printing values .....
123
90
***********Main Menu**********
==============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?2
***********Main Menu**********
==============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?3
printing values .....
90
***********Main Menu**********
==============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?4
TEXT BOOKS:
REFERANCE:
