Linked Storage Representation-Linked Lists

Introduction to Linked Lists in C

A linked list is a fundamental data structure that consists of a sequence of elements, where each element is connected to the next one through pointers. Unlike arrays, linked lists do not have a fixed size, allowing for dynamic memory allocation and efficient insertion and deletion of elements.

Key Concepts

• Node: Each element in a linked list is called a node. A node typically contains data and a pointer to the next node in the sequence.
• Head: The head is the first node of the linked list. It is used as a starting point for any operation on the list.
• Pointer: Pointers are used to connect nodes in the linked list, allowing traversal from one node to another.

Types of Linked Lists

1. Singly Linked List: Each node points to the next node and the last node points to NULL.
2. Doubly Linked List: Each node contains pointers to both the next and the previous nodes.
3. Circular Linked List: The last node points back to the head, forming a circle.

Difference Between Linked list and Arrays:

Summary

• Arrays are suitable for scenarios where you need fast access to elements and the data size is known and fixed. They are efficient in terms of access time and memory usage, but they lack flexibility for dynamic resizing and frequent insertions/deletions.
• Linked Lists are ideal when you need a data structure that can dynamically change size and where insertions and deletions are frequent. They provide flexibility but at the cost of increased memory usage and slower access times.

Each structure has its own strengths and weaknesses, and the choice between arrays and linked lists depends on the specific requirements of the application.

Advantages and Disadvantages of Linked list:

Linked lists are a fundamental data structure used in computer science for dynamic storage of data. They have various advantages and disadvantages, which make them suitable for specific use cases. Below is a detailed breakdown of the advantages and disadvantages of linked lists.

Advantages of Linked Lists

1. Dynamic Size:
   • Description: Linked lists can grow and shrink dynamically as needed, which makes them suitable for applications where the number of elements is not known in advance.
   • Benefit: Efficient memory utilization as there is no need to allocate a fixed amount of memory in advance.
2. Efficient Insertions/Deletions:
   • Description: Inserting or deleting a node in a linked list does not require shifting elements, as it does in arrays.
   • Benefit: Operations can be done in constant time O(1)O(1)O(1) if the pointer to the previous node is known, making it ideal for scenarios where frequent insertions and deletions are needed.
3. Flexible Memory Use:
   • Description: Nodes are allocated as needed and do not need contiguous memory space.
   • Benefit: Linked lists can utilize fragmented memory and handle dynamic allocation better than arrays.
4. Ease of Implementation for Certain Data Structures:
   • Description: Linked lists are the basis for implementing other complex data structures like stacks, queues, and graphs.
   • Benefit: Simplifies the implementation of more complex structures due to inherent link-based structure.
5. Efficient Data Rearrangement:
   • Description: Data rearrangement is easier as only the pointers need to be adjusted.
   • Benefit: Efficient for applications that require frequent reordering or rearrangement of elements.

Disadvantages of Linked Lists

1. Increased Memory Usage:
   • Description: Each node in a linked list requires additional memory for a pointer to the next node.
   • Drawback: Higher memory overhead compared to arrays, especially in small data elements.
2. Sequential Access:
   • Description: Accessing elements requires traversal from the head node, leading to linear time complexity O(n)O(n)O(n).
   • Drawback: Slower access times compared to arrays, which provide constant time access O(1)O(1)O(1) via indexing.
3. Complexity in Implementation:
   • Description: Implementing linked lists requires careful management of pointers and can be error-prone.
   • Drawback: More complex to implement and manage than arrays, increasing the potential for bugs.
4. Poor Cache Locality:
   • Description: Linked lists have poor locality of reference as nodes are scattered across memory.
   • Drawback: Decreased cache performance and slower access speeds compared to arrays, which have excellent cache performance due to contiguous memory allocation.
5. Extra Operations for Backward Traversal:
   • Description: Singly linked lists do not support backward traversal without additional pointers.
   • Drawback: Doubly linked lists can solve this but require even more memory overhead for an extra pointer.
6. Difficulty in Finding the Length:
   • Description: Calculating the length of a linked list requires traversing all nodes.
   • Drawback: Increased time complexity for operations that depend on knowing the length.

When to Use Linked Lists

Linked lists are ideal for applications where:

• The number of elements is unknown and can change frequently.
• Frequent insertions and deletions are required.
• Memory allocation should be flexible and non-contiguous.

When Not to Use Linked Lists

Linked lists might not be the best choice when:

• Fast random access to elements is required.
• Memory overhead is a critical concern.
• Cache performance is a significant consideration.

Conclusion

Linked lists provide flexibility and efficiency for dynamic data management but come with trade-offs in terms of memory usage and access speed. Understanding these advantages and disadvantages helps in choosing the right data structure based on specific application needs.

Purpose of Dummy Header

A dummy header (or sentinel node) in a linked list is an auxiliary node placed at the beginning of the list. It does not hold any meaningful data but serves as a placeholder to simplify certain list operations, such as insertion and deletion, by reducing the number of special cases that need to be handled.

Single linked list

A singly linked list is a fundamental data structure that consists of a sequence of nodes, where each node contains data and a pointer to the next node in the sequence. It is a simple yet powerful structure used to store and manage collections of data. Singly linked lists are widely used in computer science due to their dynamic nature and ease of insertion and deletion operations.

Structure of a Singly Linked List

A singly linked list is composed of nodes, each of which has two components:

1. Data: The actual data or value that the node holds.
2. Next Pointer: A pointer (or reference) to the next node in the list. The last node’s next pointer points to NULL, indicating the end of the list.

Here’s a simple representation:

Operations on Singly Linked Lists

1. Insertion

• At the Beginning: Insert a new node at the head of the list.
• At the End: Traverse to the end and insert the node after the last node.
• After a Given Node: Insert a node after a specified node.

2. Deletion

• From the Beginning: Remove the node at the head of the list.
• From the End: Traverse and remove the last node.
• After a Given Node: Remove a node after a specified node.

3. Traversal

• Visit each node starting from the head and proceed to the next node until reaching the end of the list.

4. Search

• Traverse the list to find a node containing a specified value.

5. Update

• Change the data in a node at a particular position.

Advantages of Singly Linked Lists

• Dynamic Size: Can grow or shrink as needed, allowing efficient memory use.
• Efficient Insertions/Deletions: Adding or removing nodes can be done without shifting elements.
• Simplicity: Easy to implement and manage for simple applications.

Disadvantages of Singly Linked Lists

• Sequential Access: Must traverse nodes sequentially to access elements.
• Increased Memory Usage: Requires extra memory for pointers in each node.
• Poor Cache Performance: Nodes may not be stored contiguously, leading to slower access.

Program for Creating Single Linked list

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

// Define a node structure
typedef struct Node {
    int data;           // Data stored in the node
    struct Node* next;  // Pointer to the next node
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));  // Allocate memory for the node
    if (newNode == NULL) {  // Check for memory allocation failure
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;   // Set the node's data
    newNode->next = NULL;   // Initialize the next pointer to NULL
    return newNode;
}

// Function to create and initialize the linked list
Node* createLinkedList() {
    // Create the head of the list
    Node* head = createNode(10);  // Create the first node with data 10

    // Create more nodes
    Node* second = createNode(20);  // Create the second node with data 20
    Node* third = createNode(30);   // Create the third node with data 30

    // Link the nodes
    head->next = second;  // Link the head to the second node
    second->next = third; // Link the second node to the third node

    return head;  // Return the head of the linked list
}

// Function to print the linked list
void printList(Node* node) {
    while (node != NULL) {  // Traverse until the end of the list
        printf("%d -> ", node->data);
        node = node->next;  // Move to the next node
    }
    printf("NULL\n");
}

// Main function to test the linked list creation
int main() {
    Node* head = createLinkedList();  // Create the linked list

    // Print the linked list
    printf("Linked list: ");
    printList(head);

    return 0;
}

typedef struct Node {
    int data;           // Data stored in the node
    struct Node* next;  // Pointer to the next node
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));  // Allocate memory for the node
    if (newNode == NULL) {  // Check if memory allocation failed
        printf("Memory allocation failed\n");
        exit(1);  // Exit if memory allocation fails
    }
    newNode->data = data;   // Set the node's data
    newNode->next = NULL;   // Initialize the next pointer to NULL
    return newNode;         // Return the new node
}

Node* createLinkedList() {
    // Create the head of the list
    Node* head = createNode(10);  // Create the first node with data 10

    // Create more nodes
    Node* second = createNode(20);  // Create the second node with data 20
    Node* third = createNode(30);   // Create the third node with data 30

    // Link the nodes
    head->next = second;  // Link the head node to the second node
    second->next = third; // Link the second node to the third node

    return head;  // Return the head of the linked list
}

void printList(Node* node) {
    while (node != NULL) {  // Traverse until the end of the list
        printf("%d -> ", node->data);  // Print the data of the current node
        node = node->next;  // Move to the next node
    }
    printf("NULL\n");  // Print NULL to indicate the end of the list
}

int main() {
    Node* head = createLinkedList();  // Create the linked list

    // Print the linked list
    printf("Linked list: ");
    printList(head);

    return 0;  // Return 0 to indicate successful completion
}

Perform Insertion and Deletion operation on a Single Linked list

Singly Linked List Structure

A singly linked list is a series of nodes where each node contains:

• Data: The value in the node.
• Next: A pointer/reference to the next node in the list.

Here’s a visual representation:

Head -> [Data | Next] -> [Data | Next] -> [Data | Next] -> [Data | NULL]

Insertion Operation

Let’s say you want to insert a new node with data 5 after the node with data 2.

Initial List:

Head -> [1 | *] -> [2 | *] -> [3 | *] -> [4 | NULL]

Step 1: Locate the Position for Insertion

Find the node with data 2.

Step 2: Create the New Node

Create a new node with data 5:

New Node -> [5 | *]

Step 3: Update Pointers

1. Set the Next Pointer of the New Node: Point it to the node that comes after the node with data 2 (which is the node with data 3).
2. Update the Next Pointer of the Node with Data 2: Point it to the new node.

Resulting List:

Head -> [1 | *] -> [2 | *] -> [5 | *] -> [3 | *] -> [4 | NULL]

Deletion Operation

Now, let’s delete the node with data 3.

Initial List:

Head -> [1 | *] -> [2 | *] -> [5 | *] -> [3 | *] -> [4 | NULL]

Step 1: Locate the Node to Delete

Find the node with data 3 and its predecessor, which is the node with data 5.

Step 2: Update Pointers

1. Update the Next Pointer of the Node with Data 5: Point it to the node that comes after the node with data 3 (which is the node with data 4).
2. Remove the Node: The node with data 3 is now bypassed and effectively removed from the list.

Resulting List:

Head -> [1 | *] -> [2 | *] -> [5 | *] -> [4 | NULL]

Summary

• Insertion:
  1. Find where to insert.
  2. Create the new node.
  3. Adjust pointers so that the new node is inserted in the list.
• Deletion:
  1. Find the node to delete and its predecessor.
  2. Adjust pointers to bypass the node to be deleted.
  3. The node is removed from the list.

Program for Inserting and Deleting nodes

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

// Definition of a node
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to create a new node
Node* create_node(int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

// Function to insert a node at the beginning
void insert_at_beginning(Node** head_ref, int data) {
    Node* new_node = create_node(data);
    new_node->next = *head_ref;
    *head_ref = new_node;
}

// Function to insert a node at the end
void insert_at_end(Node** head_ref, int data) {
    Node* new_node = create_node(data);
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }
    Node* temp = *head_ref;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = new_node;
}

// Function to delete a node with a specific value
void delete_node(Node** head_ref, int key) {
    Node* temp = *head_ref;
    Node* prev = NULL;

    // If the head node itself holds the key
    if (temp != NULL && temp->data == key) {
        *head_ref = temp->next; // Change head
        free(temp); // Free old head
        return;
    }

    // Search for the key to be deleted
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    // If the key was not present in the list
    if (temp == NULL) return;

    // Unlink the node from the linked list
    prev->next = temp->next;
    free(temp); // Free the memory
}

// Function to print the linked list
void print_list(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    Node* head = NULL;

    // Inserting elements at the beginning
    insert_at_beginning(&head, 10);
    insert_at_beginning(&head, 20);
    insert_at_beginning(&head, 30);

    // Inserting elements at the end
    insert_at_end(&head, 40);
    insert_at_end(&head, 50);

    printf("Linked list before deletion:\n");
    print_list(head);

    // Deleting a node
    delete_node(&head, 20);

    printf("Linked list after deletion:\n");
    print_list(head);

    return 0;
}

Structure of a Single Circular Linked list

A Single Circular Linked List (SCLL) is a type of linked list where each node points to the next node in the sequence, and the last node points back to the first node, forming a circular structure. This means there is no null reference to signify the end of the list.

Here’s a breakdown of its key features and components:

1. Nodes: Each node in a single circular linked list contains two parts:
   • Data: The value or information stored in the node.
   • Next Pointer: A reference to the next node in the list.
2. Circular Structure: Unlike a linear linked list where the last node points to null, in a circular linked list, the last node’s Next Pointer refers back to the first node. This creates a circular chain of nodes.
3. Head Node: The list has a head node that acts as the starting point of the list. From the head, you can traverse the entire list by following the Next Pointers until you reach the starting node again.

Program for single circular linked list

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

// Node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode; // Initialize next to point to itself
    return newNode;
}

// Function to insert a node at the end
void insertEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    Node* temp = *head;
    while (temp->next != *head) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->next = *head;
}

// Function to delete a node
void deleteNode(Node** head, int key) {
    if (*head == NULL) {
        return;
    }
    
    Node *temp = *head, *prev = NULL;
    
    // If the node to be deleted is the head node
    if (temp->data == key) {
        prev = *head;
        while (prev->next != *head) {
            prev = prev->next;
        }
        if (*head == (*head)->next) {
            free(*head);
            *head = NULL;
        } else {
            prev->next = (*head)->next;
            free(*head);
            *head = prev->next;
        }
        return;
    }
    
    // Search for the node to be deleted
    while (temp->next != *head && temp->next->data != key) {
        temp = temp->next;
    }
    
    // Node not found
    if (temp->next == *head) {
        return;
    }
    
    // Node found
    Node* nodeToDelete = temp->next;
    temp->next = nodeToDelete->next;
    free(nodeToDelete);
}

// Function to traverse and print the list
void printList(Node* head) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    
    Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("(head)\n");
}

// Main function
int main() {
    Node* head = NULL;

    insertEnd(&head, 1);
    insertEnd(&head, 2);
    insertEnd(&head, 3);
    insertEnd(&head, 4);

    printf("Circular Linked List:\n");
    printList(head);

    printf("Deleting node with data 2\n");
    deleteNode(&head, 2);
    
    printf("Circular Linked List after deletion:\n");
    printList(head);

    return 0;
}

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

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode; // Initialize next to point to itself
    return newNode;
}

void insertEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    Node* temp = *head;
    while (temp->next != *head) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->next = *head;
}

void deleteNode(Node** head, int key) {
    if (*head == NULL) {
        return;
    }
    
    Node *temp = *head, *prev = NULL;
    
    if (temp->data == key) {
        prev = *head;
        while (prev->next != *head) {
            prev = prev->next;
        }
        if (*head == (*head)->next) {
            free(*head);
            *head = NULL;
        } else {
            prev->next = (*head)->next;
            free(*head);
            *head = prev->next;
        }
        return;
    }
    
    while (temp->next != *head && temp->next->data != key) {
        temp = temp->next;
    }
    
    if (temp->next == *head) {
        return;
    }
    
    Node* nodeToDelete = temp->next;
    temp->next = nodeToDelete->next;
    free(nodeToDelete);
}

void printList(Node* head) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    
    Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("(head)\n");
}

int main() {
    Node* head = NULL;

    insertEnd(&head, 1);
    insertEnd(&head, 2);
    insertEnd(&head, 3);
    insertEnd(&head, 4);

    printf("Circular Linked List:\n");
    printList(head);

    printf("Deleting node with data 2\n");
    deleteNode(&head, 2);
    
    printf("Circular Linked List after deletion:\n");
    printList(head);

    return 0;
}

Double Linked list

A doubly linked list is a data structure that consists of a set of nodes, each of which contains a value and two pointers, one pointing to the previous node in the list and one pointing to the next node in the list. This allows for efficient traversal of the list in both directions, making it suitable for applications where frequent insertions and deletions are required.

Representation of Doubly Linked List in Data Structure:

In a data structure, a doubly linked list is represented using nodes that have three fields:

1. Data
2. A pointer to the next node (next)
3. A pointer to the previous node (prev).

Insertion at the Beginning in Doubly Linked List:

To insert a new node at the beginning of a doubly linked list, follow these steps:

1. Allocate Memory: Create a new node and assign the provided value to its data field.
2. Initialize Pointers:
   • Set the prev pointer of the new node to NULL.
3. Check if the List is Empty:
   • If the list is empty (head is NULL):
     • Set the next pointer of the new node to NULL.
     • Update the head pointer to point to the new node.
4. If the List is Not Empty:
   • Set the next pointer of the new node to the current head node.
   • Update the prev pointer of the current head node to point to the new node.
   • Update the head pointer to point to the new node.

Insertion at the End of Doubly Linked List

To insert a new node at the end of the doubly linked list, we can use the following steps:

• Allocate memory for a new node and assign the provided value to its data field.
• Initialize the next pointer of the new node to nullptr.
• If the list is empty:
  • Set the previous pointer of the new node to nullptr.
  • Update the head pointer to point to the new node.
• If the list is not empty:
  • Traverse the list starting from the head to reach the last node.
  • Adjust pointers to insert the new node at the end:
    • Set the next pointer of the last node to point to the new node.
    • Set the previous pointer of the new node to point to the last node.’

Insertion at a Specific Position of Doubly Linked List

To insert a node at a specific Position in doubly linked list, we can use the following steps:

• Traverse the list to find the node at the desired position.
• Create a new node with the data you want to insert.
• Adjust the pointers of the new node, the previous node, and the next node to include the new node in the list.
• Update the pointers of the neighboring nodes to maintain the doubly linked list structure.

Deletion at the Beginning of doubly linked list

To delete a node at the beginning of a doubly linked list, follow these steps:

1. Check if the List is Empty:
   • If the list is empty (head is NULL), there is nothing to delete. Return immediately.
2. Delete the Head Node:
   • If the node to be deleted is the head node:
     • Update the head pointer to point to the next node in the list.
     • If the new head node is not NULL, update its prev pointer to NULL.
3. Free Memory:
   • Deallocate the memory used by the node to be deleted.

Deletion at the End on doubly linked list:

To delete a node at the end of a doubly linked list, follow these steps:

1. Check if the List is Empty:
   • If the list is empty (head is NULL), there is nothing to delete. Return from the function.
2. Find the Last Node:
   • Traverse the list to reach the last node (the node whose next pointer is NULL).
3. Update the Second-to-Last Node:
   • If the list has more than one node, set the next pointer of the second-to-last node to NULL. This makes it the new last node.
4. Free Memory:
   • Free the memory allocated for the node that was deleted (the original last node).

Deletion at a Specific Position in doubly linked list:

To delete a node at a specific position in a doubly linked list, follow these steps:

1. Traverse to the Node at the Specified Position:
   • Start from the head and move through the list to reach the node at the given position. Ensure you handle edge cases, such as positions that are out of bounds.
2. Adjust Pointers:
   • If Deleting the Head Node:
     • Update the head pointer to the next node.
     • If the new head is not NULL, set its prev pointer to NULL.
   • If Deleting a Node Other Than the Head:
     • Update the next pointer of the node before the deleted node to point to the node after the deleted node.
     • Update the prev pointer of the node after the deleted node to point to the node before the deleted node.
3. Free Memory:
   • Release the memory allocated for the deleted node.

Program for Double linked list :

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

// Node structure
typedef struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// Function to insert a node at the beginning
void insertFront(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    
    if (*head != NULL) {
        (*head)->prev = newNode;
    }
    
    *head = newNode;
}

// Function to insert a node at the end
void insertEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    Node* last = *head;
    
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    while (last->next != NULL) {
        last = last->next;
    }
    
    last->next = newNode;
    newNode->prev = last;
}

// Function to insert a node after a specific node
void insertAfter(Node* prevNode, int data) {
    if (prevNode == NULL) return;
    
    Node* newNode = createNode(data);
    newNode->next = prevNode->next;
    newNode->prev = prevNode;
    
    if (prevNode->next != NULL) {
        prevNode->next->prev = newNode;
    }
    
    prevNode->next = newNode;
}

// Function to delete a node at a specific position
void deleteNode(Node** head, int position) {
    if (*head == NULL) return;
    
    Node* temp = *head;
    
    // If head node needs to be removed
    if (position == 0) {
        *head = temp->next;
        
        if (*head != NULL) {
            (*head)->prev = NULL;
        }
        
        free(temp);
        return;
    }
    
    // Traverse to the node to be deleted
    for (int i = 0; temp != NULL && i < position; i++) {
        temp = temp->next;
    }
    
    // Node not found
    if (temp == NULL) return;
    
    // Adjust pointers
    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
    }
    
    if (temp->prev != NULL) {
        temp->prev->next = temp->next;
    }
    
    free(temp);
}

// Function to print the list from head to end
void printListForward(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// Function to print the list from end to head
void printListBackward(Node* head) {
    if (head == NULL) return;
    
    Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->prev;
    }
    printf("NULL\n");
}

// Main function to demonstrate the use of the list
int main() {
    Node* head = NULL;

    // Insert elements
    insertFront(&head, 1);
    insertEnd(&head, 2);
    insertEnd(&head, 3);
    insertAfter(head, 4);  // Inserting after the head node

    printf("Doubly Linked List (Forward):\n");
    printListForward(head);

    printf("Doubly Linked List (Backward):\n");
    printListBackward(head);

    printf("Deleting node at position 2\n");
    deleteNode(&head, 2);

    printf("Doubly Linked List after deletion (Forward):\n");
    printListForward(head);

    printf("Doubly Linked List after deletion (Backward):\n");
    printListBackward(head);

    return 0;
}

typedef struct Node {
    int data;            // Holds the value of the node
    struct Node* next;   // Pointer to the next node in the list
    struct Node* prev;   // Pointer to the previous node in the list
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // Allocate memory for a new node
    newNode->data = data;    // Set the data field
    newNode->next = NULL;    // Initialize the next pointer to NULL
    newNode->prev = NULL;    // Initialize the prev pointer to NULL
    return newNode;
}

void insertFront(Node** head, int data) {
    Node* newNode = createNode(data); // Create a new node
    newNode->next = *head; // Point the new node’s next to the current head

    if (*head != NULL) {
        (*head)->prev = newNode; // Update the previous pointer of the current head
    }
    
    *head = newNode; // Update head to point to the new node
}

void insertEnd(Node** head, int data) {
    Node* newNode = createNode(data); // Create a new node
    Node* last = *head; // Start from the head to find the end
    
    if (*head == NULL) {
        *head = newNode; // If the list is empty, the new node is the head
        return;
    }
    
    while (last->next != NULL) {
        last = last->next; // Traverse to the last node
    }
    
    last->next = newNode; // Set the next pointer of the last node to the new node
    newNode->prev = last; // Set the previous pointer of the new node to the last node
}

void insertAfter(Node* prevNode, int data) {
    if (prevNode == NULL) return; // Ensure the previous node is not NULL
    
    Node* newNode = createNode(data); // Create a new node
    newNode->next = prevNode->next; // Set the new node’s next to the next of prevNode
    newNode->prev = prevNode; // Set the new node’s previous to prevNode
    
    if (prevNode->next != NULL) {
        prevNode->next->prev = newNode; // Update the previous pointer of the node after prevNode
    }
    
    prevNode->next = newNode; // Set the next pointer of prevNode to the new node
}

void deleteNode(Node** head, int position) {
    if (*head == NULL) return; // Ensure the list is not empty
    
    Node* temp = *head;
    
    // If the head node needs to be removed
    if (position == 0) {
        *head = temp->next; // Update the head to the next node
        
        if (*head != NULL) {
            (*head)->prev = NULL; // Update the prev pointer of the new head
        }
        
        free(temp); // Free the old head node
        return;
    }
    
    // Traverse to the node to be deleted
    for (int i = 0; temp != NULL && i < position; i++) {
        temp = temp->next;
    }
    
    // Node not found
    if (temp == NULL) return;
    
    // Adjust pointers
    if (temp->next != NULL) {
        temp->next->prev = temp->prev; // Update the previous pointer of the node after temp
    }
    
    if (temp->prev != NULL) {
        temp->prev->next = temp->next; // Update the next pointer of the node before temp
    }
    
    free(temp); // Free the memory allocated for the node to be deleted
}

void printListForward(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

void printListBackward(Node* head) {
    if (head == NULL) return;
    
    Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->prev;
    }
    printf("NULL\n");
}

Double circular linked list

A double circular linked list is a variation of a doubly linked list where the list is circular. This means that the last node in the list points back to the first node, and the first node’s prev pointer points to the last node. This structure allows traversal from any node in either direction and ensures that you can traverse the entire list starting from any node without needing to check for null pointers.

Definition of a Double Circular Linked List

In a double circular linked list, each node contains:

1. Data Field: Holds the value or data of the node.
2. Next Pointer: Points to the next node in the list.
3. Previous Pointer: Points to the previous node in the list.

Characteristics:

• Circular: The next pointer of the last node points back to the first node, and the prev pointer of the first node points back to the last node.
• Doubly Linked: Each node has pointers to both its next and previous nodes, enabling bidirectional traversal.

Example program for Double Circular Linked list

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

// Define the node structure
typedef struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode;
    newNode->prev = newNode;
    return newNode;
}

// Function to insert a node at the end
void insertEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* last = (*head)->prev;
        last->next = newNode;
        newNode->prev = last;
        newNode->next = *head;
        (*head)->prev = newNode;
    }
}

// Function to insert a node at the beginning
void insertFront(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* last = (*head)->prev;
        newNode->next = *head;
        newNode->prev = last;
        (*head)->prev = newNode;
        last->next = newNode;
        *head = newNode;
    }
}

// Function to delete a node by value
void deleteNode(Node** head, int value) {
    if (*head == NULL) return;
    
    Node* temp = *head;
    do {
        if (temp->data == value) {
            // Node to delete is the only node in the list
            if (temp->next == temp) {
                free(temp);
                *head = NULL;
                return;
            }
            
            // Node to delete is the head node
            if (temp == *head) {
                Node* last = (*head)->prev;
                *head = (*head)->next;
                (*head)->prev = last;
                last->next = *head;
                free(temp);
                return;
            }
            
            // Node to delete is not the head node
            temp->prev->next = temp->next;
            temp->next->prev = temp->prev;
            free(temp);
            return;
        }
        temp = temp->next;
    } while (temp != *head);
}

// Function to print the list forward
void printListForward(Node* head) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    
    Node* temp = head;
    do {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("HEAD\n");
}

// Function to print the list backward
void printListBackward(Node* head) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    
    Node* temp = head->prev;
    do {
        printf("%d <-> ", temp->data);
        temp = temp->prev;
    } while (temp->next != head->prev);
    printf("HEAD\n");
}

// Main function to demonstrate the double circular linked list
int main() {
    Node* head = NULL;

    // Insert elements
    insertEnd(&head, 1);
    insertEnd(&head, 2);
    insertEnd(&head, 3);
    insertFront(&head, 0);
    
    printf("Doubly Circular Linked List (Forward):\n");
    printListForward(head);

    printf("Doubly Circular Linked List (Backward):\n");
    printListBackward(head);

    printf("Deleting node with value 2\n");
    deleteNode(&head, 2);

    printf("Doubly Circular Linked List after deletion (Forward):\n");
    printListForward(head);

    printf("Doubly Circular Linked List after deletion (Backward):\n");
    printListBackward(head);

    return 0;
}

typedef struct Node {
    int data;           // Data stored in the node
    struct Node* next;  // Pointer to the next node in the list
    struct Node* prev;  // Pointer to the previous node in the list
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // Allocate memory for a new node
    newNode->data = data;    // Assign the data to the new node
    newNode->next = newNode; // Initialize the next pointer to point to itself
    newNode->prev = newNode; // Initialize the prev pointer to point to itself
    return newNode;
}

void insertEnd(Node** head, int data) {
    Node* newNode = createNode(data); // Create a new node

    if (*head == NULL) {
        *head = newNode; // If the list is empty, make newNode the head
    } else {
        Node* last = (*head)->prev; // Find the last node in the list
        last->next = newNode; // Set the next of the last node to newNode
        newNode->prev = last; // Set the previous of newNode to the last node
        newNode->next = *head; // Set the next of newNode to the head (circular connection)
        (*head)->prev = newNode; // Update the head's previous to newNode
    }
}

void insertFront(Node** head, int data) {
    Node* newNode = createNode(data); // Create a new node

    if (*head == NULL) {
        *head = newNode; // If the list is empty, make newNode the head
    } else {
        Node* last = (*head)->prev; // Find the last node in the list
        newNode->next = *head; // Set the new node's next to the current head
        newNode->prev = last; // Set the new node's prev to the last node
        (*head)->prev = newNode; // Update the current head's prev to the new node
        last->next = newNode; // Update the last node's next to the new node
        *head = newNode; // Update the head to be the new node
    }
}

void deleteNode(Node** head, int value) {
    if (*head == NULL) return; // Return if the list is empty
    
    Node* temp = *head;
    
    do {
        if (temp->data == value) {
            // Node to delete is the only node in the list
            if (temp->next == temp) {
                free(temp);
                *head = NULL;
                return;
            }
            
            // Node to delete is the head node
            if (temp == *head) {
                Node* last = (*head)->prev;
                *head = (*head)->next;
                (*head)->prev = last;
                last->next = *head;
                free(temp);
                return;
            }
            
            // Node to delete is not the head node
            temp->prev->next = temp->next;
            temp->next->prev = temp->prev;
            free(temp);
            return;
        }
        temp = temp->next;
    } while (temp != *head);
}

void printListForward(Node* head) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    
    Node* temp = head;
    do {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("HEAD\n");
}

void printListBackward(Node* head) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    
    Node* temp = head->prev;
    do {
        printf("%d <-> ", temp->data);
        temp = temp->prev;
    } while (temp->next != head->prev);
    printf("HEAD\n");
}

int main() {
    Node* head = NULL; // Initialize the head to NULL
    
    // Insert elements
    insertEnd(&head, 1);
    insertEnd(&head, 2);
    insertEnd(&head, 3);
    insertFront(&head, 0);
    
    // Print list forward and backward
    printf("Doubly Circular Linked List (Forward):\n");
    printListForward(head);

    printf("Doubly Circular Linked List (Backward):\n");
    printListBackward(head);

    // Delete a node and print list again
    printf("Deleting node with value 2\n");
    deleteNode(&head, 2);

    printf("Doubly Circular Linked List after deletion (Forward):\n");
    printListForward(head);

    printf("Doubly Circular Linked List after deletion (Backward):\n");
    printListBackward(head);

    return 0;
}

Advantages and disadvantages of a single circular linked list over a singly linked list

Single Circular Linked List

Advantages:

1. Circular Traversal:
   • You can traverse the list starting from any node and eventually return to the starting node. This is useful for applications requiring circular traversal, such as round-robin scheduling.
2. No Need to Check for End:
   • You don’t need to handle the end of the list explicitly, as the last node’s next pointer points back to the head. This can simplify some operations, especially when performing cyclic operations.
3. Efficient for Certain Operations:
   • Operations like traversing from any node to another node in a circular fashion are straightforward. For example, finding the next node after the current one is simple, without needing to check if the end has been reached.

Disadvantages:

1. Complexity in Insertion/Deletion:
   • While insertion and deletion operations are possible, they can be more complex to implement than in a singly linked list. Care must be taken to correctly update the circular links.
2. Potential Infinite Loops:
   • In certain scenarios, if not handled properly, circular lists might cause infinite loops during traversal. This is because the list continuously loops back to the head.
3. Difficulty in Traversing Backwards:
   • Unlike doubly circular linked lists, single circular linked lists do not support backward traversal. If you need to traverse the list in both directions, you need a different structure.

Singly Linked List

Advantages:

1. Simplicity:
   • Singly linked lists are simpler to implement compared to circular linked lists. Each node has a single pointer to the next node, and there’s no need to manage circular links.
2. Ease of Use:
   • Operations like insertion, deletion, and traversal are easier to understand and implement. The end of the list is explicitly marked by a NULL pointer.
3. Good for Linear Traversal:
   • Ideal for applications where you need to process the list in a linear fashion, where each node is visited only once.

Disadvantages:

1. End of List Check:
   • You need to handle the end of the list explicitly (i.e., checking for NULL), which adds a small amount of complexity to traversal and certain operations.
2. No Circular Traversal:
   • Traversing from the end to the beginning is not possible. This can be a limitation for certain use cases where circular traversal is needed.
3. Wasted Memory:
   • Sometimes, the linear nature can lead to wasted memory or inefficiencies in scenarios where circular traversal would be more appropriate.

Summary

• Single Circular Linked List: Best used in scenarios where circular traversal or round-robin operations are needed. It simplifies certain operations but introduces complexity in handling circular links and potential infinite loops.
• Singly Linked List: More straightforward and easier to implement, suitable for applications requiring linear traversal and where circular behavior is not needed.

The choice between a single circular linked list and a singly linked list depends on the specific requirements of the application and the operations that need to be performed.

Advantages and Disadvantages of a Double Circular linked list over a Double linked list

A doubly circular linked list and a doubly linked list are both variations of linked lists, but they have distinct characteristics and use cases. Here’s a comparison of their advantages and disadvantages:

Doubly Circular Linked List

Advantages:

1. Bidirectional Traversal:
   • Like a doubly linked list, a doubly circular linked list allows traversal in both forward and backward directions.
2. Circular Nature:
   • The list forms a loop where the last node points back to the first node. This can be useful for applications that require circular iteration or cyclic operations.
3. Efficient for Certain Operations:
   • Operations that involve circular traversal or looping (e.g., round-robin scheduling) can be more straightforward and efficient because you don’t need to check for the end of the list.
4. Simplified List Management:
   • Adding or removing elements from the head or tail of the list can be simplified, as there’s no need to handle end-of-list conditions.

Disadvantages:

1. Complexity in Implementation:
   • Managing circular references can complicate code, especially when performing insertion and deletion operations. Special care is needed to maintain the circular structure correctly.
2. Infinite Loops Risk:
   • Care must be taken to avoid infinite loops in traversal or other operations, as the list forms a continuous loop.
3. Increased Overhead:
   • The circular nature might introduce additional overhead in some cases, as operations that assume a non-circular structure need extra handling.

Doubly Linked List

Advantages:

1. Flexible Traversal:
   • Supports traversal in both forward and backward directions, allowing for efficient access to both ends of the list.
2. Simpler Management:
   • Easier to understand and implement compared to circular lists because it doesn’t involve circular references. You can easily identify the beginning and end of the list.
3. Versatile Use Cases:
   • Suitable for a wide range of applications where circular traversal is not required. Useful for many standard data structures and algorithms.

Disadvantages:

1. End-of-List Handling:
   • Special cases need to be handled for operations at the end of the list (e.g., detecting the end of traversal or insertion/deletion at the end).
2. Less Efficient for Circular Operations:
   • For use cases requiring circular iteration or cyclic behavior, a doubly circular linked list might be more efficient.
3. Extra Space Overhead:
   • Each node requires extra space for two pointers (previous and next), which can be a consideration in memory-constrained environments.

Summary

• Doubly Circular Linked List: Best for scenarios where you need continuous circular traversal and where circular behavior simplifies your operations. It introduces some complexity in implementation and can lead to infinite loops if not managed carefully.
• Doubly Linked List: More straightforward to implement and understand, and suitable for general-purpose use where circular behavior is not required. It may require more handling for operations at the ends of the list and can be less efficient for circular operations.