Linked list

Advantages of Linked Lists over array:

Ease of insertion/deletion.
Insertion at the beginning is a constant time operation and takes O(1) time, as compared to arrays where inserting an element at the beginning takes O(n) time, where n is the number of elements in the array.
Linked lists are dynamic data structures. i.e., they can grow or shrink during the execution of a program.
Linked lists have efficient memory utilization. Here, memory is not pre-allocated. Memory is allocated whenever it is required and it is de-allocated (removed) when it is no longer needed.
insertion and deletion are easier and efficient. Linked lists provide flexibility in inserting a data item at a specified position and deletion of the data item from the given position.
Many complex applications can be easily carried out with linked lists.

Drawbacks of linked lists:

Random access is not allowed. We have to access elements sequentially starting from the first node (head node). So we cannot do a binary search with linked lists efficiently with its default implementation.
Extra memory space for a pointer is required with each element of the list.
It takes a lot of time in traversing and changing the pointers.
Reverse traversing is not possible in single linked lists.
Searching for an element is costly and requires O(n) time complexity.
Sorting of linked lists is very complex and costly.
Appending an element to a linked list is a costly operation, and takes O(n) time, where n is the number of elements in the linked list, as compared to arrays that take O(1) time.

Applications of linked list:

Represent very large numbers and operations of the large number such as adiition, multiplication and division.
Linked lists are to implement stack, queue, trees and graphs.
Implement the symbol table in compiler construction.

Types of Linked Lists:

Singly Linked List: In this type of linked list, one can move or traverse the linked list in only one direction, where the next pointer of each node points to other nodes but the next pointer of the last node points to NULL.
Doubly Linked List: In this type of linked list, one can traverse the linked list in both the directions (forward and backward).
Circular Linked List: In this type of linked list, the last node of the linked list contains the link of the first/head node of the linked list in its next pointer.
Doubly Circular Linked List: A doubly circular linked list or a circular two-way linked list is a more complex type of linked list that contains a pointer to the next as well as the previous node in the sequence. The difference between the doubly linked and circular doubly list is the same as that between a singly linked list and a circular linked list. The circular doubly linked list does not contain null in the previous field of the first node.
Header Linked List: A header linked list is a special type of linked list that contains a header node at the beginning of the list.

Singly linked list

Syntax of a node ↓

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

                
struct node *start = NULL; // points to the first element. Initially NULL

In singly linked list a head pointer is pointing to the first node.

Operations on singly linked list ↓

insertion
deletion
traversing
searching

Insertion are of three types ↓

insertion at front
insertion at last
insertion in between

                   
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int data;
    struct node *next;
} node;
node *start = NULL;

void insertAtFront();
void insertAtBack();
void insertAfterNode();
void deleteAtFront();
void deleteAtBack();
void deleteANode();
void display();

int main()
{
    int choice;
    while (1)
    {
        printf("\n------- MENU ---------");
        printf("\n1. Insert at front");
        printf("\n2. Insert at back");
        printf("\n3. Insert after a node");
        printf("\n4. Delete at front");
        printf("\n5. Delete at back");
        printf("\n6. Delete a node");
        printf("\n7. Display");
        printf("\n8. Exit");
        printf("\nEnter you choice : ");
        scanf("%d", &choice);
        switch (choice)
        {
        case 1:
            insertAtFront();
            break;
        case 2:
            insertAtBack();
            break;
        case 3:
            insertAfterNode();
            break;
        case 4:
            deleteAtFront();
            break;
        case 5:
            deleteAtBack();
            break;
        case 6:
            deleteANode();
            break;
        case 7:
            display();
            break;
        case 8:
            exit(0);
        default:
            printf("\nEnter a correct choice");
        }
    }
    return 0;
}
void insertAtFront()
{
    node *newnode = (node *)malloc(sizeof(node));
    printf("Enter a value : ");
    scanf("%d", &newnode->data);
    newnode->next = start;
    start = newnode;
}

void insertAtBack()
{
    node *newnode = (node *)malloc(sizeof(node));
    node *last = start;
    printf("Enter a value : ");
    scanf("%d", &newnode->data);
    newnode->next = NULL;
    if (start == NULL)
        start = newnode;
    else
    {
        while (last->next != NULL)
            last = last->next;
        last->next = newnode;
    }
}

void insertAfterNode()
{
    if (start == NULL)
    {
        printf("\nList is empty cannot insert after a node\n");
        return;
    }
    int node_val;
    printf("\nEnter a node value after which you want to insert : ");
    scanf("%d", &node_val);
    node *ptr = start;
    while (ptr->data != node_val)
    {
        if (ptr->next == NULL)
        {
            printf("\n Node not found cannot insert element");
            return;
        }
        ptr = ptr->next;
    }
    node *newNode = (node *)malloc(sizeof(node));
    newNode->next = NULL;
    printf("\nEnter the value : ");
    scanf("%d", &newNode->data);
    newNode->next = ptr->next;
    ptr->next = newNode;
}

void deleteAtFront()
{
    if (start == NULL)
    {
        printf("\nList is empty");
        return;
    }
    node *temp = start;
    start = start->next;
    free(temp);
}

void deleteAtBack()
{
    if (start == NULL)
    {
        printf("\nList is empty");
        return;
    }
    if (start->next == NULL)
    {
        free(start);
        start = NULL;
        return;
    }
    node *temp = start;
    while (temp->next->next != NULL)
        temp = temp->next;
    free(temp->next);
    temp->next = NULL;
}

void deleteANode()
{
    if (start == NULL)
    {
        printf("\nList is empty");
        return;
    }
    int search;
    printf("Enter a value you want to delete : ");
    scanf("%d", &search);
    node *temp = start;
    while (temp->data != search)
    {
        if (temp->next == NULL)
        {
            printf("\nValue not found");
            return;
        }
        temp = temp->next;
    }
    if (temp == start)
        deleteAtFront();
    else if (temp->next == NULL)
        deleteAtBack();
    else
    {
        node *prev = start;
        while (prev->next != temp)
            prev = prev->next;
        prev->next = temp->next;
        free(temp);
    }
}

void display()
{
    if (start == NULL)
    {
        printf("\nList is empty");
        return;
    }
    node *newnode = start;
    while (newnode != NULL)
    {
        printf("%d --> ", newnode->data);
        newnode = newnode->next;
    }
}

Circular Single Linked List

It is just a single linked list in which the link field of the last node points back to the address of the first node.
A circular linked list has no beginning and no end. It is necessary to establish a special pointer called start pointer always pointing to the first node of the list.
Circular linked lists are frequently used instead of ordinary linked list because many operations are much easier to implement.
In circular linked list no null pointer are used, hence all pointers contain valid address.

                            
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int data;
    struct node *next;
} node;
node *start = NULL;

void insertAtFront();
void insertAtBack();
void insertAfterNode();
void deleteAtFront();
void deleteAtBack();
void deleteNode();
void display();

int main()
{
    int choice;
    while (1)
    {
        printf("\n------- MENU Circular single linked list ---------");
        printf("\n1. Insert at front");
        printf("\n2. Insert at back");
        printf("\n3. Insert after a node");
        printf("\n4. Delete at front");
        printf("\n5. Delete at back");
        printf("\n6. Delete a node");
        printf("\n7. Display");
        printf("\n8. Exit");
        printf("\nEnter you choice : ");
        scanf("%d", &choice);
        switch (choice)
        {
        case 1:
            insertAtFront();
            break;
        case 2:
            insertAtBack();
            break;
        case 3:
            insertAfterNode();
            break;
        case 4:
            deleteAtFront();
            break;
        case 5:
            deleteAtBack();
            break;
        case 6:
            deleteNode();
            break;
        case 7:
            display();
            break;
        case 8:
            exit(0);
        default:
            printf("\nEnter a correct choice");
        }
    }
    return 0;
}
void insertAtFront()
{
    node *newNode = (node *)malloc(sizeof(node));
    printf("Enter a value : ");
    scanf("%d", &newNode->data);
    if (start == NULL)
    {
        start = newNode;
        newNode->next = start;
    }
    else
    {
        newNode->next = start;
        start = newNode;
    }
}

void insertAtBack()
{
    node *newNode = (node *)malloc(sizeof(node));
    node *last = start;
    printf("Enter a value : ");
    scanf("%d", &newNode->data);
    newNode->next = NULL;
    if (start == NULL)
    {
        start = newNode;
        newNode->next = start;
    }
    else
    {
        while (last->next != start)
            last = last->next;
        last->next = newNode;
        newNode->next = start;
    }
}

void insertAfterNode()
{
    if (start == NULL)
    {
        printf("\nlist is empty, cannot insert after a node\n");
        return;
    }
    int node_val;
    printf("\nEnter a node value after which you want to insert : ");
    scanf("%d", &node_val);
    node *temp = start;
    while (temp->data != node_val)
    {
        if (temp->next == NULL)
        {
            printf("\nValue not found");
            return;
        }
        temp = temp->next;
    }
    node *newNode = (node *)malloc(sizeof(node));
    newNode->next = NULL;
    printf("\nEnter the value : ");
    scanf("%d", &newNode->data);
    newNode->next = temp->next;
    temp->next = newNode;
}

void deleteAtFront()
{
    if (start == NULL)
    {
        printf("\nNo node exist");
        return;
    }
    if (start->next == start) // there is only one element
    {
        free(start);
        start = NULL;
        return;
    }
    node *last = start, *temp = start;
    while (last->next != start)
        last = last->next;
    start = start->next;
    last->next = start;
    free(temp);
}

void deleteAtBack()
{
    if (start == NULL)
    {
        printf("\nNo node exist");
        return;
    }
    if (start->next == start) // only one element left
    {
        free(start);
        start = NULL;
        return;
    }
    node *temp = start;
    while (temp->next->next != start)
    {
        temp = temp->next;
    }
    free(temp->next);
    temp->next = start;
}

void deleteNode()
{
    if (start == NULL)
    {
        printf("\nNo node exist");
        return;
    }
    int search;
    printf("Enter a value you want to delete : ");
    scanf("%d", &search);
    node *temp = start;
    while (temp->data != search)
    {
        temp = temp->next;
        if (temp->next == NULL)
        {
            printf("\nValue not found");
            return;
        }
    }
    if (temp == start)
        deleteAtFront();
    else if (temp->next == start)
        deleteAtBack();
    else
    {
        node *prev = start;
        while (prev->next != temp)
        {
            prev = prev->next;
        }
        prev->next = temp->next;
    }
}

void display()
{
    if (start == NULL)
    {
        printf("\nEmpty list");
        return;
    }
    node *newNode = start;
    while (newNode->next != start)
    {
        printf("%d --> ", newNode->data);
        newNode = newNode->next;
    }
    printf("%d --> ", newNode->data);
}

Doubly Linked List:

A doubly linked list is a two-way list in which all have two links. This helps in accessing both successor node and predecessor node from the given node position.
It provides bi-directional traversing. Each node contains three fields:
1. Left link (prev)
2. Data
3. Right link (next)
The left link points to the predecessor node and the righ link points to the successor node. The data field stores the required data.
Many application requires searching forward and backward thru nodes of a list. For example searching for a name in telephone directory would need forward and backward scanning thru a region of the whole list.
The basic operations in a double linked list are:
- Creation
- Insertion
- Deletion
- Traversing
The beginning of the double linked list is stored in a "start" pointer which points to the first node. The first node's left link and last node's right link is set to NULL.

The following code gives the structure definition:

                        
struct node
{
    struct node *prev;
    int data;
    struct node *next;
};
struct node *start = NULL;

                    
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    struct node *prev;
    int data;
    struct node *next;
} node;
node *start = NULL;
void insert_front(int val)
{
    node *newNode = (node *)malloc(sizeof(node));
    newNode->data = val;
    newNode->prev = NULL;
    newNode->next = NULL;
    if (start == NULL)
    {
        start = newNode;
    }
    else
    {
        newNode->next = start;
        start->prev = newNode;
        start = newNode;
    }
}
void insert_last(int val)
{
    node *newNode = (node *)malloc(sizeof(node));
    newNode->next = NULL;
    newNode->prev = NULL;
    newNode->data = val;

    if (start == NULL)
    {
        start = newNode;
    }
    else
    {
        node *ptr = start;
        while (ptr->next != NULL)
        {
            ptr = ptr->next;
        }
        newNode->prev = ptr;
        ptr->next = newNode;
    }
}
void insertAfterANode()
{
    if (start == NULL)
    {
        printf("\nList is empty, cannot insert a node");
        return;
    }
    int ele;
    printf("Enter the element after which you insert new element : ");
    scanf("%d", &ele);
    node *ptr = start;
    while (ptr->data != ele)
    {
        if (ptr->next == NULL)
        {
            printf("\n Element not found, cannot insert element");
            return;
        }
        ptr = ptr->next;
    }
    node *newNode = (node *)malloc(sizeof(node));
    newNode->next = NULL;
    newNode->prev = NULL;
    printf("Enter the node value : ");
    scanf("%d", &newNode->data);
    if (ptr == start)
    {
        newNode->prev = start;
        start->next = newNode;
    }
    else if (ptr->next == NULL)
    {
        ptr->next = newNode;
        newNode->prev = ptr;
    }
    else
    {
        newNode->next = ptr->next;
        newNode->prev = ptr;
        ptr->next->prev = newNode;
        ptr->next = newNode;
    }
}
void delete_front()
{
    if (start == NULL)
    {
        printf("\t\tUnderflow");
        return;
    }
    if (start->next == NULL)
        start = NULL;
    else
    {
        node *ptr = start;
        start = start->next;
        ptr->next = NULL;
        start->prev = NULL;
        free(ptr);
    }
}
void delete_last()
{

    if (start == NULL)
    {
        printf("\t\tUnderflow");
        return;
    }
    node *ptr = start;
    while (ptr->next != NULL)
    {
        ptr = ptr->next;
    }
    if (ptr->prev == NULL)
        start = NULL;
    else
    {
        ptr->prev->next = NULL;
        ptr->prev = NULL;
        free(ptr);
    }
}
void deleteNode()
{
    if (start == NULL)
    {
        printf("\t\tList is empty");
        return;
    }
    int ele;
    printf("Enter the element you want to delete : ");
    scanf("%d", &ele);
    node *ptr = start;
    while (ptr->data != ele)
    {
        if (ptr->next == NULL)
        {
            printf("\nElement not found");
            return;
        }
        ptr = ptr->next;
    }
    if (ptr == start)
    {
        delete_front();
    }
    else if (ptr->next == NULL)
    {
        delete_last();
    }
    else
    {
        ptr->next->prev = ptr->prev;
        ptr->prev->next = ptr->next;
        free(ptr);
    }
}
void display()
{

    if (start == NULL)
    {

        printf("\t\tUnderflow");
    }
    else
    {
        node *ptr = start;
        while (ptr != NULL)
        {
            printf("\t%d<=>", ptr->data);
            ptr = ptr->next;
        }
    }
}
int main()
{
    int ch, val, ele;
    while (1)
    {
        printf("\n1.insert in began\n2.insert in end\n3.insert after node");
        printf("\n4.Delete in front\n5.Delete in last\n6.Delete a node");
        printf("\n7.Display\n8.Exit\n");
        printf("Enter your choice : ");
        scanf("%d", &ch);

        switch (ch)
        {
        case 1:
        {
            printf("Enter the  data value : ");
            scanf("%d", &val);
            insert_front(val);
            break;
        }
        case 2:
        {
            printf("Enter the data value : ");
            scanf("%d", &val);
            insert_last(val);
            break;
        }

        case 3:
        {
            insertAfterANode();
            break;
        }

        case 4:
            delete_front();
            break;

        case 5:
            delete_last();
            break;

        case 6:
            deleteNode();
            break;

        case 7:
            display();
            break;

        case 8:
            exit(0);

        default:
            printf("Wrong input mate !!");
            break;
        }
    }
    return 0;
}

Circular Double Linked List

A circular double linked list has both sucessor and predecessor pointer in circular manner. The object behind considering circular double linked list is to simplify the insertion and deletion operations performed on double linked list.
In circular double linked list the right link of the right most node points back to the start node and left link of the first node points to the last node.

Garbage collection and Compaction

Garbage collection

Garbage collection is the process of automatically reclaiming memory that is no longer in use by the program.
In the context of linked lists, garbage collection involves identifying and deallocating unused nodes.
Node becomes unused when they are no longer reachable from the list's head node.
Garbage collection ensures efficient memory utilization and prevents memory leaks.
Mark and Sweep algorithm: It is a common technique used for garbage collection in linked lists.
- This algorithm consists of two phases: marking and sweeping.
- In the marking phase, the algorithm traverses the linked list from the head node and marks all reachable nodes.
- Marking can be done by setting a flag or modifying a field in each node.
- In the sweeping phase, the algorithm traverses the linked list again and deallocates all unmarked nodes.
- The memory occupied by unmarked nodes is returned to the system for reuse.

Using free to deallocate the unnecessary nodes

After marking the reachable nodes during the mark phase of the mark and sweep algorithm, you need to deallocate the memory for the unmarked nodes.Traverse the linked list and for each unmarked node, use free() to release the memory occupied by that node.
For example ↓

                           
// Assuming a linked list node structure like:
struct Node {
    int data;
    struct Node* next;
};

// During garbage collection, deallocate unmarked nodes
struct Node* current = head;
while (current != NULL) {
    struct Node* nextNode = current->next;
    if (!current->marked) {
        free(current);  // Deallocate memory for unmarked node
    }
    current = nextNode;
}

Compaction

Compaction is an optimization technique that aims to reduce memory fragmentation in a linked list.
Memory fragmentation occurs when free memory blocks are scattered throughout the memory space.
Compaction rearranges the nodes in memory to eliminate fragmentation and create a contiguous block of free memory.
The compaction process involves iterating over the linked list, moving the nodes closer together, and updating the pointers accordingly.
After compaction, the linked list occupies a compact memory space, which improves memory utilization and reduces memory allocation overhead.

Using free() in Compaction

During the compaction process, you rearrange the nodes to eliminate memory fragmentation and create a contiguous block of free memory.
As you move nodes, you will have "gaps" or unused memory spaces left behind.
To reclaim this unused memory, you can use free() to deallocate those gaps.
For example ↓

                        
// Assuming a linked list node structure like:
struct Node {
    int data;
    struct Node* next;
};

// Perform compaction and deallocate gaps
struct Node* current = head;
struct Node* prev = NULL;
while (current != NULL) {
    // Move the node to its new position
    // ...

    // Deallocate the gap between prev and current
    if (prev != NULL && prev->next != current) {
        struct Node* gap = prev->next;
        prev->next = current;
        free(gap);  // Deallocate memory for the gap
    }

    prev = current;
    current = current->next;
}