Understanding the types and operations of Linked Lists
Originally published at https://www.niit.com/india/
Linked lists are a collection of linear data formation or nodes whose order is not determined by their location in the memory, but each of the nodes signifies towards the next point in the collection. Altogether these data structures form a sequence.
The form of the node consists of data and links to the subsequent node in the sequence.
A linked list is the most common and simplest data structure. During iteration, this linear data structure offers flexibility, allowing insertion and removal of any element from any position in the link. The only drawback of this structure is that faster access like, random access is not likely feasible. However, more complex forms that can add additional links can allow you to insert or remove links at any random position. To understand linked lists in-depth you can choose to take up the course Professional Program in Full Stack Software Engineering offered by NIIT
Types of linked lists
Types of linked lists are as follows:
● Singly-linked list
● Doubly linked list
● Circular linked list
Singly linked list
In singly-linked lists, the nodes are connected in a sequence where each of the nodes contains a value and address field with the reference of the next subsequent node in the link. It is unidirectional, which simply means that data navigation flows in one single direction.
class Node{
int data; // to store the data
Node *next; // a pointer pointing to the next node in the list
};
In this form of the linked list, the node contains the value and address of the next node, and the next value in the sequence of the last node is NULL. The NULL signifies the end of the linked list. It is the simplest form of a linked list and requires much less space as compared to the other types.
Doubly linked list
In the doubly linked list, there’s an extra memory field to store the address of the last node and the address of the subsequent node in a single element. The basic structure is as follows: address of the previous node-value-address of the next node. It is bidirectional. The data navigation flows from both forward and backward directions.
class Double_LL{
Double_LL *prev; // a pointer to pointing to the previous node in the list
int data; // to store the data of the node
Double_LL *next; // a pointer pointing to the next node in the list
};
The removal and insertion operation is much more efficient than the singly linked list but the number of modifications increases while performing various operations. Due to the doubly linked list structure, it requires much more space as it contains an extra memory to store the address of the previous node.
Circular linked list
The circular linked list does not have null values. It can either be a singly linked list or a doubly-linked list. In the case of doubly-linked lists, the first node contains the reference of the last element as previous and the last node contains the address of the first element as the next. On the other hand, in singly-linked lists, the last node contains the link of the first element.
Its flow of data navigation can be from any point as it has no NULL value, but in this type of structure, you can be stuck in an infinite loop If not traversed properly, as there is no null value to stop the traversing. Performing various operations like reversing is much more complex in a circular linked list as compared to other types.
It is an important data structure if we want to access the data in a loop where a previous node can be easily accessed which is not possible in singly-linked lists.
Basic operations of linked lists.
Insertion: For the addition of nodes at any selected position.
Traversal: To access all nodes one by one.
Deletion: For removal of nodes at any selected position.
Searching: To search any data by value.
Updating: To update a value.
Sorting: To configure nodes in a link according to a specific format.
Merging: To merge any two linked lists.
The explanation of these operations is for singly-linked lists.
Linked lists traversal
Traversal means accessing all the different nodes in a list one after another, starting the access from the top or the head of the list. Then, the next node data is accessed in the sequence until the last node is accessed.
The algorithm to access data in a link is as follows:
void print(Node *head)
{
Node *temp=head;
if(head==NULL)
return;
while(temp!=NULL)
{
cout<<temp->data<<” “;
temp=temp->next;
}
}
Linked list node insertion
It means to add or insert a node at any point in the link. Insertion can be at the beginning, at the end, or any selected position in the link.
When inserting at the beginning of the link it is not important to find the link. If the link is empty then the new node is inserted as the head of the link, and when the new node is added to an existing link the new node replaces it as the head of the link.
Algorithm to insert at the beginning:
void insertBG(Node *head,int val)
{
Node *temp=new Node(val);
if(head==NULL)
head=temp;
else
{
temp->next=head;
head=temp;
}
}
When inserting at the end of the link, the user has to access all the nodes present to find the endpoint. In case the list is empty the inserted node acts as both the first and the last node of the link.
Algorithm to insert at the end:
void insertEND(Node *head,int val)
{
Node *temp=head;
Node *temp1=new Node(val);
if(head==NULL)
head=temp1;
else
{
while(temp->next!=NULL)
temp=temp->next;
temp->next=temp1;
}
}
When inserting at any given position, the link is accessed to find the point where the node is to be added. The new node is inserted after the given position. If the address is not given to the previous node, you can traverse the link to find the desired point.
Algorithm to insert at any selected position:
void insert_POS(Node *head,int pos,int val)
{
Node *temp=head;
for(int i=0;i<pos-2;i++)
temp=temp->next;
Node *temp1=new Node(val); // insert value of the node
temp1->next=temp->next;
temp->next=temp1;
}
Deletion in a linked list
To remove a node from any list there are three steps involved.
First, you have to find the node previous to the node that is to be removed. Then the next pointer of the previous node is changed in the link. The last step is to delete the memory of the removed link. In the case where the first node of the link is to be deleted the head of the link is updated.
Algorithm to delete a node:
void delete_LL(Node *head,int node)
{
if(head==NULL)
return;
Node *temp=head;
for(int i=0;i<node-2;i++)
temp=temp->next;
Node *curr=temp->next; // to point to the node to be deleted
temp->next=curr->next;
curr->next=NULL;
delete curr;
}
Searching for a node in the linked list.
To search for any node given in a list, we need to access the list and find the value given in the node.
Algorithm to search:
bool search(Node *head,int key)
{
if(head==NULL)
return false;
Node *temp=head;
while(temp!=NULL)
{
if(temp->data==key)
return true;
temp=temp->next;
}
return false;
}
Updating a node in a linked list
To update a node in a link, we need to update the value of the first node and set the new value.
Algorithm to update a node value:
void update_data(Node *head,val)
{
if(head==NULL)
return;
Node *temp=head;
while(temp->data!=val)
temp=temp->next;
temp->data=val;
}
Endnote
We hoped you liked this presentation on understanding the various types of operations in Linked lists. If so, do explore NIIT’s Knowledge Centre for similar resources.
