There are various types of Linked Lists available that we can implement as per the program requirement. But before understanding the various types of Linked Lists, let’s first understand What is a Linked List? Why did it come into existence? What real-world problems can be solved with the help of this? etc.
What is a Linked List?
The linked list is the linear data structure that contains the collection of nodes. But what is the node? A node consists of two things, are –
- Data
- Pointer to the next node.
In the linked list, each node is pointing to the other to maintain the sequence. A linked List is used to utilize the space in memory.
Why Linked List?
We know about Array Data structure, which contains the sequential data access and each element can be accessed with the help of indexes in the array. And also the limitations of the array are that the size of the array is fixed and it occupies the contiguous memory.
So suppose in the case when the program requires large memory, but that amount of memory is not available sequentially in the memory. Then, in this case, arrays are not very useful. It fails to allocate the memory required by the program.
Consider the above image as the memory, black colour blocks are occupied memory blocks by the programs. So in this case, if my program requires the memory of 8 bytes (blocks) then it is not possible with the array. Because nowhere in memory there are 8 contiguous free blocks available. There are available spaces in the memory, but all are not contiguous.
So that problem can be solved using the help of the linked list. Because it doesn’t require contiguous memory allocation. Instead, it can occupy the block of the memory that is available across different locations in the memory and it stores the pointers that will point to that different memory location to identify the next block.
In the above image, arrows can be considered as the pointer to the next memory location. And that is how the linked list allocates memory. Linked Lists can be grown dynamically and it avoids wastage of space in the memory like in the array. But linked lists are not indexable. This means, like an array, we cannot access any element of a linked list using indexes.
Head and Tail pointer
The Head pointer keeps track of the starting node of the linked list. And the Tail pointer point to the end of the linked list. A tail pointer is a must if we want to insert the node at the end of the list in constant time. Linked lists are not indexable so for inserting any node we need to traverse the whole list to get the location to insert the node. As the pointer modification needs to be done.
A real-world example of uses of Linked List –
Consider an example in which we have to design a song playlist, and in that playlist, songs are to be added dynamically. So, if we use an array here, then that is not a memory-efficient solution. Because we need to predefine the size of the playlist. And the playlist doesn’t need to contain a fixed number of songs.
So what we can do here is, we can create different nodes for each of the song IDs. And then we somehow need to connect these nodes. So we can use a pointer to connect that. So here we can use the concept of the linked list to solve this problem.
The below image shows the high-level idea of the linked list for the playlist of songs.
Types of Linked Lists
There are majorly 3 types of linked lists in the data structures that can be implemented. And that is –
- Singly Linked List.
- Doubly Linked List.
- Circular Linked List.
Every Linked List has its own implementation and functionality. So let’s understand each one in-depth.
1. Singly Linked List
Linked List contains the data and the pointers for pointing to the next memory block. And if that node points to the single next node, then that is a singly linked list. The node structure of the singly linked list can be described as –
Singly Linked List node has two parts of it –
- The Data part contains the data. This data can be of any type, It might be – Integer, Float, Double, String character, or even any custom data type.
- The Next part contains the address of the next node. The type of node address it points to is already defined while creating the structure of the node.
So the linear data structure (singly linked list) is represented in memory as –
The pointer that will point to the first node and last node is there in the stack memory. And the arrow we used to denote the next node is just for understanding. In memory. it actually contains only the address of that particular node, described in the above image.
Singly Linked List Node Definition Structure – Consider the same example that we need to create the playlist of the song. So in the term of a singly linked list. The structure for the linked list of playlists will be –
PlayListNode {
int songID;
PlayListNode *next;
}
This structure is language-independent. Each language has its own way to define custom structure. Like c contains struct. And other programming languages mostly use classes to achieve that.
The above structure describes the Node Playlist that contains the song id that is a data part. And the other one is the pointer of the next node of the playlist node type. That helps to point to the next node for making and ordering between them.
How to implement the structure of this singly linked list in the program?
The linked list contains some pointers, which are – Head and Tail Pointer. For the implementation of this singly linked list, some steps need to be followed. And those are –
- Definition of Node –
- Define the structure of the node.
- Declare a data part. (In our example, its song ID is of integer type).
- Declare a pointer that points to the next node.
- Allocation of memory for the node.
- Perform Operations on the node like –
- Insert a Node.
- Delete a Node.
- Search on the List.
Insertion, Deletion, and Search on the Singly linked list are a little bit different than the array data structure. Because we need to modify some pointers to complete that. So let’s look at some algorithms for the basic two operations on the linked list of Insert and Delete.
Algorithm for Insertion in Singly Linked-List –
- Create a node using the defined structure.
- Assign the data to the data part of the node.
- For the Next pointer,
- Inserting at front – Assign the next pointer to the head node and make the head node point to this new node.
- Inserting at the end – Assign the tail node next pointer point to the new node and make the tail point to the new node and then make the new pointer next node point to null to represent the end of the list.
- Inserting in the middle – Search the position to be inserted and adjust the pointer of new node points to the next location of the position. Ans for the positioning node, make its next pointer point to the new node.
Algorithm for Deletion from Singly Linked-List –
- Search for the node to be deleted.
- If the node wasn’t found then return a message indicating the node was not found.
- If node found –
- Along with searching, use an extra tail pointer that will point to the previous node of the current while searching.
- Adjust the next pointer of that tail pointer to the node to delete the next pointer. And free that node to delete memory.
Now let’s implement this playlist module into the program. In this article, Implementation is done using java. But the algorithm can be implemented in any preferred language.
JAVA Implementation for all functions of Single Linked List:
class PlayListNode{
int songId;
PlayListNode next;
}
public class Main {
//Declaring Head and tail pointer to null because at start no node present.
static PlayListNode head = null, tail = null;
//Method to Insert Node at Start
public static void insertNodeBegining(int songId){
//Creating new Node and Adjusting pointers accordingly.
PlayListNode newNode = new PlayListNode();
newNode.songId = songId;
if(head == null){
//If it's the first node.
head = tail = newNode;
newNode.next = null;
}else{
newNode.next = head;
head = newNode;
}
System.out.println(" Song added at the front in the playlist." );
}
//Method to Insert Node at End
public static void insertNodeEnd(int songId){
//Creating new Node and Adjusting pointers accordingly.
PlayListNode newNode = new PlayListNode();
newNode.songId = songId;
newNode.next = null;
if(head == null){
//If it's first node.
head = tail = newNode;
}else{
tail.next = newNode;
tail = newNode;
}
System.out.println(" Song added at the end in the playlist." );
}
//Method to Insert Node in Between.
public static void insertNodeBetween(int after, int songId){
PlayListNode temp = head;
boolean found = false;
//Searching for location in list.
while(temp != null){
if(temp.songId == after){
found = true;
break;
}
temp = temp.next;
}
//Terminating the method if position is not found.
if(!found){
System.out.println(" No sond exist with id "+ songId +" to insert after.");
return;
}
//Creating new node and adjusting the pointer.
PlayListNode newNode = new PlayListNode();
newNode.songId = songId;
newNode.next = temp.next;
temp.next = newNode;
System.out.println(" Song added after " + after + " in the playlist." );
}
//Method to Search Node in List.
public static void searchNode(int songId){
PlayListNode temp = head;
boolean found = false;
//Searching for node in the list.
while(temp != null){
if(temp.songId == songId){
found = true;
break;
}
temp = temp.next;
}
//Terminating the method if node is not found.
if(!found){
System.out.println(" Song doesn't exist in playlist.");
return;
}
//Printing the message if node is found.
System.out.println(" Song ID "+ songId+ " found in the playlist." );
}
//Method to delete Node from the List.
public static void deleteNode(int songId){
PlayListNode nodeToDelete = head, prev = null;
boolean found = false;
//Searching for node in the list.
while(nodeToDelete != null){
if(nodeToDelete.songId == songId){
found = true;
break;
}
prev = nodeToDelete;
nodeToDelete = nodeToDelete.next;
}
//Terminating the method if node not found.
if(!found){
System.out.println(" Song doesn't exist in playlist.");
return;
}
//Checking if the node to delete is the first node
if(prev != null){
//Adjusting pointers and tail pointer as well if the to delete
//node is the last node.
prev.next = nodeToDelete.next;
if(nodeToDelete == tail)
tail = prev;
}
else{
//Adjusting the pointer as node is the head
nodeToDelete = nodeToDelete.next;
head = nodeToDelete;
}
System.out.println(" Song "+ songId +" deleted from playlist.");
}
//Method to print the available node from the List.
public static void print(){
//Terminating the function if no node is present.
if(head == null){
System.out.println(" No playlist created...");
return;
}
//Printing the nodes in the list.
PlayListNode temp = head;
System.out.println(" Songs in the playlist are - ");
while(temp != null){
System.out.println(" Song = " + temp.songId);
temp = temp.next;
}
}
public static void main(String args[]) {
//Calling the Methods to insert, delete, search and print.
insertNodeBegining(5);
insertNodeBegining(4);
insertNodeBegining(3);
insertNodeBegining(2);
insertNodeBegining(1);
insertNodeEnd(6);
insertNodeBetween(3, 7);
print();
deleteNode(7);
deleteNode(3);
deleteNode(9);
searchNode(5);
print();
}
}
Run this code on InterviewBit Java Compiler
Output For this program is –
Song added at the front in the playlist. Song added at the front in the playlist. Song added at the front in the playlist. Song added at the front in the playlist. Song added at the front in the playlist. Song added at the end in the playlist. Song added after 3 in the playlist. Songs in the playlist are - Song = 1 Song = 2 Song = 3 Song = 7 Song = 4 Song = 5 Song = 6 Song 7 deleted from playlist. Song 3 deleted from playlist. Song doesn't exist in playlist. Song ID 5 is found in the playlist. Songs in the playlist are - Song = 1 Song = 2 Song = 4 Song = 5 Song = 6
2. Double Linked List
We have seen that in the singly linked list we have the data part that contains data and the pointer part that will point to the next node. Now consider a scenario where we want to traverse the singly linked list in the reverse direction, then we found that a singly linked list can’t achieve that. Because in a singly linked list it can only traverse in the forward direction. So using a singly linked list if we want to achieve that, then we have to traverse again from start and reach that node, which is highly inefficient.
So how do we fix that issue? So with the help of a doubly-linked list, this issue can be fixed.
Doubly Linked List contains all the properties of a singly linked list with an extra pointer that will point to the previous node. So the node structure of the singly linked list is-
A doubly linked list has 3 properties –
- The data part contains the data. And just like the singly linked list, it can contain any type of data, predefined or user-defined.
- The pointer to the next node contains the address of the next node, which helps point to the next node in the sequence to maintain the ordering. It is the same as the singly linked list.
- Pointer to the previous node is the new property added to the doubly linked list, And this contains the address of the previous node. With the help of this pointer, the problem with the singly linked list was solved. If the node itself is the first node, then the previous pointer contains a null address.
So the memory representation of the doubly linked list will be as-
In the above image, we can see that each node except the first and last will have two incoming pointers and 2 outgoing pointers. As described in the singly linked list that node only contains the address. Making an arrow is just our visual representation.
Doubly Linked List Node Definition Structure – Consider the same example that we need to create the playlist of the song. So in the term of a doubly linked list. The structure for the linked list of playlists will be –
PlayListNode {
int songID;
PlayListNode *next;
PlayListNode *previous;
}
This structure is also language-independent. As already described in the Singly linked-list section.
The above structure describes the Node Playlist that contains the song id that is a data part. And the other one is the pointer of the next node of the playlist node type and as well as the previous node of the playlist created.
We have implemented a playlist module with a singly linked list, In but, it has a glitch that we can’t go backwards from any node. So now let’s solve that issue with the help of a doubly linked list implementation.
How to implement the structure of this doubly linked list in the program?
Like we have already implemented the singly linked list, the doubly linked list will also be the same except for some more pointer modifications. So the steps are the same as the singly linked list. The steps are –
- Allocate the Memory of the node and assign the value to it.
- Adjust pointers according to the operations. (Insert / Delete / Search) etc.
Algorithm to implement the Doubly Linked List –
- Create a node using the defined structure.
- Assign the data to the data part of the node.
- For the Next pointer,
- Inserting at front – Assign the next pointer to the head node and make the head node point to this new node and make the new node’s previous point null.
- Inserting at the end – Assign the tail node next pointer point to the new node.
- Then make the new node’s previous pointer point to the tail node.
- Then make the tail point to the new node.
- Make the new pointer next node point to null to represent the end of the list.
- Inserting in the middle – Search the positioning node to be inserted and adjust the pointer of the new node points to the next location of the position.
- Make position next points to the new node.
- New node previous points to the positioning node.
- Make the new node next’s previous point to the new node.
Algorithm for Deletion from Doubly Linked List –
- Search for the node to be deleted from the list.
- If the node wasn’t found then return a message indicating the node was not found.
- If a node is found then we need to do some pointer modification. And the modification will be-
- Pointing node to delete the previous node’s next pointer point to the node to delete the next pointer node.
- Pointer node to delete next node’s previous pointer point to the node to delete the previous node.
- Free the current node to delete the node from the memory.
We have read about the doubly linked list and its implementation algorithm. Now let’s implement this algorithm in the song playlist feature program. Again, I am implementing algorithms in the Java language. But the algorithm can be applied to any language of your choice.
Doubly Linked List Implementation in Java:
class PlayListNode{
int songId;
PlayListNode next;
PlayListNode prev;
}
public class Main {
//Declaring Head and tail pointer to null because at start no node present.
static PlayListNode head = null, tail = null;
//Method to Insert Node at Start
public static void insertNodeBegining(int songId){
//Creating new Node and Adjusting pointers accordingly.
PlayListNode newNode = new PlayListNode();
newNode.songId = songId;
if(head == null){
//If it's first node.
head = tail = newNode;
newNode.next = null;
newNode.prev = null;
}else{
newNode.next = head;
head.prev = newNode;
head = newNode;
newNode.prev = null;
}
System.out.println(" Song added at the front in the playlist." );
}
//Method to Insert Node at End
public static void insertNodeEnd(int songId){
//Creating new Node and Adjusting pointers accordingly.
PlayListNode newNode = new PlayListNode();
newNode.songId = songId;
newNode.next = null;
if(head == null){
//If it's the first node.
head = tail = newNode;
newNode.prev = null;
}else{
newNode.prev = tail;
tail.next = newNode;
tail = newNode;
}
System.out.println(" Song added at the end in the playlist." );
}
//Method to Insert Node in Between.
public static void insertNodeBetween(int after, int songId){
PlayListNode temp = head;
boolean found = false;
//Searching for location in list.
while(temp != null){
if(temp.songId == after){
found = true;
break;
}
temp = temp.next;
}
//Terminating the method if position is not found.
if(!found){
System.out.println(" No sond exist with id "+ songId +" to insert after.");
return;
}
//Creating new nodes and adjusting the pointer.
PlayListNode newNode = new PlayListNode();
newNode.songId = songId;
newNode.next = temp.next;
newNode.prev = temp;
temp.next = newNode;
if(temp != tail)
newNode.next.prev = newNode;
else
tail = newNode;
System.out.println(" Song added after " + after + " in the playlist." );
}
//Method to Search Node in List.
public static void searchNode(int songId){
PlayListNode temp = head;
boolean found = false;
//Searching for node in the list.
while(temp != null){
if(temp.songId == songId){
found = true;
break;
}
temp = temp.next;
}
//Terminating the method if node is not found.
if(!found){
System.out.println(" Song dosen't exist in playlist.");
return;
}
//Printing the message if node is found.
System.out.println(" Song ID "+ songId+ " found in the playlist." );
}
//Method to delete Node from the List.
public static void deleteNode(int songId){
PlayListNode nodeToDelete = head;
boolean found = false;
//Searching for node in list.
while(nodeToDelete != null){
if(nodeToDelete.songId == songId){
found = true;
break;
}
nodeToDelete = nodeToDelete.next;
}
//Terminating the method if node not found.
if(!found){
System.out.println(" Song doesn't exist in playlist.");
return;
}
//Checking if the node to delete is the first node
if(nodeToDelete != head){
//Adjusting pointers and tail pointer as well if the to delete
//node is the last node.
nodeToDelete.prev.next = nodeToDelete.next;
if(nodeToDelete != tail)
nodeToDelete.next.prev = nodeToDelete.prev;
else
tail = nodeToDelete.prev;
}
else{
//Adjusting the pointer as node is the head
nodeToDelete.next.prev = null;
head = nodeToDelete.next;
}
System.out.println(" Song "+ songId +" deleted from playlist.");
}
//Method to print the available node from the List.
public static void print(){
//Terminating the function if no node is present.
if(head == null){
System.out.println(" No playlist created...");
return;
}
//Printing the nodes in the list.
PlayListNode temp = head;
System.out.println(" Songs in the playlist are - ");
while(temp != null){
System.out.println(" Song = " + temp.songId);
temp = temp.next;
}
}
public static void main(String args[]) {
//Calling the Methods to insert, delete, search and print.
insertNodeBegining(5);
insertNodeBegining(4);
insertNodeBegining(3);
insertNodeBegining(2);
insertNodeBegining(1);
insertNodeEnd(6);
insertNodeBetween(3, 7);
print();
deleteNode(7);
deleteNode(3);
deleteNode(9);
searchNode(5);
print();
}
}
Run Code on InterviewBit
Output
Song added at the front in the playlist. Song added at the front in the playlist. Song added at the front in the playlist. Song added at the front in the playlist. Song added at the front in the playlist. Song added at the end in the playlist. Song added after 3 in the playlist. Songs in the playlist are - Song = 1 Song = 2 Song = 3 Song = 7 Song = 4 Song = 5 Song = 6 Song 7 deleted from playlist. Song 3 deleted from playlist. Song doesn't exist in playlist. Song ID 5 is found in the playlist. Songs in the playlist are - Song = 1 Song = 2 Song = 4 Song = 5 Song = 6
3. Circular Linked List
The circular linked list itself circularly states that list. This means the last node of the list will be connected to the first node. As described in the below image.
While we are understanding the linked list types with the example of the feature module of the song playlist. In the real-world application, we often see those playlist songs play on loop. This means after playing the last song of the playlist, the song starts from the beginning. That is the place where a circular linked list can be used to build this kind of feature.
So we can define the circular linked list as the type of linked list in which the last node of the list is connected with the first node, and for recognizing where the list starts, the head pointer is there that points to the first node in the circular linked list.
Designing Circular Linked List
Circular linked behaves exactly like the other two linked lists (Singly and Doubly), except for the circular behaviour of circular linked lists. So we can design the circular linked list using these two basic linked list types. So we can say that a circular linked list can be of 2 types –
- Singly Circular Linked List.
- Doubly Circular Linked List.
Singly Circular Linked List –The behaviour of a singly linked list can easily be applicable here with the specialization of circular nature. So the steps we have followed to build the singly linked list will be the same. But only modification can be done on the pointer of the last node pointing to the first node. Example –
Implementation of Singly Circular Linked List into the program.
- Create node structure (same as a singly linked list).
- Allocate Memory to the node.
- Perform Operations –
- Insert.
- Update.
- Delete.
Algorithm for Insertion in Circular Singly Linked-List-
- Create a node.
- Initialize the value in the data part of the node.
- Adjust the pointers –
- If a new node inserted is the first node then make the head pointer point to the node and in the pointer part, point the node with itself.
- Insertion at Front or End – Insertion at If a new node wanted to be inserted at the beginning, then make the new node’s next pointer point to the head and the head will now point to the new node, And the tail node’s next pointer points to the head node (or new node).
The behaviour for insertion at the front or end will be the same because of the circular nature.
- Insertion in Between – In the new node wanted to be inserted after any node then-
- First search for the position of the node.
- Then mark the new node’s next pointer and point to the position’s next pointer.
- Mark position’s node next pointer points to the new node.
Note: This is the algorithm that can be implemented in any programming language and while implementing the program, we might need to take care of the additional pointers. And that we will see in the code implementation.
Algorithm for Deletion of Node from Circular linked List-
- Search for the node (node to delete).
- If the node to delete is not found then return a message indicating the error.
- Else make the node delete the previous next pointer point to the node to delete’s next pointer. And adjust the head and tail pointer accordingly.
Java Program for Implementation of Circular Singly Linked List –
class PlayListNode{
int songId;
PlayListNode next;
}
public class Main {
//Declaring Head and tail pointer to null because at start no node present.
static PlayListNode head = null, tail = null;
//Method to Insert Node at Start
public static void insertNodeBeginingOrEnd(int songId){
//Creating new Node and Adjusting pointers accordingly.
PlayListNode newNode = new PlayListNode();
newNode.songId = songId;
//If the Playlist is not created.
if(head == null){
//If it's the first node.
head = tail = newNode;
newNode.next = head;
}
//If only 1 node is there in the playlist.
else if(tail == head){
newNode.next = head;
head.next = newNode;
tail = newNode;
}
//Otherwise
else{
newNode.next = head;
tail.next = newNode;
tail = newNode;
}
System.out.println(" Song added in the playlist." );
}
//Method to Insert Node in Between.
public static void insertNodeBetween(int after, int songId){
PlayListNode temp = head;
boolean found = false;
//Searching for location in list.
do{
if(temp.songId == after){
found = true;
break;
}
temp = temp.next;
}while(temp != head);
//Terminating the method if position is not found.
if(!found){
System.out.println(" No sond exist with id "+ songId +" to insert after.");
return;
}
//Creating new node and adjusting the pointer.
PlayListNode newNode = new PlayListNode();
newNode.songId = songId;
newNode.next = temp.next;
temp.next = newNode;
System.out.println(" Song added after " + after + " in the playlist." );
}
//Method to Search Node in List.
public static void searchNode(int songId){
PlayListNode temp = head;
boolean found = false;
//Searching for node in list.
do{
if(temp.songId == songId){
found = true;
break;
}
temp = temp.next;
}while(temp != head);
//Terminating the method if node is not found.
if(!found){
System.out.println(" Song dosen't exist in playlist.");
return;
}
//Printing the message if node is found.
System.out.println(" Song ID "+ songId+ " found in the playlist." );
}
//Method to delete Node from the List.
public static void deleteNode(int songId){
PlayListNode nodeToDelete = head, prev = tail;
boolean found = false;
//Searching for node in the list.
do{
if(nodeToDelete.songId == songId){
found = true;
break;
}
prev = nodeToDelete;
nodeToDelete = nodeToDelete.next;
}while(nodeToDelete != head);
//Terminating the method if node is not found.
if(!found){
System.out.println(" Song doesn't exist in playlist.");
return;
}
//Checking if the node to delete is the first node
if(nodeToDelete != head){
//Adjusting pointers and tail pointer as well if the to delete
//node is the last node.
prev.next = nodeToDelete.next;
if(nodeToDelete == tail)
tail = prev;
}
else{
//Adjusting the pointer as node is the head
nodeToDelete = nodeToDelete.next;
head = nodeToDelete;
}
System.out.println(" Song "+ songId +" deleted from playlist.");
}
//Method to print the available node from the List.
public static void print(){
//Terminating the function if no node is present.
if(head == null){
System.out.println(" No playlist created...");
return;
}
//Printing the nodes in the list.
PlayListNode temp = head;
System.out.println(" Songs in the playlist are - ");
do{
System.out.println(" Song = " + temp.songId);
temp = temp.next;
}while(temp != head);
}
public static void main(String args[]) {
//Calling the Methods to insert, delete, search and print.
insertNodeBeginingOrEnd(5);
insertNodeBeginingOrEnd(4);
insertNodeBeginingOrEnd(3);
insertNodeBeginingOrEnd(2);
insertNodeBeginingOrEnd(1);
insertNodeBetween(4, 6);
insertNodeBetween(3, 7);
print();
deleteNode(7);
deleteNode(3);
deleteNode(9);
searchNode(5);
print();
}
}
Run Code on InterviewBit
Output –
Song added to the playlist. Song added to the playlist. Song added to the playlist. Song added to the playlist. Song added to the playlist. Song added after 4 in the playlist. Song added after 3 in the playlist. Songs in the playlist are - Song = 5 Song = 4 Song = 6 Song = 3 Song = 7 Song = 2 Song = 1 Song 7 deleted from playlist. Song 3 deleted from playlist. Song doesn't exist in playlist. Song ID 5 is found in the playlist. Songs in the playlist are - Song = 5 Song = 4 Song = 6 Song = 2 Song = 1
Circular Doubly Linked List
We have already seen above the doubly linked list. And as well as also read about the property of the circular linked list. So the circular linked list can also be implemented with the help of a doubly linked list. Like in the singly circular linked list we have taken a tail pointer that points to one node previous to the head, It is not required here. For implementation, we can modify the pointers only with the usual implementation of a doubly-linked list. Example –
Implementation of Circular Doubly Linked-List –
- Create node structure (same as a doubly-linked list).
- Allocate Memory to the node.
- Perform Operations –
- Insert.
- Update.
- Delete.
Algorithm for Insertion in Circular Doubly Linked-List –
- Create a node with a defined structure.
- Allocate memory and initialize the value in the data part of the node.
- Adjust the pointers-
- If the new node is the first node then make a new node next and the previous pointer points to itself and makes a head and tail point to the new node.
- Insertion at Front or Rear –
- Mark the new node next pointer points to the head.
- Mark the new node previous pointer points to the head’s previous node.
- Mark new (node previous node) nxt pointer points to the new node.
- Mark head node previous pointer points to the new node.
- Mark a new node as head.
- Insertion at Middle – Search for the position of the node to be inserted.
- Mark the new node next pointer point to position’s next node.
- Mark (position’s next node) previous pointer point to the new node.
- Mark Position’s node next pointer points to the new node.
- Mark new node previous pointer point to the previous pointer.
Algorithm for Deletion from Circular Doubly Linked-List –
- Search for the node to delete.
- If the node is not found then return the message indicating the error.
- If a node is found then adjust the pointers-
- Mark (node to delete the previous node) next pointer point to the node to delete next pointer.
- Mark (node to delete next node) previous pointer point to the node to delete the previous pointer.
- Free the node to delete the node.
Java Program Implementation of Circular Doubly Linked List:
class PlayListNode{
int songId;
PlayListNode next;
PlayListNode prev;
}
public class Main {
//Declaring Head and tail pointer to null because at start no node present.
static PlayListNode head = null, tail = null;
//Method to Insert Node at Start
public static void insertNodeBeginingOrEnd(int songId){
//Creating new Node and Adjusting pointers accordingly.
PlayListNode newNode = new PlayListNode();
newNode.songId = songId;
if(head == null){
//If it's first node.
head = tail = newNode;
newNode.next = newNode;
newNode.prev = newNode;
}
else if(head.next == head){
newNode.next = head;
newNode.prev = head;
head.prev = newNode;
head.next = newNode;
head = newNode;
}
else{
newNode.next = head;
newNode.prev = head.prev;
head.prev = newNode;
(newNode.prev).next = newNode;
head = newNode;
}
System.out.println(" Song added at the front in the playlist." );
}
//Method to Insert Node in Between.
public static void insertNodeBetween(int after, int songId){
PlayListNode temp = head;
boolean found = false;
//Searching for location in list.
do{
if(temp.songId == after){
found = true;
break;
}
temp = temp.next;
}while(temp != head);
//Terminating the method if position not found.
if(!found){
System.out.println(" No sond exist with id "+ songId +" to insert after.");
return;
}
//Creating new node and adjusting the pointer.
PlayListNode newNode = new PlayListNode();
newNode.songId = songId;
newNode.next = temp.next;
newNode.prev = temp;
(newNode.next).prev = newNode;
temp.next = newNode;
System.out.println(" Song added after " + after + " in the playlist." );
}
//Method to Search Node in List.
public static void searchNode(int songId){
PlayListNode temp = head;
boolean found = false;
//Searching for node in list.
do{
if(temp.songId == songId){
found = true;
break;
}
temp = temp.next;
}while(temp != head);
//Terminating the method if node not found.
if(!found){
System.out.println(" Song doesn't exist in playlist.");
return;
}
//Printing the message if node found.
System.out.println(" Song ID "+ songId+ " found in the playlist." );
}
//Method to delete Node from the List.
public static void deleteNode(int songId){
PlayListNode nodeToDelete = head;
boolean found = false;
//Searching for node in the list.
do{
if(nodeToDelete.songId == songId){
found = true;
break;
}
nodeToDelete = nodeToDelete.next;
}while(nodeToDelete != head);
//Terminating the method if node is not found.
if(!found){
System.out.println(" Song doesn't exist in playlist.");
return;
}
//Checking if the node to delete is the first node
(nodeToDelete.prev).next = nodeToDelete.next;
(nodeToDelete.next).prev = nodeToDelete.prev;
if(nodeToDelete == head)
head = nodeToDelete.next;
System.out.println(" Song "+ songId +" deleted from playlist.");
}
//Method to print the available node from the List.
public static void print(){
//Terminating the function if no node is present.
if(head == null){
System.out.println(" No playlist created...");
return;
}
//Printing the nodes in the list.
PlayListNode temp = head;
System.out.println(" Songs in the playlist are - ");
do{
System.out.println(" Song = " + temp.songId);
temp = temp.next;
}while(temp != head);
}
public static void main(String args[]) {
//Calling the Methods to insert, delete, search and print.
insertNodeBeginingOrEnd(5);
insertNodeBeginingOrEnd(4);
insertNodeBeginingOrEnd(3);
insertNodeBeginingOrEnd(2);
insertNodeBeginingOrEnd(1);
insertNodeBetween(2, 8);
insertNodeBetween(3, 7);
print();
deleteNode(7);
deleteNode(3);
deleteNode(9);
searchNode(5);
print();
}
}
Run Code on InterviewBit
Output
Song added to the playlist. Song added to the playlist. Song added to the playlist. Song added to the playlist. Song added to the playlist. Song added after 4 in the playlist. Song added after 3 in the playlist. Songs in the playlist are - Song = 5 Song = 4 Song = 6 Song = 3 Song = 7 Song = 2 Song = 1 Song 7 deleted from playlist. Song 3 deleted from playlist. Song doesn't exist in the playlist. Song ID 5 is found in the playlist. Songs in the playlist are - Song = 5 Song = 4 Song = 6 Song = 2 Song = 1
Algorithm Analysis of All Types of Linked Lists
We have seen the three different types of Linked List, and Basic operations on the linked list. Now let’s analyze the time complexity for the operations on the linked list. And this is applicable to all the 3 types of linked lists.
- Insertion – For Inserting the element in the Linked list, We perform mainly 2 operations.
- Creating a node with the value.
- Adjusting the pointers.
if we insert nodes either on the Front or the Rear side. Then using the head and tail pointer we did this in the constant operation by just adjusting the pointers.
But if we want to insert the node in the middle of the linked list, then first we need to search for the element after which we want to insert the node. And then adjust the pointers.
So, this search can take the most linear time in case the node we are searching is present in the last.
So with this theory, we can conclude that Insertion at the front or rear takes constant time i.e, O(1). And Insertion at the middle takes O(n) time.
- Searching – If you want to search an element then we must travel the entire linked list until the element wasn’t found or until the end of the linked list so we can say that searching can take O(n) time.
- Deletion – Deletion in the linked list is just the adjustment of the pointers and releasing of the occupied memory of the node. And for deletion, we need to search for the node that you want to delete. We know that searching can take linear time, so we can conclude that deletion can take almost O(n) times.
Conclusion
A linked list is the physical and linear data structure. We call it the physical data structure because this format is actually stored in the memory. A linked list can easily solve the problems of the array data structure. All the 3 different types of linked lists are implemented based on the requirement of the program.
Like we have taken the example by developing the playlist function module and implementing it with all different types of linked lists. But in real-world implementation in the applications, we can choose the most appropriate type.
Linked List Coding Problems
- Detect Loop in Linked List
- Reverse a Linked List
- Delete Node in a Linked List
- Intersection of Two Linked Lists
- Add Two Numbers Represented by Linked Lists
