1. Linked List

Love Babbar's Linked List notes (class instead of structs were used) 02. Linked List
Abdul Sir's Linked List in C++ using Class : 11. Linked List > C++ Class Code for a Linked List

Problem with array : Fixed Size
We might not be sure of how many elements we'd want to store in an array. Taking an array of a fixed size might lead to problems where the size might be either too large or too small for our requirements.

Array Revision :

We can either create an array inside the stack or inside the heap.

int a[5]; // to create the array inside the stack
int *p = new int[5] // to create an array inside the heap
  • Benefit of using arrays is that the it is contiguous

If we want a variable size data structure then we can't opt for arrays.

Linked List :

General Idea of Linked List :

  • linked list is a collection of nodes where each node contains data and pointer to the next node.

  • Linked list is always created inside heap memory.

  • Pasted image 20231219232459.png
    Pasted image 20231219232138.png
    Pasted image 20231219232237.png

  • Element Space and the Pointer Space together are called node.

How to define a node :

  • to define a node we have to define two things, data and a pointer.
  • data can be of any type : int, double, float, etc.
  • Pointer is pointing to a node therefore pointer is of node type.
  • Node is having a pointer of node type.
    Pasted image 20231219233419.png
  • struct Node *next; : here next is a pointer of struct Node type.
  • Structs having pointer of it's own type are called Self-Referential Structure
  • in c++ we can use both struct and class to define a node
Tip

In any compiler if integer is taking 4 or 2 bytes inside a structure then the pointer inside that structure will also take 4 or 2 bytes respectively.
Pasted image 20231219234015.png

Creating a node :

For creating a node we need a pointer because nodes are to be created inside the heap.


struct Node
{
	int data;
	struct Node *next;
};

struct Node *p; // this pointer will be created inside the stack

// for clang : we use malloc
p = (struct Node *)malloc(sizeof(struct Node));

// for c++ : 
p = new Node;

p -> data = 10; //assigning data to the dataspace
p -> next = 0; // zero which means NULL is stored here, so it is not pointing anywhere

Pasted image 20231219234526.png

  • here p is pointing to the address of dataspace in the node
  • since p is a pointer to a structure therefore we'll use arrow to access the members of the structure.
  • Pasted image 20231219235103.png

More about Linked List :

Pasted image 20231220002523.png

  • q=p; : means q=200 so q will also point to the address 200
    Pasted image 20231220002646.png
  • q=p->next; : q will get the value 210, therefore q is pointing on the next node. It will be read as let q point on next node of p.
    Pasted image 20231220002825.png
  • p=p->next; : p will now be pointing to the value stored at address 210
    Pasted image 20231220003557.png

Checking if a pointer is pointing at some address or not :

Pasted image 20231220004822.png

  • If a pointer is not pointing anywhere then these conditions will be true:
    Pasted image 20231220004923.png
  • If a pointer is pointing at some address then these conditions will be true:
    Pasted image 20231220005037.png
  • To check if after a given node there is any other node present or not (basically aur koi node pe current node point kar raha ya nahi yee check karna hai). Agar kisi node pe point nahi karega then it is the last node.
    Pasted image 20231220005409.png
    If this above statement returns true then that means the current node is the last node in the linked list.
    Pasted image 20231220005552.png
    If this above statement returns true then that means the current node is NOT the last node in the linked list.

Displaying a Linked List / Traversing a Linked List :

  • at the end of the linked list pointer p will become NULL i.e. p=0;
    Pasted image 20231220010351.png

Printing the nodes :

Pasted image 20231220010551.png

Creating and Displaying a Linked List (code) :

#include<iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
}*first=NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node; // first is a pointer which is pointing to a node created in heap.
    first -> data = A[0];
    first -> next = NULL;
    last=first;

    // for the rest of the nodes we'll create them using for loop
    for (i=1; i<n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t -> data = A[i];
        t->next=NULL;
        last->next=t;
        last=t;
    }
}

void Display ( struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}

int main()
{
    int A[]={3,5,7,10,15};

    create(A, 5);
    Display(first);
    
    return 0;
}

Using a CLASS :

Method 1 :

#include<iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
}*first=NULL;


void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node; // first is a pointer which is pointing to a node created in heap.
    first -> data = A[0];
    first -> next = NULL;
    last=first;

    // for the rest of the nodes we'll create them using for loop
    for (i=1; i<n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t -> data = A[i];
        t->next=NULL;
        last->next=t;
        last=t;
    }
}

void Display (Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}

int main()
{
    int A[]={3,5,7,10,15};

    create(A, 5);
    Display(first);

    return 0;
}

Method2 :

Recursive Display of Linked List :

Pasted image 20231220222512.png

Counting Nodes in the linked list :

Pasted image 20231220223730.png

Recursive fxn for counting Nodes :

Pasted image 20231220224100.png
another method :
Pasted image 20231220230538.png

Sum of all the elements in a linked list :

Pasted image 20231220231222.png

Recursive method :

Pasted image 20231220231325.png

find Max :

int findMax(struct Node *p)
{
    int max = INT_MIN;
    while(p)
    {
        if(p->data > max)
            max = p->data;
        p=p->next;
    }
    return max;
}

using recursion :

Method 1 :

Pasted image 20231221000320.png

Method 2 :

int findMax(struct Node *p)
{
    int x = INT_MIN;
    if(p==0)
        return INT_MIN;
    else
    {
        x=findMax(p->next);
        if (x > p->data)
            return x;
        else
            return p->data;
    }
}

Pasted image 20231223003059.png

Method 3 :

Same as method 2 but with ternary operator

int findMax(struct Node *p)
{
    int x = INT_MIN;
    if(p==0)
        return INT_MIN;
    x = findMax(p->next);
    return x > p->data ? x : p->data;
}

Searching in a Linked List

  • We can't perform a Binary Search on a Linked List as we cannot directly go on the middle of a Linked List. We have to traverse from the beginning.
    So we'll look at only linear search.

See the search function : 

#include<iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
}*first=NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node; // first is a pointer which is pointing to a node created in heap.
    first -> data = A[0];
    first -> next = NULL;
    last=first;

    // for the rest of the nodes we'll create them using for loop
    for (i=1; i<n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t -> data = A[i];
        t->next=NULL;
        last->next=t;
        last=t;
    }
}

void Display ( struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}

Node *search(struct Node *p, int key)
{
    while (p != NULL)
    {
        if (p->data == key)
            return p; // return the address of the node
        else
           p = p->next;
    }
    return NULL;
}

int main()
{
    int A[]={3,5,7,10,15};

    create(A, 5);
    Display(first);
    printf("%d", search(first, 7));
    return 0;
}

Recursive Approach

#include<iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
}*first=NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node; // first is a pointer which is pointing to a node created in heap.
    first -> data = A[0];
    first -> next = NULL;
    last=first;

    // for the rest of the nodes we'll create them using for loop
    for (i=1; i<n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t -> data = A[i];
        t->next=NULL;
        last->next=t;
        last=t;
    }
}

void Display ( struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}

Node *search(Node *p, int key)
{
    if (p == NULL)
        return NULL;
    else if (key == p->data)
        return p;
    else
        return search(p->next, key);
}

int main()
{
    int A[]={3,5,7,10,15};

    create(A, 5);
    Display(first);
    printf("%d", search(first, 7));
    return 0;
}

How to improve Searching in Linked List :

We've already seen two methods to improve linear search in arrays :

  1. Transposition
  2. Move to Head

Move to head :

Pasted image 20231223122313.png

#include<iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
}*first=NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node; // first is a pointer which is pointing to a node created in heap.
    first -> data = A[0];
    first -> next = NULL;
    last=first;

    // for the rest of the nodes we'll create them using for loop
    for (i=1; i<n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t -> data = A[i];
        t->next=NULL;
        last->next=t;
        last=t;
    }
}

void Display ( struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}

Node *searchNormal(Node *p, int key)
{
    while(p != NULL)
    {
        if (p->data == NULL)
            return NULL;
        else if ( p->data == key)
            return p;
        else
            p = p-> next;
    }
    return NULL;
}

Node *searchOptimized(Node *p, int key)
{
    Node *q = NULL;
    while(p != NULL)
    {
        if (key == p-> data)
        {
            q->next = p->next;
            p->next = first;
            first = p;
            return p;
        }
        else
        {
            q=p;
            p=p->next;
        }
    }
    return NULL;
}

int main()
{
    int A[] = {3,5,7,10,15};

    create(A, 5);
    Display(first);

    printf("\n%d", searchOptimized(first, 7));
    printf("\n%d", searchNormal(first, 7));
    return 0;
}

Inserting in a Linked List :

Pasted image 20231223123157.png

  • arrows represent the positions where we can insert a new node
    There will be two different cases
  1. Inserting before first Node : Here we'll have to the first pointer also to point to the added node.
  2. Inserting a node in between (after a given position): There is no change in the first pointer.

Inserting before First Node:

Pasted image 20231223125358.png

Inserting a node after a given position :

Pasted image 20231223125949.png

Single function for inserting a node anywhere in a Linked List

Pasted image 20231223132121.png

#include<iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
}*first=NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node; // first is a pointer which is pointing to a node created in heap.
    first -> data = A[0];
    first -> next = NULL;
    last=first;

    // for the rest of the nodes we'll create them using for loop
    for (i=1; i<n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t -> data = A[i];
        t->next=NULL;
        last->next=t;
        last=t;
    }
}

void Display ( struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    cout << endl;
}

void insert(struct Node *p, int pos, int x )
{
    Node *t;
    if(pos == 0) // inserting before 'first'
    {
        t = new Node;
        t->data = x;
        t->next = first;
        first = t;
    }
    else if (pos > 0)
    {
        for (int i = 0; i<pos-1 && p; i++) //as for inserting after pos 4 we'll have to move the p pointer 3 times as initially the p pointer is pointing at first node. Also, we did '&& p' to check if p exists or not
        {
            p = p->next;
        }
        if(p)
        {
            t = new Node;
            t->data = x;
            t->next = p->next;
            p->next = t;
        }
    }
}

int main()
{
    int A[] = {3,5,7,10,15};

    create(A, 5);
    Display(first);
    insert(first, 3, 12);
    Display(first);

    return 0;
}

Another method : Using count function

#include <stdio.h>
#include <stdlib.h>
struct Node
{
    int data;
    struct Node *next;
} *first = NULL;
void create(int A[], int n)
{
    int i;
    struct Node *t, *last;
    first = (struct Node *)malloc(sizeof(struct Node));
    first->data = A[0];
    first->next = NULL;
    last = first;
    for (i = 1; i < n; i++)
    {
        t = (struct Node *)malloc(sizeof(struct Node));
        t->data = A[i];
        t->next = NULL;
        last->next = t;
        last = t;
    }
}

int count(Node *p)
{
    if(p==NULL)
        return 0;
    else
    return count(p->next) + 1;   
}

void Display(struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}
void Insert(struct Node *p, int index, int x)
{
    struct Node *t;
    int i;
    if (index < 0 || index > count(p))
        return;
    t = (struct Node *)malloc(sizeof(struct Node));
    t->data = x;
    if (index == 0)
    {
        t->next = first;
        first = t;
    }
    else
    {
        for (i = 0; i < index - 1; i++)
            p = p->next;
        t->next = p->next;
        p->next = t;
    }
}
int main()
{
    int A[] = {10, 20, 30, 40, 50};
    create(A, 5);
    Insert(first, 0, 5);
    Display(first);
    return 0;
}

Creating a linked list using Insert function :

Pasted image 20231223141130.png

#include<iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
}*first=NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node; // first is a pointer which is pointing to a node created in heap.
    first -> data = A[0];
    first -> next = NULL;
    last=first;

    // for the rest of the nodes we'll create them using for loop
    for (i=1; i<n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t -> data = A[i];
        t->next=NULL;
        last->next=t;
        last=t;
    }
}

void Display ( struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    cout << endl;
}

void insert(struct Node *p, int pos, int x )
{
    Node *t;
    if(pos == 0) // inserting before 'first'
    {
        t = new Node;
        t->data = x;
        t->next = first;
        first = t;
    }
    else if (pos > 0)
    {
        for (int i = 0; i<pos-1 && p; i++) //as for inserting after pos 4 we'll have to move the p pointer 3 times as initially the p pointer is pointing at first node. Also, we did '&& p' to check if p exists or not
        {
            p = p->next;
        }
        if(p)
        {
            t = new Node;
            t->data = x;
            t->next = p->next;
            p->next = t;
        }
    }
}

int main()
{
    // int A[] = {3,5,7,10,15};

    // create(A, 5);
    // Display(first);
    insert(first, 0, 1);
    insert(first, 1, 2);
    insert(first, 3, 4);
    insert(first, 2, 3);
    Display(first);
    // → 1 2 3 // notice that 4 is not printed because for it p had become NULL as we had jumped a node

    return 0;
}

Creating a Linked List by Inserting at Last :

Pasted image 20231223142159.png

  • In order to avoid traversing the linked list every time we want to add a node we'll maintain a pointer last which will always point at the last node, this way we'll able to save a lot of time.
  • Suppose there is only 1 node in the beginning and the first pointer is pointing to that node then the last pointer must also point to that first node, this is a special case that we need to take care of.
  • If there are no nodes in the linked list then it'll create the first node.

Pasted image 20231223153418.png

3 Different ways :

1. void insertLast(int x) :

#include<iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
}*first=NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node; // first is a pointer which is pointing to a node created in heap.
    first -> data = A[0];
    first -> next = NULL;
    last=first;

    // for the rest of the nodes we'll create them using for loop
    for (i=1; i<n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t -> data = A[i];
        t->next=NULL;
        last->next=t;
        last=t;
    }
}

void Display ( struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    cout << endl;
}

void insertLast(int x )
{
    Node *last = new Node;
    Node *t = new Node;
    t->data = x;
    t->next = NULL;
    if(first == NULL) // means there are no nodes in the linked list
        first = last = t;
    else
    {
        last = first;
        while(last->next)
            last = last->next;
        last->next = t;        
        last = t;
    }
}

int main()
{
    Display(first);
    insertLast(2);
    insertLast(3);
    insertLast(4);
    Display(first); // → 2 3 4

    return 0;
}

2. void insertLast(struct Node *&p, int x) :

#include <iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
} *first = NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node;      // first is a pointer which is pointing to a node created in heap.
    first->data = A[0];
    first->next = NULL;
    last = first;

    // for the rest of the nodes we'll create them using for loop
    for (i = 1; i < n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t->data = A[i];
        t->next = NULL;
        last->next = t;
        last = t;
    }
}

void Display(struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    cout << endl;
}

void insertLast(struct Node *&p, int x)
{
    Node *last = new Node;
    Node *t = new Node;
    t->data = x;
    t->next = NULL;
    if (p == NULL) // means there are no nodes in the linked list
        p = last = t;
    else
    {
        last = p;
        while (last->next)
            last = last->next;
        last->next = t;
        last = t;
    }
}

int main()
{
    Display(first);
    insertLast(first, 2);
    insertLast(first, 3);
    insertLast(first, 4);
    Display(first); // → 2 3 4

    return 0;
}

3. struct Node *insertLast(struct Node *p, int x) :

#include <iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
} *first = NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node;      // first is a pointer which is pointing to a node created in heap.
    first->data = A[0];
    first->next = NULL;
    last = first;

    // for the rest of the nodes we'll create them using for loop
    for (i = 1; i < n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t->data = A[i];
        t->next = NULL;
        last->next = t;
        last = t;
    }
}

void Display(struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    cout << endl;
}

struct Node *insertLast(struct Node *p, int x)
{
    Node *last = new Node;
    Node *t = new Node;
    t->data = x;
    t->next = NULL;
    if (p == NULL)
    {
        p = last = t;
    }
    else
    {
        last = p;
        while (last->next)
            last = last->next;
        last->next = t;
        last = t;
    }
    return p; // Return the updated pointer
}

int main()
{
    Display(first);
    first = insertLast(first, 2);
    first = insertLast(first, 3);
    first = insertLast(first, 4);
    Display(first);

    return 0;
}
  • ! only for testing : Changing the data in a node : 
#include<iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
}*first=NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node; // first is a pointer which is pointing to a node created in heap.
    first -> data = A[0];
    first -> next = NULL;
    last=first;

    // for the rest of the nodes we'll create them using for loop
    for (i=1; i<n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t -> data = A[i];
        t->next=NULL;
        last->next=t;
        last=t;
    }
}

void Display ( struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    cout << endl;
}

void change(Node *p)
{
    for(int i=0; i<2; i++)
        p = p->next;
    p->data = 0;
}

int main()
{
    int A[] = {3,5,7,10,15};
    create(A, 5);

    Display(first);
    change(first);
    Display(first); // → 2 3 4

    return 0;
}

Inserting Node in a sorted Linked List :

#include<iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
}*first=NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node; // first is a pointer which is pointing to a node created in heap.
    first -> data = A[0];
    first -> next = NULL;
    last=first;

    // for the rest of the nodes we'll create them using for loop
    for (i=1; i<n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t -> data = A[i];
        t->next=NULL;
        last->next=t;
        last=t;
    }
}

void Display ( struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}

void insertSorted(Node *p, int x)
{
    Node *t = new Node;
    Node *q = new Node;
    t->data = x;
    t->next = NULL;

    if(first == NULL) // if there are no nodes created yet
        first = t;
    else
    {
        while( p && p->data <= x) // do not interchange these conditions around the && operator. We've to check whether p exists or not and if it exists then only check if p-> data <=x.
        {
            q=p;
            p=p->next;
        }
        if (p==first) // if we've to insert before first node
        {
            t->next=first;
            first=t;
        }
        else
        {
            t->next=q->next;
            q->next=t;
        }
    }

}

int main()
{
    int A[]={3,5,7,10,15};

    create(A, 5);
    insertSorted(first, 23); 
    Display(first); // -> 3 5 7 10 15 23

    return 0;
}

Deleting nodes from Linked List :

Pasted image 20231226212103.png

  • For deleting first node we'll simply move the first pointer to the next node
  • For deleting any other node we'll use a different approach.
  • make sure to deallocate the memory assigned to the deleted node.

Pasted image 20231226220002.png

#include <iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
} *first = NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node;      // first is a pointer which is pointing to a node created in heap.
    first->data = A[0];
    first->next = NULL;
    last = first;

    // for the rest of the nodes we'll create them using for loop
    for (i = 1; i < n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t->data = A[i];
        t->next = NULL;
        last->next = t;
        last = t;
    }
}

void Display(struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}

int count(Node *p)
{
    if (p == NULL)
        return 0;
    else
        return count(p->next) + 1;
}

void Delete(Node *p, int pos)
{
    int x = -1;
    Node *q = NULL;
    if (pos == 1)
    {
        x = first->data;
        p = first;
        first = first->next;
        delete (p);
    }
    else
    {
        for (int i = 0; i < pos - 1; i++)
        {
            q = p;
            p = p->next;
        }

        q->next = p->next;
        x = p->data; // storing the value of deleted node's 'data' if we'd like to use it in the future.
        free(p);
    }
}

int main()
{
    int A[] = {3, 5, 7, 10, 15};

    create(A, 5);
    Delete(first, 5);
    Display(first);

    return 0;
}

Sir's code :

#include <stdio.h>
#include <stdlib.h>
struct Node
{
	int data;
	struct Node *next;
} *first = NULL;
void create(int A[], int n)
{
	int i;
	struct Node *t, *last;
	first = (struct Node *)malloc(sizeof(struct Node));
	first->data = A[0];
	first->next = NULL;
	last = first;
	for (i = 1; i < n; i++)
	{
		t = (struct Node *)malloc(sizeof(struct Node));
		t->data = A[i];
		t->next = NULL;
		last->next = t;
		last = t;
	}
}
void Display(struct Node *p)
{
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
}

int count(Node *p)
{
    if(p==NULL)
        return 0;
    else
    return count(p->next) + 1;   
}

void RDisplay(struct Node *p)
{
	if (p != NULL)
	{
		RDisplay(p->next);
		printf("%d ", p->data);
	}
}
int Delete(struct Node *p, int index)
{
	struct Node *q = NULL;
	int x = -1, i;
	if (index < 1 || index > count(p))
		return -1;
	if (index == 1)
	{
		q = first;
		x = first->data;
		first = first->next;
		free(q);
		return x;
	}
	else
	{
		for (i = 0; i < index - 1; i++)
		{
			q = p;
			p = p->next;
		}
		q->next = p->next;
		x = p->data;
		free(p);
		return x;
	}
}
int main()
{
	int A[] = {10, 20, 30, 40, 50};
	create(A, 5);
printf("%d\n",Delete(first,2));
Display(first);
return 0;
}

Check If a Linked List is sorted or Not :

Ugly Method (My Method ☠️☠️) :

(ignore this method)

void checkSorted(Node *p) {
    if(p)
    {
        int x, flag=0;
        while (p->next != NULL)
        {
            x = p->data;
            p = p->next;
            if(x>p->data)
            {
                flag++;
                break;
            }
        }
        if(flag>0) printf("UnSorted");
        else printf("Sorted");
    }
}
// can be simplified by using return statements.

Better Approach :

bool checkSorted(Node *p) {
    int x = INT_MIN;
    while (p != NULL)
    {
        if (x > p->data)
        {
            return false;
        }
        x=p->data;
        p=p->next;
    }
    return true;
}

Remove Duplicates from Sorted Linked List

  • take two pointers (p and q, p is the trailing pointer) on consecutive nodes and check if the data is same or not.
  • if the data in both the nodes is similar then make p point to node after q and then delete the node q.
    Pasted image 20231229224554.png
  • then make q point to node after p;
    Pasted image 20231229224713.png

Code :
Pasted image 20231229230732.png

#include <iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
} *first = NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node;      // first is a pointer which is pointing to a node created in heap.
    first->data = A[0];
    first->next = NULL;
    last = first;

    // for the rest of the nodes we'll create them using for loop
    for (i = 1; i < n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t->data = A[i];
        t->next = NULL;
        last->next = t;
        last = t;
    }
}

void Display(struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    cout << endl;
}

int count(Node *p)
{
    if (p == NULL)
        return 0;
    else
        return count(p->next) + 1;
}

void removeDuplicateInSorted (Node *p)
{
    Node *q=p->next;
    while (q != NULL)
    {
        if(p->data != q->data)
        {
            p=q;
            q=q->next;
        }
        else
        {
            p->next = q->next;
            free (q);
            q=p->next;
        }
    }
}


int main()
{
    int A[] = {3, 5, 7, 10, 10, 10, 15};

    create(A, 7); // → 3 5 7 10 10 10 15 
    Display(first);
    removeDuplicateInSorted(first);
    Display(first); // → 3 5 7 10 15

    return 0;
}

Reversing a Linked List

  • A Linked List can be reversed by two methods :
    1. Reversing Elements :
      Pasted image 20231229232503.png
      Here for e.g. elements 2 and 8 will be interchanged but the nodes will remain the same.
    2. Reversing Links :
      Pasted image 20231229232720.png
      Here the node with address 300 should be pointing to address 250, 250 should be pointing to address 210 and 210 should be pointing to address 200.
      After the reversal the 300 node should become the first node.

In a linked list we prefer Reversing Links rather than Reversing Elements. Because data in a linked list need not be an integer always. It can be a record too, for e.g. a node can have roll no., name, class, etc... therefore it is easy to Reverse Links instead of reversing elements.

1. Reversing Elements :

  • We can copy the elements of linked list in an array then reverse the elements in the array back to the linked list.
    Pasted image 20231230002246.png
  • Here A is the array.
    Pasted image 20231230002853.png
#include <iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
} *first = NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node;      // first is a pointer which is pointing to a node created in heap.
    first->data = A[0];
    first->next = NULL;
    last = first;

    // for the rest of the nodes we'll create them using for loop
    for (i = 1; i < n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t->data = A[i];
        t->next = NULL;
        last->next = t;
        last = t;
    }
}

void Display(struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    cout << endl;
}

int count(Node *p)
{
    if (p == NULL)
        return 0;
    else
        return count(p->next) + 1;
}

void reverseElements(Node *p)
{
    int i =0;
    int *A = new int[count(p)];
    Node *q = p;

    while(q!=NULL)
    {
        A[i] = q->data;
        q=q->next;
        i++;
    }
    q=p;
    i--;

    while(q!=NULL)
    {
        q->data = A[i];
        q=q->next;
        i--;
    }
}


int main()
{
    int A[] = {2,4,6,8};

    create(A, 4);
    Display(first); // → 2 4 6 8 
    reverseElements(first);
    Display(first); // → 8 6 4 2 

    return 0;
}

2. Reversing Links :

Pasted image 20231230003942.png

  • We'll take 3 pointers (Sliding Pointers) and then slide them.
  • Initially p will point at first node and q and r will point to NULL.

Pasted image 20231230004101.png

  • the node at which q will point to will have it's next changed so that it starts pointing to r, then p q r will shift ahead and again q's next will be made to point r. The cycle continues...

Code :
Pasted image 20231230004747.png

#include <iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
} *first = NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node;      // first is a pointer which is pointing to a node created in heap.
    first->data = A[0];
    first->next = NULL;
    last = first;

    // for the rest of the nodes we'll create them using for loop
    for (i = 1; i < n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t->data = A[i];
        t->next = NULL;
        last->next = t;
        last = t;
    }
}

void Display(struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    cout << endl;
}

int count(Node *p)
{
    if (p == NULL)
        return 0;
    else
        return count(p->next) + 1;
}

void reverseLinks(Node *p)
{
    Node *q, *r;
    q = r = NULL;
    
    while (p!=NULL)
    {
        r=q;
        q=p;
        p=p->next;
        q->next = r;
    }
    first = q;
}


int main()
{
    int A[] = {2,4,6,8};

    create(A, 4);
    Display(first); // → 2 4 6 8 
    reverseLinks(first);
    Display(first); // → 8 6 4 2 

    return 0;
}

Using Recursion :

Pasted image 20231230011506.png

#include <iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
} *first = NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node;      // first is a pointer which is pointing to a node created in heap.
    first->data = A[0];
    first->next = NULL;
    last = first;

    // for the rest of the nodes we'll create them using for loop
    for (i = 1; i < n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t->data = A[i];
        t->next = NULL;
        last->next = t;
        last = t;
    }
}

void Display(struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    cout << endl;
}

int count(Node *p)
{
    if (p == NULL)
        return 0;
    else
        return count(p->next) + 1;
}

void reverseRecursive(Node *q, Node *p)
{
    if(p != NULL)
    {
        reverseRecursive(p, p->next);
        p->next = q;
    }
    else
    {
        first = q;
    }
}

int main()
{
    int A[] = {2,4,6,8};

    create(A, 4);
    Display(first); // → 2 4 6 8 
    reverseRecursive(NULL, first);
    Display(first); // → 8 6 4 2 

    return 0;
}

Concatenating Two Linked Lists :

Pasted image 20231230232215.png
Procedure : We have to reach the end of the Linked List and make the last node point to the 2nd Linked List.
Pasted image 20231230232350.png

#include <iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
} *first = NULL, *second = NULL, *third=NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node;      // first is a pointer which is pointing to a node created in heap.
    first->data = A[0];
    first->next = NULL;
    last = first;

    // for the rest of the nodes we'll create them using for loop
    for (i = 1; i < n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t->data = A[i];
        t->next = NULL;
        last->next = t;
        last = t;
    }
}
void create2(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    second = new Node;      // second is a pointer which is pointing to a node created in heap.
    second->data = A[0];
    second->next = NULL;
    last = second;

    // for the rest of the nodes we'll create them using for loop
    for (i = 1; i < n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t->data = A[i];
        t->next = NULL;
        last->next = t;
        last = t;
    }
}

void Display(struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    cout << endl;
}

int count(Node *p)
{
    if (p == NULL)
        return 0;
    else
        return count(p->next) + 1;
}

void concat(Node *p, Node *q)
{
   third = p;
   while (p->next != NULL)
        p=p->next;
    p->next = q;

}


int main()
{
    int A[] = {50,40,10,30,20};
    int B[] = {1,2,3,4,5};
    create(A, 5);
    create2(B, 5);

    Display(first); // → 50 40 10 30 20 
    Display(second); // → 1 2 3 4 5
    
    concat(first, second);

    Display(first); // → 50 40 10 30 20 1 2 3 4 5
    Display(third);// → 50 40 10 30 20 1 2 3 4 5

    return 0;
}

Merging 2 Sorted Linked List

  • Merging here is basically the process of combining two sorted Linked Lists to give another sorted Linked List.

Remember that we learned about Merging in Arrays as well, there we had to make use of the third new array as well but here in Linked List we do not require any extra LL or Array.

However we do require a extra pointers (other than first and second pointers).

Procedure :

We'll take two extra Pointers third & last. third will point to the starting of the merged LL and last will point to the end of the merged LL.

  • Compare the element of the 1st Node in first LL and element of first Node in 2nd LL.
  • Whichever is smaller, bring third and last upon it.
  • Then move first ahead then make last->next = NULL; (remember that third is pointing to 2 now)
    Pasted image 20231230233751.png
  • now again compare first & second and make last->next point to whichever is smaller. (here 4 < 8 so last-> next = second)
  • Move second ahead and then last->next = NULL

Now,
Pasted image 20231230235648.png

  • This is the initial thing that we have to do. Steps after this are all repeating steps so we'll take care of them by using while loop.

Final Code :
Pasted image 20231231001325.png

#include <iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
} *first = NULL, *second = NULL, *third = NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node;      // first is a pointer which is pointing to a node created in heap.
    first->data = A[0];
    first->next = NULL;
    last = first;

    // for the rest of the nodes we'll create them using for loop
    for (i = 1; i < n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t->data = A[i];
        t->next = NULL;
        last->next = t;
        last = t;
    }
}
void create2(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    second = new Node;     // second is a pointer which is pointing to a node created in heap.
    second->data = A[0];
    second->next = NULL;
    last = second;

    // for the rest of the nodes we'll create them using for loop
    for (i = 1; i < n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t->data = A[i];
        t->next = NULL;
        last->next = t;
        last = t;
    }
}

void Display(struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    cout << endl;
}

int count(Node *p)
{
    if (p == NULL)
        return 0;
    else
        return count(p->next) + 1;
}

void merge(Node *p, Node *q)
{
    Node *last = NULL;
    if (p->data < q->data)
    {
        third = last = p;
        p = p->next;
        third->next = NULL;
    }
    else
    {
        third = last = q;
        q = q->next;
        last->next = NULL;
    }

    while (p && q)
    {
        if (p->data < q->data)
        {
            last->next=p;
            last=p;
            p=p->next;
            last->next = NULL;
        }
        else
        {
            last ->next = q;
            last = q;
            q=q->next;
            last->next=NULL;
        }
    }
    if(p) last->next = p;
    if(q) last->next = q;
}

int main()
{
    int A[] = {50, 40, 10, 30, 20};
    int B[] = {1, 2, 3, 5, 4};
    create(A, 5);
    create2(B, 5);

    Display(first);
    Display(second);

    merge(first, second);

    Display(third); // → 1 2 3 5 4 50 40 10 30 20
    return 0;
}

Check for a LOOP in Linked List :

Pasted image 20231231184606.png

  • We'll take two pointers p and q.
  • p will move by 1 step and q will move by two steps.
  • if p & q meet again then a loop exists.
  • if any pointer becomes null (obviously q will become null first as it is moving faster) then the LL is linear.

Suppose we have two cars with different speeds then, on a Linear Track these cars will never meet again but on a Circular Track they will meet again. Same concept is being used here.
Pasted image 20231231185549.png

  • if else part on the right can be written as a single statement as well (it's written just after line having while statement).
  • A little condition is missing in the code here so for that see the complete code below : 
#include <iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
} *first = NULL; // first is a global pointer

/* -------- creating a linked list using an array ------- */
void create(int A[], int n) // n = no. of elements in the array
{
    int i;
    struct Node *t, *last; //'t' will help us in creating a new node, 'last' will be pointing on the last node and will help us in adding a new node in the linked list
    first = new Node;      // first is a pointer which is pointing to a node created in heap.
    first->data = A[0];
    first->next = NULL;
    last = first;

    // for the rest of the nodes we'll create them using for loop
    for (i = 1; i < n; i++) // we are starting from 1 as 0th element has already been created
    {
        t = new Node;
        t->data = A[i];
        t->next = NULL;
        last->next = t;
        last = t;
    }
}

void Display(struct Node *p)
{
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    cout << endl;
}

int count(Node *p)
{
    if (p == NULL)
        return 0;
    else
        return count(p->next) + 1;
}

int isLoop (Node *f)
{
    Node *p, *q;
    p = q = f;

    do
    {
        p=p->next;
        q=q->next;
        q=q? q->next : q;
    }while(p && q && p!=q);

    if(p==q)
        return 1;
    else
        return 0;
}


int main()
{
    int A[] = {10, 20, 30, 40, 50};
    create(A, 5);
    Display(first);

/* ------------------- to form a loop: ------------------ */
    Node *t1, *t2;
    t1=first->next->next; // t1 is now pointing at 30
    t2=first->next->next->next->next; // t2 is now pointing at 50
    t2->next = t1;
/* ------------------------------------------------------ */

    cout << isLoop(first); // → 1

    return 0;
}

C++ Class Code for a Linked List :

#include <iostream>
using namespace std;

class Node
{
public:
    int data;
    Node *next;
};

class LinkedList
{
private:
    Node *first;

public:
    // constructor function
    LinkedList()
    {
        first = NULL;
    }

    // constructor for creating a Linked List using an array
    LinkedList(int A[], int n);
    ~LinkedList(); // Destructor function

    void Display();
    void Insert(int index, int x);
    int Delete(int index);
    int Length();
};

LinkedList::LinkedList(int A[], int n)
{
    Node *last, *t;
    int i = 0;
    first = new Node;
    first->data = A[0];
    first->next = NULL;
    last = first;
    for (i = 1; i < n; i++)
    {
        t = new Node;
        t->data = A[i];
        t->next = NULL;
        last->next = t;
        last = t;
    }
}

LinkedList::~LinkedList()
{
    Node *p = first;
    while (first)
    {
        first = first->next;
        delete p;
        p = first;
    }
}

void LinkedList::Display()
{
    Node *p = first;
    while (p)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

int LinkedList::Length()
{
    Node *p = first;
    int len = 0;
    while (p)
    {
        len++;
        p = p->next;
    }
    return len;
}

void LinkedList::Insert(int index, int x)
{
    Node *t, *p = first;
    if (index < 0 || index > Length())
        return;
    t = new Node;
    t->data = x;
    t->next = NULL;
    if (index == 0)
    {
        t->next = first;
        first = t;
    }
    else
    {
        for (int i = 0; i < index - 1; i++)
            p = p->next;
        t->next = p->next;
        p->next = t;
    }
}

int LinkedList::Delete(int index)
{
    Node *p, *q = NULL;
    int x = -1;
    if (index < 1 || index > Length())
        return -1;
    if (index == 1)
    {
        p = first;
        first = first->next;
        x = p->data;
        delete p;
    }
    else
    {
        p = first;
        for (int i = 0; i < index - 1; i++)
        {
            q = p;
            p = p->next;
        }
        q->next = p->next;
        x = p->data;
        delete p;
    }
    return x;
}

int main()
{
    int A[] = {1, 2, 3, 4, 5};
    LinkedList l(A, 5);
    l.Insert(3, 10);
    l.Display();

    return 0;
}

Circular Linked List

  • Linked List where the last node points at the first node is called a circular Linked List.

  • Here since the LL is circular so there is no first node.

  • So we name the pointer head instead of first.

  • Pasted image 20231231215340.png

  • A Circular LL can't be NULL even if it is empty.

Another representation of Circular LL :
Pasted image 20231231215835.png

  • Here head node is not used for storing data.

Displaying a Circular Linked List : (and creating a Circular LL as well)

Pasted image 20231231220620.png

#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node *next;
} *head;

// creating a Circular Linked List
void create(int A[], int n)
{
    int i;
    struct Node *t, *last;
    head = new Node;
    head->data = A[0];
    head->next = head;
    last = head;

    for (int i = 1; i < n; i++)
    {
        t = new Node;
        t->data = A[i];
        t->next = last->next;
        last->next = t;
        last = t;
    }
}

void display(Node *h)
{
    do
    {
        printf("%d ", h->data);
        h=h->next;
    } while (h != head);
}

int main()
{

    int A[] = {2, 3, 4, 5, 6};
    create(A, 5);
    display(head);
    return 0;
}

Using Recursion :

Pasted image 20231231221135.png

#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node *next;
} *head;

// creating a Circular Linked List
void create(int A[], int n)
{
    int i;
    struct Node *t, *last;
    head = new Node;
    head->data = A[0];
    head->next = head;
    last = head;

    for (int i = 1; i < n; i++)
    {
        t = new Node;
        t->data = A[i];
        t->next = last->next;
        last->next = t;
        last = t;
    }
}

void recursiveDisplay(Node *h)
{
    static int flag = 0;
    if (h != head || flag == 0)
    {
        flag = 1;
        printf("%d ", h->data);
        recursiveDisplay(h->next);
    }
}

int main()
{

    int A[] = {2, 3, 4, 5, 6};
    create(A, 5);
    recursiveDisplay(head);
    return 0;
}

Inserting in a Circular Linked List :

Pasted image 20231231225509.png

  • The code is similar to Linear LL, we'll have to provide an index after which we want the node to be inserted so there is not any difference left in inserting in Linear LL and Circular LL.
  • NOTE: We can't add a node before the head node with this method tho. I mean, we can indeed add it by taking index as 5 (see image above) so the node will be added after index 5 which will technically be before head. But we'll see another method for it as well where we won't have to specify the index :

Adding a Node before head in a Circular Linked List :

See the NOTE above as well please.

Pasted image 20231231232246.png

  • first we'll create the new node t which we desire to insert before the head node.
  • make the t->next = head;
  • Move to the last node of the Circular Linked List (thou shall not cast judgement upon the one who says a Circular LL can have a last node)
  • make the last node's next point to t
    Now shall we make the new node (t) as head ? Logically you don't have to.
    Pasted image 20240101000043.png

Single Insert Function with both of the above features:

Pasted image 20240101005715.png

#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node *next;
} *head;

// creating a Circular Linked List
void create(int A[], int n)
{
    int i;
    struct Node *t, *last;
    head = new Node;
    head->data = A[0];
    head->next = head;
    last = head;

    for (int i = 1; i < n; i++)
    {
        t = new Node;
        t->data = A[i];
        t->next = last->next;
        last->next = t;
        last = t;
    }
}

void display(Node *h)
{
    do
    {
        printf("%d ", h->data);
        h=h->next;
    } while (h != head);
}

int length(Node *p)
{
    int len = 0;
    do
    {
        len++;
        p=p->next;
    }while(p != head);
    return len;
}

void insert (Node *p, int index, int x)
{
    if(index < 0 || index > length(head)) return;

    Node *t;
    int i;

    if(index == 0)
    {
        t = new Node;
        t->data = x;

        if(head == NULL)
        {
            head = t;
            head->next = NULL;
        }
        else
        {
            t->next = head;
            while (p->next != head) p=p->next;
            p->next = t;
            head = t;
        }
    }
    else
    {
        t = new Node;
        t->data = x;

        for (int i=0; i < index-1; i++)
            p=p->next;
        t->next = p->next;
        p->next = t;
    }
}

int main()
{

    int A[] = {2, 3, 4, 5, 6};
    create(A, 5);
    // cout << length(head);
    insert(head, 2, 1); // inserting value 1 after value 3
    display(head); // → 2 3 1 4 5 6 
    
    return 0;
}

Deleting in a Circular LL :

Pasted image 20240103104738.png
Pasted image 20240103105117.png

For Deleting Head Node :

  • For deleting the head node the last node should point on the new head node after deletion
    Pasted image 20240103105243.png

Combined / Complete Delete Function :

Pasted image 20240103105902.png

#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node *next;
} *head;

// creating a Circular Linked List
void create(int A[], int n)
{
    int i;
    struct Node *t, *last;
    head = new Node;
    head->data = A[0];
    head->next = head;
    last = head;

    for (int i = 1; i < n; i++)
    {
        t = new Node;
        t->data = A[i];
        t->next = last->next;
        last->next = t;
        last = t;
    }
}

void display(Node *h)
{
    do
    {
        printf("%d ", h->data);
        h=h->next;
    } while (h != head);
}

int length(Node *p)
{
    int len = 0;
    do
    {
        len++;
        p=p->next;
    }while(p != head);
    return len;
}

int Delete ( Node*p, int index)
{
    Node *q;
    int i, x;

    if(index < 0 || index > length(head))
        return -1;
    if(index==0)
    {
        while(p->next != head) p=p->next;
        x= head->data;
        if(p==head)
        {
            free(head);
            head=NULL;
        }
        else
        {
            p->next=head->next;
            free(head);
            head=p->next;
        }
    }
    else
    {
        for (i=0 ; i<index-1; i++)
            p=p->next;
        q=p->next;
        p->next = q->next;
        x = q->data;
        free(q);
    }
    return x;
}

int main()
{

    int A[] = {2, 3, 4, 5, 6};
    create(A, 5);
    // display(head);
    cout << Delete(head, 1); // → 3
    
    return 0;
}

Doubly Linked List :

Pasted image 20240103123356.png

  • We can move bi-directionally
    Pasted image 20240103123602.png Pasted image 20240103123903.png
#include<iostream>
using namespace std;

struct Node
{
    struct Node *prev;
    int data;
    struct Node *next;
}* first = NULL;

void create (int A[], int n)
{
    struct Node *t, *last;
    int i;

    first = new Node;
    first -> data = A[0];
    first->prev = first->next=NULL;
    last = first;

    for(i=1; i<n; i++)
    {
        t= new Node;
        t->data=A[i];
        t->next=last->next; // i.e NULL or Simply take NULL instead of last->next
        t->prev=last;
        last->next=t;
        last = t;
    }
}

void Display ( Node *p)
{
    while(p)
    {
        printf("%d ", p->data);
        p=p->next;
    }
    cout << endl;
}

int Length(Node *p)
{
    int len = 0;
    while (p)
    {
        len++;
        p=p->next;
    }
    return len;
}

int main()
{
    int A[] = {10, 20, 30, 40, 50};
    create(A, 5);
    Display(first);
    cout << Length(first);

    return 0;
}

Insert a node in a Doubly Linked List :

Two Cases :

  1. Before First Node
    Pasted image 20240103130523.png
  2. At any given Index
    Pasted image 20240103131818.png
    Pasted image 20240103131828.png

Complete Code : 

#include<iostream>
using namespace std;

struct Node
{
    struct Node *prev;
    int data;
    struct Node *next;
}* first = NULL;

void create (int A[], int n)
{
    struct Node *t, *last;
    int i;

    first = new Node;
    first -> data = A[0];
    first->prev = first->next=NULL;
    last = first;

    for(i=1; i<n; i++)
    {
        t= new Node;
        t->data=A[i];
        t->next=last->next;
        t->prev=last;
        last->next=t;
        last = t;
    }
}

void Display ( Node *p)
{
    while(p)
    {
        printf("%d ", p->data);
        p=p->next;
    }
    cout << endl;
}

int Length(Node *p)
{
    int len = 0;
    while (p)
    {
        len++;
        p=p->next;
    }
    return len;
}

void Insert(Node *p, int index, int x)
{
    Node *t;
    int i;

    if(index<0 || index>Length(p))
        return;
    if(index == 0)
    {
        t = new Node;
        t->data = x;
        t->prev=NULL;
        t->next=first;
        first->prev = t;
        first = t;
    }
    else
    {
        for (int i = 0; i<index-1; i++)
            p=p->next;
        t=new Node;
        t->data = x;
        t->prev = p;
        t->next = p->next;
        if(p->next) p->next->prev = t;
        p->next = t;
    }
}

int main()
{
    int A[] = {10, 20, 30, 40, 50};
    create(A, 5);
    Insert(first, 0, 23);
    Display(first); // → 23 10 20 30 40 50 

    return 0;
}

Deleting a node in Doubly Linked List :

  1. Delete First Node
  2. Delete from given Index
#include<iostream>
using namespace std;

struct Node
{
    struct Node *prev;
    int data;
    struct Node *next;
}* first = NULL;

void create (int A[], int n)
{
    struct Node *t, *last;
    int i;

    first = new Node;
    first -> data = A[0];
    first->prev = first->next=NULL;
    last = first;

    for(i=1; i<n; i++)
    {
        t= new Node;
        t->data=A[i];
        t->next=last->next;
        t->prev=last;
        last->next=t;
        last = t;
    }
}

void Display ( Node *p)
{
    while(p)
    {
        printf("%d ", p->data);
        p=p->next;
    }
    cout << endl;
}

int Length(Node *p)
{
    int len = 0;
    while (p)
    {
        len++;
        p=p->next;
    }
    return len;
}

int Delete (Node *p, int index)
{
    Node *q;
    int x = -1, i;
    if(index < 1 || index > Length(p))
        return -1;
    if(index == 1)
    {
        first = first -> next;
        if(first) first->prev = NULL;

        x=p->data;
        free(p);
    }
    else
    {
        for (i=0; i<index-1; i++)
            p=p->next;
        p->prev->next = p->next;
        if(p->next)
            p->next->prev = p->prev;
        x=p->data;
        free(p);
    }
    return x;
}

int main()
{
    int A[] = {10, 20, 30, 40, 50};
    create(A, 5);
    Delete(first, 1); // → 20 30 40 50 
    Display(first);

    return 0;
}

Reversing a Doubly Linked List :

Pasted image 20240103150220.png
Pasted image 20240103150056.png

#include<iostream>
using namespace std;

struct Node
{
    struct Node *prev;
    int data;
    struct Node *next;
}* first = NULL;

void create (int A[], int n)
{
    struct Node *t, *last;
    int i;

    first = new Node;
    first -> data = A[0];
    first->prev = first->next=NULL;
    last = first;

    for(i=1; i<n; i++)
    {
        t= new Node;
        t->data=A[i];
        t->next=last->next;
        t->prev=last;
        last->next=t;
        last = t;
    }
}

void Display ( Node *p)
{
    while(p)
    {
        printf("%d ", p->data);
        p=p->next;
    }
    cout << endl;
}

int Length(Node *p)
{
    int len = 0;
    while (p)
    {
        len++;
        p=p->next;
    }
    return len;
}

void Reverse(Node *p)
{
    Node *temp;
    while(p!=NULL)
    {
        temp = p->next;
        p->next = p->prev;
        p->prev = temp;
        p=p->prev;
        if(p!= NULL && p->next==NULL)
            first=p;
    }
}

int main()
{
    int A[] = {10, 20, 30, 40, 50};
    create(A, 5);
    Reverse(first);
    Display(first); // → 50 40 30 20 10 

    return 0;
}

Circular Doubly Linked List :

Pasted image 20240103150842.png

Displaying :

Pasted image 20240103150910.png

Interactive Graph
Table Of Contents
Linked List
Array Revision :
Linked List :
General Idea of Linked List :
How to define a node :
Creating a node :
More about Linked List :
Checking if a pointer is pointing at some address or not :
Displaying a Linked List / Traversing a Linked List :
Printing the nodes :
Creating and Displaying a Linked List (code) :
Using a CLASS :
Method 1 :
Method2 :
Recursive Display of Linked List :
Counting Nodes in the linked list :
Recursive fxn for counting Nodes :
Sum of all the elements in a linked list :
Recursive method :
find Max :
using recursion :
Method 1 :
Method 2 :
Method 3 :
Searching in a Linked List
Recursive Approach
How to improve Searching in Linked List :
Move to head :
Inserting in a Linked List :
Inserting before First Node:
Inserting a node after a given position :
Single function for inserting a node anywhere in a Linked List
Another method : Using count function
Creating a linked list using Insert function :
Creating a Linked List by Inserting at Last :
1. void insertLast(int x) :
2. void insertLast(struct Node *&p, int x) :
3. struct Node *insertLast(struct Node *p, int x) :
Inserting Node in a sorted Linked List :
Deleting nodes from Linked List :
Sir's code :
Check If a Linked List is sorted or Not :
Ugly Method (My Method ☠️☠️) :
Better Approach :
Remove Duplicates from Sorted Linked List
Reversing a Linked List
1. Reversing Elements :
2. Reversing Links :
Using Recursion :
Concatenating Two Linked Lists :
Merging 2 Sorted Linked List
Procedure :
Check for a LOOP in Linked List :
C++ Class Code for a Linked List :
Circular Linked List
Displaying a Circular Linked List : (and creating a Circular LL as well)
Using Recursion :
Inserting in a Circular Linked List :
Adding a Node before head in a Circular Linked List :
Single Insert Function with both of the above features:
Deleting in a Circular LL :
For Deleting Head Node :
Combined / Complete Delete Function :
Doubly Linked List :
Insert a node in a Doubly Linked List :
Deleting a node in Doubly Linked List :
Reversing a Doubly Linked List :
Circular Doubly Linked List :
Displaying :