Linked lists are one of the linear data structures like arrays but they are non-linear in storing their elements i.e. they do not store in a continuous manner such as arrays. In this blog we will be talking about:
- What are Linked Lists (Other than the definition)
- Initialization and Traversal
- Important Operations (Insertion && Deletion)
- What are its types
What are Linked Lists?
Linked Lists are linear and non-linear at the same time. With their storage being not in sequential manner, they are non-linear but then how they are counted with other linear data structures like arrays, stacks or queues.
They do store the data at different places in a memory but in a sequential manner. How? They use pointers. With each element they store the pointer to the next element and in this way the elements are stored in a sequential manner but the locations can be far away from the previous element.
But what's the point of storing in such a manner?
Like in arrays, the elements are stored in a sequential manner but the memory is limited and the processes of insertion and deletion takes more time.
And linked list helps in such a way that they have no problem with the memory limitations and is efficient while handling insertion or deletion than arrays.
Initializing && Traversing a Linked List:
We will be making a class for a Node in a Linked List which will have:
Data of the element
Pointer to the next element.
class Node{
public:
int data;
Node* next;
//to introduce new nodes with their data
Node(int x){
data = x;
next = NULL;
}
};
Calling them in the main function:
int main()
{
//Intialising the head element.
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
head->next->next->next->next = new Node(5);
/*
It looks like
1->2->3->4->5->NULL
⬆
(head)
*/
//A temporary node to traverse the linked list
Node* curr = head;
//traversing the linked list
while(curr != NULL){
cout<<curr->data<<" ";
//iterating to the next element
curr = curr->next;
}
return 0;
}
// O/P: 1 2 3 4 5
And that's how you initialize and traverse the Linked List.
It's Operations
Insertion and Deletion are two of the main operations on a Linked List. These operations can be done at three locations in a Linked List:
At the beginning.
At a particular position.
At the end.
➡ Insertion:
⭐At the beginning:
When we are adding an element at the beginning, there are few points to handle:
The new element should have a pointer to next element (former head element).
Changing the head of the list
Example:
Linked List: 1->2->3->4->5, New Element: 6
New Linked List: 6->1->2->3->4->5
In this, we changed new element(6) pointer to next element(1) and head points to 6 now.
Node* insertAtBeginning(Node* head){
//Declaring a new Node
Node* temp = new Node(5);
//Pointer for next element
temp->next = head;
//Making the new element, head of the list
head = temp;
//return the new head;
return head;
}
⭐At particular position:
When we are adding an element at a particular position, there are few points to handle:
Keep the position one less than the desired position to handle pointers.
The new element should have a pointer to next element.
The previous element should now point to the new element.
We keep a count element and current node to add the element in the list.
Example:
Linked List: 1->2->3->4->5 New Element: 6
New Linked List: 1->2->3->6->4->5
In this, we changed new element(6) pointer to next element(4) and previous element(3) points to 6 now.
Node* insertAtPosition(Node* head, int pos){
//Declaring a new Node
Node* temp = new Node(6);
//Node to keep check on current element
Node* curr = head;
//Count to check position
int count = 1;
while(count<pos && curr != NULL){
count++;
curr = curr->next;
}
if(count == pos){
//points to handle
temp->next = curr->next;
curr->next = temp;
}
return head;
}
⭐At the end:
When we are adding an element at the end, there are few points to handle:
The new element should have a pointer to NULL.
The new element should have a pointer to new element.
It's quite similar to the operation of inserting at a particular position.
Example:
Linked List: 1->2->3->4->5 New Element: 6
New Linked List: 1->2->3->4->5->6
In this, we changed new element(6) pointer to NULL and previous element(5) points to 6 now.
Node* insertAtEnd(Node* head){
//Declaring a new Node
Node* temp = new Node(6);
//Node to keep check on current element
Node* curr = head;
//Traversing till 5 only and not to NULL
while(curr->next != NULL){
curr = curr->next;
}
//points to handle
curr->next = temp;
temp->next = NULL;
return head;
}
Now it's time to talk about the Deletion operation at the three positions.
➡ Deletion:
⭐From the beginning:
When we are removing an element from the beginning, there are few points to handle:
The second element should be the head of the linked list now.
Free the memory of first element of the list.
The above can be handled by using a temporary node.
Example:
Linked List: 1->2->3->4->5->6 Element to be deleted: 1
New Linked List: 2->3->4->5->6
In this, we changed head pointer to next element(2) and free memory of 1.
Node* deleteFromBeginning(Node* head){
//Temporary node to keep check on head element
Node* temp = head;
//Move head to next element
head = head->next;
//Free the first node
free(temp);
return head;
}
⭐From particular position:
When we are removing an element from a particular position, there are few points to handle:
Reach the desired element by keep the track of count.
The previous element (of the yet to be deleted element) should now point to the next element.
This can be done by keeping a node to the current and previous element.
Example:
Linked List: 1->2->3->4->5->6 Element to delete: 4
New Linked List: 1->2->3->5->6
In this, we changed previous element(3) pointer to next element(5) and free current element(4) from memory.
Node* deleteFromPosition(Node* head, int pos){
//Node to keep check on current and previous element
Node* curr = head, *prev;
int count = 1;
//traversing the LL to the desired element
while(count<pos && curr->next != NULL){
count++;
//keeping a check on current and previous element
prev = curr;
curr = curr->next;
}
//points to handle
prev->next = curr->next;
free(curr);
return head;
}
⭐From the end:
When we are removing an element from the end, there are few points to handle:
It should be given the same points as deletion from particular position.
The second-last element now points to NULL.
Example:
Linked List: 1->2->3->4->5->6 Element to be deleted: 6
New Linked List: 1->2->3->4->5->NULL
In this, we changed removed element(6) and previous element(5) points to NULL now.
Node* deleteFromEnd(Node* head){
//Node to keep check on current and previous element
Node* curr = head, *prev;
//traversing the LL to the last element
while(curr->next != NULL){
//keeping a check on current and previous element
prev = curr;
curr = curr->next;
}
//points to handle
prev->next = NULL;
free(curr);
return head;
}
Types of Linked Lists
We will talk about two types of Linked Lists:
Doubly Linked Lists
Circular Linked Lists
Doubly Linked Lists: The Linked Lists we have learnt about so far are also called Singly Linked Lists. Now, it gets easy to know what are Doubly Linked Lists. These are the lists with two pointers one pointing to the next element and other to the previous element.
A representation of Doubly Linked List:
1<->2<->3<->4<->5<->6
It's an enhanced version of singly linked lists as now we can move forwards and backwards. In this, we don't have to be at the previous element to insert and delete the desired element, it can be done from both ways unlike singly linked lists.
But it require more space for that extra pointer and the process of insertion or deletion is not as much efficient as in singly linked lists.
- Circular Linked Lists: Circular Linked Lists are Singly Linked Lists only but with last element pointing back to the first element.
1->2->3->4->5->6
⬆ ⬇
⬅ ⬅ ⬅ ⬅ ⬅
As each element always have a successor, one needs to be cautious while traversing them or traversal can go on forever.
Their best use case is in managing computing resources and implementing stacks and queues.
Points to Remember
So, we have covered a lot about Linked Lists, here's a quick summary to revise up the points:
Linked Lists are linear data structures but store elements in a non-linear way.
They use pointers to store elements in sequential manner.
They are efficient than arrays in performing Insertion and Deletion and don't have memory restrictions.
Insertions and Deletion occur at 3 positions:
At the Beginning
At a particular position
At the End
There are 2 types of Linked Lists: Doubly and Circular
Doubly Linked Lists have pointer to the forward and backward elements making it more accessible than Singly Linked Lists.
In Circular Linked Lists, each element has a successor, even the last element. Last element points back to first element.
Now, I believe you are prepared enough to work with operations on Doubly Linked Lists on your own. Just keep in mind to work with pointers on both sides.