Circular Linked List is a variation of Linked list in which the first element points to the last element and the last element points to the first element. Both Singly Linked List and Doubly Linked List can be made into a circular linked list.
Singly Linked List as Circular
In singly linked list, the next pointer of the last node points to the first node.
Doubly Linked List as Circular
In doubly linked list, the next pointer of the last node points to the first node and the previous pointer of the first node points to the last node making the circular in both directions.
As per the above illustration, following are the important points to be considered.
The last link’s next points to the first link of the list in both cases of singly as well as doubly linked list.
The first link’s previous points to the last of the list in case of doubly linked list.
Basic Operations in Circular Linked List
Following are the important operations supported by a circular list.
insert − Inserts an element at the start of the list.
delete − Deletes an element from the start of the list.
display − Displays the list.
Circular Linked List – Insertion Operation
The insertion operation of a circular linked list only inserts the element at the start of the list. This differs from the usual singly and doubly linked lists as there is no particular starting and ending points in this list. The insertion is done either at the start or after a particular node (or a given position) in the list.
Algorithm
1. START
2. Check if the list is empty
3. If the list is empty, add the node and point the head
to this node
4. If the list is not empty, link the existing head as
the next node to the new node.
5. Make the new node as the new head.
6. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>structnode{int data;int key;structnode*next;};structnode*head =NULL;structnode*current =NULL;
bool isEmpty(){return head ==NULL;}//insert link at the first locationvoidinsertFirst(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){
head = link;
head->next = head;}else{//point it to old first node
link->next = head;//point first to new first node
head = link;}}//display the listvoidprintList(){structnode*ptr = head;printf("\n[ ");//start from the beginningif(head !=NULL){while(ptr->next != ptr){printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;}}printf(" ]");}voidmain(){insertFirst(1,10);insertFirst(2,20);insertFirst(3,30);insertFirst(4,1);insertFirst(5,40);insertFirst(6,56);printf("Circular Linked List: ");//print listprintList();}
The Deletion operation in a Circular linked list removes a certain node from the list. The deletion operation in this type of lists can be done at the beginning, or a given position, or at the ending.
Algorithm
1. START
2. If the list is empty, then the program is returned.
3. If the list is not empty, we traverse the list using a
current pointer that is set to the head pointer and create
another pointer previous that points to the last node.
4. Suppose the list has only one node, the node is deleted
by setting the head pointer to NULL.
5. If the list has more than one node and the first node is to
be deleted, the head is set to the next node and the previous
is linked to the new head.
6. If the node to be deleted is the last node, link the preceding
node of the last node to head node.
7. If the node is neither first nor last, remove the node by
linking its preceding node to its succeeding node.
8. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>structnode{int data;int key;structnode*next;};structnode*head =NULL;structnode*current =NULL;
bool isEmpty(){return head ==NULL;}//insert link at the first locationvoidinsertFirst(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){
head = link;
head->next = head;}else{//point it to old first node
link->next = head;//point first to new first node
head = link;}}//delete first itemstructnode*deleteFirst(){//save reference to first linkstructnode*tempLink = head;if(head->next == head){
head =NULL;return tempLink;}//mark next to first link as first
head = head->next;//return the deleted linkreturn tempLink;}//display the listvoidprintList(){structnode*ptr = head;//start from the beginningif(head !=NULL){while(ptr->next != ptr){printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;}}}voidmain(){insertFirst(1,10);insertFirst(2,20);insertFirst(3,30);insertFirst(4,1);insertFirst(5,40);insertFirst(6,56);printf("Circular Linked List: ");//print listprintList();deleteFirst();printf("\nList after deleting the first item: ");printList();}
Output
Circular Linked List: (6,56) (5,40) (4,1) (3,30) (2,20)
List after deleting the first item: (5,40) (4,1) (3,30) (2,20)
Circular Linked List – Displaying the List
The Display List operation visits every node in the list and prints them all in the output.
Algorithm
1. START
2. Walk through all the nodes of the list and print them
3. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>structnode{int data;int key;structnode*next;};structnode*head =NULL;structnode*current =NULL;
bool isEmpty(){return head ==NULL;}//insert link at the first locationvoidinsertFirst(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){
head = link;
head->next = head;}else{//point it to old first node
link->next = head;//point first to new first node
head = link;}}//display the listvoidprintList(){structnode*ptr = head;printf("\n[ ");//start from the beginningif(head !=NULL){while(ptr->next != ptr){printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;}}printf(" ]");}voidmain(){insertFirst(1,10);insertFirst(2,20);insertFirst(3,30);insertFirst(4,1);insertFirst(5,40);insertFirst(6,56);printf("Circular Linked List: ");//print listprintList();}
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>structnode{int data;int key;structnode*next;};structnode*head =NULL;structnode*current =NULL;
bool isEmpty(){return head ==NULL;}intlength(){int length =0;//if list is emptyif(head ==NULL){return0;}
current = head->next;while(current != head){
length++;
current = current->next;}return length;}//insert link at the first locationvoidinsertFirst(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){
head = link;
head->next = head;}else{//point it to old first node
link->next = head;//point first to new first node
head = link;}}//delete first itemstructnode*deleteFirst(){//save reference to first linkstructnode*tempLink = head;if(head->next == head){
head =NULL;return tempLink;}//mark next to first link as first
head = head->next;//return the deleted linkreturn tempLink;}//display the listvoidprintList(){structnode*ptr = head;printf("\n[ ");//start from the beginningif(head !=NULL){while(ptr->next != ptr){printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;}}printf(" ]");}intmain(){insertFirst(1,10);insertFirst(2,20);insertFirst(3,30);insertFirst(4,1);insertFirst(5,40);insertFirst(6,56);printf("Original List: ");//print listprintList();while(!isEmpty()){structnode*temp =deleteFirst();printf("\nDeleted value:");printf("(%d,%d) ",temp->key,temp->data);}printf("\nList after deleting all items: ");printList();}
Output
Original List:
[ (6,56) (5,40) (4,1) (3,30) (2,20) ]
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:
[ ]
Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, forward as well as backward easily as compared to Single Linked List. Following are the important terms to understand the concept of doubly linked list.
Link − Each link of a linked list can store a data called an element.
Next − Each link of a linked list contains a link to the next link called Next.
Prev − Each link of a linked list contains a link to the previous link called Prev.
Linked List − A Linked List contains the connection link to the first link called First and to the last link called Last.
Doubly Linked List Representation
As per the above illustration, following are the important points to be considered.
Doubly Linked List contains a link element called first and last.
Each link carries a data field(s) and a link field called next.
Each link is linked with its next link using its next link.
Each link is linked with its previous link using its previous link.
The last link carries a link as null to mark the end of the list.
Basic Operations in Doubly Linked List
Following are the basic operations supported by a list.
Insertion − Adds an element at the beginning of the list.
Insert Last − Adds an element at the end of the list.
Insert After − Adds an element after an item of the list.
Deletion − Deletes an element at the beginning of the list.
Delete Last − Deletes an element from the end of the list.
Delete − Deletes an element from the list using the key.
Display forward − Displays the complete list in a forward manner.
Display backward − Displays the complete list in a backward manner.
Doubly Linked List – Insertion at the Beginning
In this operation, we create a new node with three compartments, one containing the data, the others containing the address of its previous and next nodes in the list. This new node is inserted at the beginning of the list.
Algorithm
1. START
2. Create a new node with three variables: prev, data, next.
3. Store the new data in the data variable
4. If the list is empty, make the new node as head.
5. Otherwise, link the address of the existing first node to the
next variable of the new node, and assign null to the prev variable.
6. Point the head to the new node.
7. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>structnode{int data;int key;structnode*next;structnode*prev;};//this link always point to first Linkstructnode*head =NULL;//this link always point to last Linkstructnode*last =NULL;structnode*current =NULL;//is list empty
bool isEmpty(){return head ==NULL;}//display the doubly linked listvoidprintList(){structnode*ptr = head;while(ptr !=NULL){printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;}}//insert link at the first locationvoidinsertFirst(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){//make it the last link
last = link;}else{//update first prev link
head->prev = link;}//point it to old first link
link->next = head;//point first to new first link
head = link;}voidmain(){insertFirst(1,10);insertFirst(2,20);insertFirst(3,30);insertFirst(4,1);insertFirst(5,40);insertFirst(6,56);printf("\nDoubly Linked List: ");printList();}
In this insertion operation, the new input node is added at the end of the doubly linked list; if the list is not empty. The head will be pointed to the new node, if the list is empty.
Algorithm
1. START
2. If the list is empty, add the node to the list and point
the head to it.
3. If the list is not empty, find the last node of the list.
4. Create a link between the last node in the list and the
new node.
5. The new node will point to NULL as it is the new last node.
6. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>structnode{int data;int key;structnode*next;structnode*prev;};//this link always point to first Linkstructnode*head =NULL;//this link always point to last Linkstructnode*last =NULL;structnode*current =NULL;//is list empty
bool isEmpty(){return head ==NULL;}//display the doubly linked listvoidprintList(){structnode*ptr = head;while(ptr !=NULL){printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;}}//insert link at the first locationvoidinsertFirst(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){//make it the last link
last = link;}else{//update first prev link
head->prev = link;}//point it to old first link
link->next = head;//point first to new first link
head = link;}//insert link at the last locationvoidinsertLast(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){//make it the last link
last = link;}else{//make link a new last link
last->next = link;//mark old last node as prev of new link
link->prev = last;}//point last to new last node
last = link;}voidmain(){insertFirst(1,10);insertFirst(2,20);insertFirst(3,30);insertFirst(4,1);insertLast(5,40);insertLast(6,56);printf("Doubly Linked List: ");printList();}
This deletion operation deletes the existing first nodes in the doubly linked list. The head is shifted to the next node and the link is removed.
Algorithm
1. START
2. Check the status of the doubly linked list
3. If the list is empty, deletion is not possible
4. If the list is not empty, the head pointer is
shifted to the next node.
5. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>structnode{int data;int key;structnode*next;structnode*prev;};//this link always point to first Linkstructnode*head =NULL;//this link always point to last Linkstructnode*last =NULL;structnode*current =NULL;//is list empty
bool isEmpty(){return head ==NULL;}//display the doubly linked listvoidprintList(){structnode*ptr = head;while(ptr !=NULL){printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;}}//insert link at the first locationvoidinsertFirst(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){//make it the last link
last = link;}else{//update first prev link
head->prev = link;}//point it to old first link
link->next = head;//point first to new first link
head = link;}//delete first itemstructnode*deleteFirst(){//save reference to first linkstructnode*tempLink = head;//if only one linkif(head->next ==NULL){
last =NULL;}else{
head->next->prev =NULL;}
head = head->next;//return the deleted linkreturn tempLink;}voidmain(){insertFirst(1,10);insertFirst(2,20);insertFirst(3,30);insertFirst(4,1);insertFirst(5,40);insertFirst(6,56);printf("Doubly Linked List: \n");printList();printf("\nList after deleting first record: \n");deleteFirst();printList();}
Output
Doubly Linked List: (6,56) (5,40) (4,1) (3,30) (2,20) (1,10)
List after deleting first record: (5,40) (4,1) (3,30) (2,20) (1,10)
Doubly Linked List – Complete Implementation
Following are the complete implementations of Doubly Linked List in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>structnode{int data;int key;structnode*next;structnode*prev;};//this link always point to first Linkstructnode*head =NULL;//this link always point to last Linkstructnode*last =NULL;structnode*current =NULL;//is list empty
bool isEmpty(){return head ==NULL;}//display the list in from first to lastvoiddisplayForward(){//start from the beginningstructnode*ptr = head;//navigate till the end of the listprintf("\n[ ");while(ptr !=NULL){printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;}printf(" ]");}//display the list from last to firstvoiddisplayBackward(){//start from the laststructnode*ptr = last;//navigate till the start of the listprintf("\n[ ");while(ptr !=NULL){//print dataprintf("(%d,%d) ",ptr->key,ptr->data);//move to next item
ptr = ptr ->prev;printf(" ");}printf(" ]");}//insert link at the first locationvoidinsertFirst(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){//make it the last link
last = link;}else{//update first prev link
head->prev = link;}//point it to old first link
link->next = head;//point first to new first link
head = link;}//insert link at the last locationvoidinsertLast(int key,int data){//create a linkstructnode*link =(structnode*)malloc(sizeof(structnode));
link->key = key;
link->data = data;if(isEmpty()){//make it the last link
last = link;}else{//make link a new last link
last->next = link;//mark old last node as prev of new link
link->prev = last;}//point last to new last node
last = link;}//delete first itemstructnode*deleteFirst(){//save reference to first linkstructnode*tempLink = head;//if only one linkif(head->next ==NULL){
last =NULL;}else{
head->next->prev =NULL;}
head = head->next;//return the deleted linkreturn tempLink;}//delete link at the last locationstructnode*deleteLast(){//save reference to last linkstructnode*tempLink = last;//if only one linkif(head->next ==NULL){
head =NULL;}else{
last->prev->next =NULL;}
last = last->prev;//return the deleted linkreturn tempLink;}//delete a link with given keystructnode*delete(int key){//start from the first linkstructnode* current = head;structnode* previous =NULL;//if list is emptyif(head ==NULL){returnNULL;}//navigate through listwhile(current->key != key){//if it is last nodeif(current->next ==NULL){returnNULL;}else{//store reference to current link
previous = current;//move to next link
current = current->next;}}//found a match, update the linkif(current == head){//change first to point to next link
head = head->next;}else{//bypass the current link
current->prev->next = current->next;}if(current == last){//change last to point to prev link
last = current->prev;}else{
current->next->prev = current->prev;}return current;}
bool insertAfter(int key,int newKey,int data){//start from the first linkstructnode*current = head;//if list is emptyif(head ==NULL){return false;}//navigate through listwhile(current->key != key){//if it is last nodeif(current->next ==NULL){return false;}else{//move to next link
current = current->next;}}//create a linkstructnode*newLink =(structnode*)malloc(sizeof(structnode));
newLink->key = key;
newLink->data = data;if(current == last){
newLink->next =NULL;
last = newLink;}else{
newLink->next = current->next;
current->next->prev = newLink;}
newLink->prev = current;
current->next = newLink;return true;}intmain(){insertFirst(1,10);insertFirst(2,20);insertFirst(3,30);insertFirst(4,1);insertFirst(5,40);insertFirst(6,56);printf("\nList (First to Last): ");displayForward();printf("\n");printf("\nList (Last to first): ");displayBackward();printf("\nList , after deleting first record: ");deleteFirst();displayForward();printf("\nList , after deleting last record: ");deleteLast();displayForward();printf("\nList , insert after key(4) : ");insertAfter(4,7,13);displayForward();printf("\nList , after delete key(4) : ");delete(4);displayForward();}
Output
List (First to Last):
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
List (Last to first):
[ (1,10) (2,20) (3,30) (4,1) (5,40) (6,56) ]
List , after deleting first record:
[ (5,40) (4,1) (3,30) (2,20) (1,10) ]
List , after deleting last record:
[ (5,40) (4,1) (3,30) (2,20) ]
List , insert after key(4) :
[ (5,40) (4,1) (4,13) (3,30) (2,20) ]
List , after delete key(4) :
[ (5,40) (4,13) (3,30) (2,20) ]
A linked list is a linear data structure which can store a collection of “nodes” connected together via links i.e. pointers. Linked lists nodes are not stored at a contiguous location, rather they are linked using pointers to the different memory locations. A node consists of the data value and a pointer to the address of the next node within the linked list.
A linked list is a dynamic linear data structure whose memory size can be allocated or de-allocated at run time based on the operation insertion or deletion, this helps in using system memory efficiently. Linked lists can be used to implment various data structures like a stack, queue, graph, hash maps, etc.
A linked list starts with a head node which points to the first node. Every node consists of data which holds the actual data (value) associated with the node and a next pointer which holds the memory address of the next node in the linked list. The last node is called the tail node in the list which points to null indicating the end of the list.
Linked Lists vs Arrays
In case of arrays, the size is given at the time of creation and so arrays are of fixed lenghth where as Linked lists are dynamic in size and any number of nodes can be added in the linked lists dynamically. An array can accommodate similar types of data types where as linked lists can store various nodes of different data types.
Types of Linked List
Following are the various types of linked list.
Singly Linked Lists
Singly linked lists contain two “buckets” in one node; one bucket holds the data and the other bucket holds the address of the next node of the list. Traversals can be done in one direction only as there is only a single link between two nodes of the same list.
Doubly Linked Lists
Doubly Linked Lists contain three “buckets” in one node; one bucket holds the data and the other buckets hold the addresses of the previous and next nodes in the list. The list is traversed twice as the nodes in the list are connected to each other from both sides.
Circular Linked Lists
Circular linked lists can exist in both singly linked list and doubly linked list.
Since the last node and the first node of the circular linked list are connected, the traversal in this linked list will go on forever until it is broken.
Basic Operations in Linked List
The basic operations in the linked lists are insertion, deletion, searching, display, and deleting an element at a given key. These operations are performed on Singly Linked Lists as given below −
Insertion − Adds an element at the beginning of the list.
Deletion − Deletes an element at the beginning of the list.
Display − Displays the complete list.
Search − Searches an element using the given key.
Delete − Deletes an element using the given key.
Linked 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 −
Insertion in linked list can be done in three different ways. They are explained as follows −
Insertion at Beginning
In this operation, we are adding an element at the beginning of the list.Algorithm
1. START
2. Create a node to store the data
3. Check if the list is empty
4. If the list is empty, add the data to the node and
assign the head pointer to it.
5. If the list is not empty, add the data to a node and link to the
current head. Assign the head to the newly added node.
6. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}voidmain(){int k=0;insertatbegin(12);insertatbegin(22);insertatbegin(30);insertatbegin(44);insertatbegin(50);printf("Linked List: ");// print listprintList();}
Output
Linked List:
[ 50 44 30 22 12 ]
Insertion at Ending
In this operation, we are adding an element at the ending of the list.Algorithm
1. START
2. Create a new node and assign the data
3. Find the last node
4. Point the last node to new node
5. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}voidinsertatend(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;structnode*linkedlist = head;// point it to old first nodewhile(linkedlist->next !=NULL)
linkedlist = linkedlist->next;//point first to new first node
linkedlist->next = lk;}voidmain(){int k=0;insertatbegin(12);insertatend(22);insertatend(30);insertatend(44);insertatend(50);printf("Linked List: ");// print listprintList();}
Output
Linked List:
[ 12 22 30 44 50 ]
Insertion at a Given Position
In this operation, we are adding an element at any position within the list.Algorithm
1. START
2. Create a new node and assign data to it
3. Iterate until the node at position is found
4. Point first to new first node
5. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}voidinsertafternode(structnode*list,int data){structnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;
lk->next = list->next;
list->next = lk;}voidmain(){int k=0;insertatbegin(12);insertatbegin(22);insertafternode(head->next,30);printf("Linked List: ");// print listprintList();}
Output
Linked List:
[ 22 12 30 ]
Linked List – 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.
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 in linked lists is also performed in three different ways. They are as follows −
Deletion at Beginning
In this deletion operation of the linked, we are deleting an element from the beginning of the list. For this, we point the head to the second node.Algorithm
1. START
2. Assign the head pointer to the next node in the list
3. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}voiddeleteatbegin(){
head = head->next;}intmain(){int k=0;insertatbegin(12);insertatbegin(22);insertatbegin(30);insertatbegin(40);insertatbegin(55);printf("Linked List: ");// print listprintList();deleteatbegin();printf("\nLinked List after deletion: ");// print listprintList();}
Output
Linked List:
[ 55 40 30 22 12 ]
Linked List after deletion:
[ 40 30 22 12 ]
Deletion at Ending
In this deletion operation of the linked, we are deleting an element from the ending of the list.Algorithm
1. START
2. Iterate until you find the second last element in the list.
3. Assign NULL to the second last element in the list.
4. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}voiddeleteatend(){structnode*linkedlist = head;while(linkedlist->next->next !=NULL)
linkedlist = linkedlist->next;
linkedlist->next =NULL;}voidmain(){int k=0;insertatbegin(12);insertatbegin(22);insertatbegin(30);insertatbegin(40);insertatbegin(55);printf("Linked List: ");// print listprintList();deleteatend();printf("\nLinked List after deletion: ");// print listprintList();}
Output
Linked List:
[ 55 40 30 22 12 ]
Linked List after deletion:
[ 55 40 30 22 ]
Deletion at a Given Position
In this deletion operation of the linked, we are deleting an element at any position of the list.Algorithm
1. START
2. Iterate until find the current node at position in the list.
3. Assign the adjacent node of current node in the list
to its previous node.
4. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}voiddeletenode(int key){structnode*temp = head,*prev;if(temp !=NULL&& temp->data == key){
head = temp->next;return;}// Find the key to be deletedwhile(temp !=NULL&& temp->data != key){
prev = temp;
temp = temp->next;}// If the key is not presentif(temp ==NULL)return;// Remove the node
prev->next = temp->next;}voidmain(){int k=0;insertatbegin(12);insertatbegin(22);insertatbegin(30);insertatbegin(40);insertatbegin(55);printf("Linked List: ");// print listprintList();deletenode(30);printf("\nLinked List after deletion: ");// print listprintList();}
Output
Linked List:
[ 55 40 30 22 12 ]
Linked List after deletion:
[ 55 40 22 12 ]
Linked List – Reversal 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.
Algorithm
Step by step process to reverse a linked list is as follows −
1. START
2. We use three pointers to perform the reversing:
prev, next, head.
3. Point the current node to head and assign its next value to
the prev node.
4. Iteratively repeat the step 3 for all the nodes in the list.
5. Assign head to the prev node.
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}voidreverseList(structnode** head){structnode*prev =NULL,*cur=*head,*tmp;while(cur!=NULL){
tmp = cur->next;
cur->next = prev;
prev = cur;
cur = tmp;}*head = prev;}voidmain(){int k=0;insertatbegin(12);insertatbegin(22);insertatbegin(30);insertatbegin(40);insertatbegin(55);printf("Linked List: ");// print listprintList();reverseList(&head);printf("\nReversed Linked List: ");printList();}
Searching for an element in the list using a key element. This operation is done in the same way as array search; comparing every element in the list with the key element given.
Algorithm
1 START
2 If the list is not empty, iteratively check if the list
contains the key
3 If the key element is not present in the list, unsuccessful
search
4 END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}intsearchlist(int key){structnode*temp = head;while(temp !=NULL){if(temp->data == key){return1;}
temp=temp->next;}return0;}voidmain(){int k=0;insertatbegin(12);insertatbegin(22);insertatbegin(30);insertatbegin(40);insertatbegin(55);printf("Linked List: ");// print listprintList();int ele =30;printf("\nElement to be searched is: %d", ele);
k =searchlist(30);if(k ==1)printf("\nElement is found");elseprintf("\nElement is not found in the list");}
Output
Linked List:
[ 55 40 30 22 12 ]
Element to be searched is: 30
Element is found
Linked List – Traversal Operation
The traversal operation walks through all the elements of the list in an order and displays the elements in that order.
Algorithm
1. START
2. While the list is not empty and did not reach the end of the list,
print the data in each node
3. END
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}voidmain(){int k=0;insertatbegin(12);insertatbegin(22);insertatbegin(30);printf("Linked List: ");// print listprintList();}
Output
Linked List:
[ 30 22 12 ]
Linked List – Complete implementation
Following are the complete implementations of Linked List in various programming languages −
#include <stdio.h>#include <string.h>#include <stdlib.h>structnode{int data;structnode*next;};structnode*head =NULL;structnode*current =NULL;// display the listvoidprintList(){structnode*p = head;printf("\n[");//start from the beginningwhile(p !=NULL){printf(" %d ",p->data);
p = p->next;}printf("]");}//insertion at the beginningvoidinsertatbegin(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;// point it to old first node
lk->next = head;//point first to new first node
head = lk;}voidinsertatend(int data){//create a linkstructnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;structnode*linkedlist = head;// point it to old first nodewhile(linkedlist->next !=NULL)
linkedlist = linkedlist->next;//point first to new first node
linkedlist->next = lk;}voidinsertafternode(structnode*list,int data){structnode*lk =(structnode*)malloc(sizeof(structnode));
lk->data = data;
lk->next = list->next;
list->next = lk;}voiddeleteatbegin(){
head = head->next;}voiddeleteatend(){structnode*linkedlist = head;while(linkedlist->next->next !=NULL)
linkedlist = linkedlist->next;
linkedlist->next =NULL;}voiddeletenode(int key){structnode*temp = head,*prev;if(temp !=NULL&& temp->data == key){
head = temp->next;return;}// Find the key to be deletedwhile(temp !=NULL&& temp->data != key){
prev = temp;
temp = temp->next;}// If the key is not presentif(temp ==NULL)return;// Remove the node
prev->next = temp->next;}intsearchlist(int key){structnode*temp = head;while(temp !=NULL){if(temp->data == key){return1;}
temp=temp->next;}return0;}voidmain(){int k=0;insertatbegin(12);insertatbegin(22);insertatend(30);insertatend(44);insertatbegin(50);insertafternode(head->next->next,33);printf("Linked List: ");// print listprintList();deleteatbegin();deleteatend();deletenode(12);printf("\nLinked List after deletion: ");// print listprintList();insertatbegin(4);insertatbegin(16);printf("\nUpdated Linked List: ");printList();
k =searchlist(16);if(k ==1)printf("\nElement is found");elseprintf("\nElement is not present in the list");}
Output
Linked List:
[ 50 22 12 33 30 44 ]
Linked List after deletion:
[ 22 33 30 ]
Updated Linked List:
[ 16 4 22 33 30 ]
Element is found
