Linked List

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

  1. Ease of insertion and deletion.

  2. 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

  1. Access time of linked list is O(N) while that of array is O(1).

  2. Arrays are contiguous block, so any element will be physically near it's neighbour.This greatly benefits from modern CPU caching methods.

  3. 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.