Intended Audience
As promised, In this blog we will be revising linked list data structure.The blog is not for complete beginners . This blog will be suitable for someone who is revisiting linked list.
Advantages Of Linked List Over Arrays
Ease of insertion and deletion.
Arrays store the data contiguously which can lead to external fragmentation.
ADT
Main operations :-
insert an element to the list
deleting the element at specified position in the list
Auxiliary operations :-
count the number of elements in the list
find nth node on the list
delete complete list
Issues with LL
Access time of linked list is O(N) while that of array is O(1).
Arrays are contiguous block, so any element will be physically near it's neighbour.This greatly benefits from modern CPU caching methods.
LL wastes memory in terms of extra reference points.
Comparisions of LL, Arrays, Dynamic Arrays
Singly linked list
This is the list we imagine when we hear the word "linked list".
The node in this linked list contains the data element and the pointer to the next node. The last node points to null.
The node class for singly linked list looks like
class Node{
int data; //The data to be stored
Node* next; // The reference to the next node
public:
Node(int val = 0){
this->data = val; //initialised to 0
this->next = nullptr; // intialised to nullptr
}
};
Let's make a complete linked list data-structure
#include <bits/stdc++.h>
using namespace std;
class Node{
int data; //The data to be stored
Node* next; // The reference to the next node
public:
friend class ll;
Node(int val = 0){
this->data = val; //initialised to 0
this->next = nullptr; // intialised to nullptr
}
};
class ll{
Node* head;
int size;
public:
ll(){
//initialisation
this->head = nullptr;
this->size = 0;
}
void Insert(int data,int pos){ //pos as per 0-based indexing
//TC = O(N)
if(pos > size){
cout << "Can't insert data (Invalid position)" << endl;
return;
}
Node* newNode = new Node(data);
if(size == 0){
//Handling when ll is empty
head = newNode;
size++;
return;
}
int currPtr = 0;
Node* curr = head;
Node* prev = nullptr;
//iterating till currPtr reached the pos
while(currPtr < pos){
prev = curr;
curr = curr->next;
currPtr++;
}
if(prev){
prev->next = newNode;
}
else{
//Handling the edge case when pos = 0 because prev will be null
head = newNode;
}
newNode->next = curr;
size++;
return;
}
int Delete (int pos){
//TC = O(N)
if(pos > size){
cout << "Can't delete data (Invalid position)" << endl;
return -1;
}
if(pos == 0){
Node* temp = head;
int val = temp->data;
head = head->next;
delete(temp);
size--;
return val;
}
int currPtr = 0;
Node* curr = head;
Node* prev = nullptr;
while(currPtr < pos){
prev = curr;
curr = curr->next;
currPtr++;
}
int val = (curr)?curr->data:-1;
if(curr){
prev->next = curr->next;
delete(curr);
}
else{
prev->next = nullptr;
}
size--;
return val;
}
void print(){
Node* temp = head;
while(temp){
cout<<temp->data<<" ";
temp = temp->next;
}cout<<endl;
}
};
int main() {
ll l1;
l1.Insert(10,0);
l1.Insert(20,1);
l1.Insert(40,2);
l1.Insert(30,0);
l1.Delete(0);
l1.print();
return 0;
}
Doubly Linked List
The node in this type of linked list contains the data element and the pointer to the next node.Also it contains one more pointer which points towards the prev element.
In singly linkedlist we could go only in one direction but in doubly linked list we can move in two direction.
The node of this linkedlist looks like :-
class Node{
int data; //The data to be stored
Node* next; // The reference to the next node
Node* prev; // The reference to the prev node
public:
Node(int val = 0){
this->data = val; //initialised to 0
this->next = nullptr; // intialised to nullptr
this->prev = nullptr; //initialised to nullptr
}
};
Implementing doubly linked list data structure is even more easier than singly linked list. In this case while deleting we do not need to keep track of the prev node. And insertion will be same as singly linked list with slight modification to adjust the prev pointer.
// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
class Node{
int data; //The data to be stored
Node* next; // The reference to the next node
Node* prev; // The reference to the previous node
public:
friend class dll;
Node(int val = 0){
this->data = val; //initialised to 0
this->next = nullptr; // intialised to nullptr
this->prev = nullptr; // intialised to nullptr
}
};
class dll{
Node* head;
int size;
public:
dll(){
//initialisation
this->head = nullptr;
this->size = 0;
}
void Insert(int data,int pos){ //pos as per 0-based indexing
if(pos > size){
cout << "Can't insert data (Invalid position)" << endl;
return;
}
Node* newNode = new Node(data);
if(size == 0){
//Handling when ll is empty
head = newNode;
size++;
return;
}
int currPtr = 0;
Node* curr = head;
Node* prev = nullptr;
//iterating till currPtr reached the pos
// Note :- we need not use prev here but using prev node make it easier to implement
while(currPtr < pos){
prev = curr;
curr = curr->next;
currPtr++;
}
if(prev){
prev->next = newNode;
//making the prev pointer of the added node equal to the previous node node
newNode->prev = prev;
}
else{
//Handling the edge case when pos = 0 because prev will be null
head = newNode;
}
newNode->next = curr;
if(curr){
//making the prev pointer of the next node equal to the added node
curr->prev = newNode;
}
size++;
return;
}
int Delete (int pos){
if(pos > size){
cout << "Can't delete data (Invalid position)" << endl;
return -1;
}
if(pos == 0){
Node* temp = head;
int val = temp->data;
head = head->next;
// making prev of head point to nullptr
if(head)head->prev = nullptr;
delete(temp);
size--;
return val;
}
int currPtr = 0;
Node* curr = head;
Node* prev = nullptr;
// Note :- we need not use prev here but using prev node make it easier to implement
while(currPtr < pos){
prev = curr;
curr = curr->next;
currPtr++;
}
int val = (curr)?curr->data:-1;
if(curr){
prev->next = curr->next;
if(curr->next){
curr->next->prev = curr->prev;
}
delete(curr);
}
else{
// This will never be executed
prev->next = nullptr;
}
size--;
return val;
}
void print(){
Node* temp = head;
Node* prev = nullptr;
while(temp){
cout<<temp->data<<" ";
prev = temp;
temp = temp->next;
}cout<<endl;
while(prev){
cout<<prev->data<<" ";
prev = prev->prev;
}cout<<endl;
}
};
int main() {
dll l1;
l1.Insert(10,0);
l1.Insert(20,1);
l1.Insert(40,2);
l1.Insert(30,0);
l1.Delete(2);
l1.print();
return 0;
}
Circular Linked List
In a singly circular linked list ,each node has one link similar to an ordinary singly linked-list ,except that the last node points back to the first node.
Circular linked list do not have any ends. While traversing circular linked list we should be careful otherwise we will be traversing the list indefinitely.
The node structure and the implementation of cll is similar to that of singly linked list.
The implementation of circular linked list is given below
// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
class Node{
int data; //The data to be stored
Node* next; // The reference to the next node
public:
friend class cll;
Node(int val = 0){
this->data = val; //initialised to 0
this->next = this; // note that the node points to itself here
}
};
class cll{
Node* head;
int size;
public:
cll(){
//initialisation
this->head = nullptr;
this->size = 0;
}
void Insert(int data){//insertion at the end
Node* newNode = new Node(data);
if(size == 0){
//Handling when ll is empty
head = newNode;
size++;
return;
}
Node* curr = head;
Node* prev = nullptr;
//iterating till curr come back after a revolution
do{
prev = curr;
curr = curr->next;
}while(curr!=head);
//At this point prev is pointting to the last element in the cll
prev->next = newNode;
newNode->next = curr;
size++;
return;
}
int Delete (){//deleting the head
if(size==0){
cout<<"Nothing to delete"<<endl;
return -1;
}
if(size==1){
this->head = nullptr;
size = 0;
return -1;
}
Node* curr = head;
Node* prev = nullptr;
//iterating till curr come back after a revolution
do{
prev = curr;
curr = curr->next;
}while(curr!=head);
//At this point prev is pointting to the last element in the cll
prev->next = curr->next;
head = curr->next;
size--;
delete(curr);
}
void print(){
if(size==0){
return ;
}
Node* curr = head;
Node* prev = nullptr;
//iterating till curr come back after a revolution
do{
cout<<curr->data<<" ";
prev = curr;
curr = curr->next;
}while(curr!=head);
cout<<endl;
}
};
int main() {
cll l1;
l1.Insert(10);
l1.Insert(20);
l1.Insert(40);
l1.Insert(30);
l1.Delete();
l1.print();
return 0;
}
I have kept some functions of the circular linked list to be implemented.It will be a good revision.
Memory-Efficient doubly linked list
In conventional doubly linked list , we have two pointers for pointing to the next node and the previous node. This leads to the wastage of memory.
Recently a journal presented an alternative way for implementing doubly linked list.This implementation is based on pointer difference.Each node uses only one pointer field to traverse back and forth.
The node structure looks like
class Node{
int data;
Node*ptrdiff; // prev xor next
public:
Node(int data){
this->data = data;
this->ptrdiff = nullptr;
}
};
ptrdiff is xor of prev and the next node.
Consider the doubly linked list :
A[10,p1] --> B[20,p2] --> C[30,p3] --> D[40,p4]
A,B,C,D are node with value as first parameter and sencond parameter is ptrdiff
Therefore,
p1 = null ^ B
p2 = A ^ C
p3 = B ^ D
p4 = C ^ null
Let us assume we are at node C and want to move to B.We know that C's ptrdiff is defined as B^D ,thus p3^D will give us address of B and similarly p3^B will given D's address.
TRY IMPLEMENTING THIS VERSION OF LINKED LIST AS PART OF HOMEWORK.
Thank you for patient reading . Let's meet next monday with another interesting data structure.