Introduction to Linked Lists

Overview of Linked Lists

A linked list is a data structure used for storing collections of data. Unlike arrays, linked lists do not require contiguous memory locations. Each element in a linked list is called a node, and each node contains two parts: data and a reference (or link) to the next node in the sequence. This structure allows for efficient insertion and deletion of elements.

Definition and Basic Concepts

Node: The fundamental building block of a linked list. Each node contains data and a reference to the next node.
Head: The first node in a linked list.
Tail: The last node in a linked list, which points to null (or, in circular linked lists, points back to the head).
Pointer/Reference: The link part of the node that points to the next node in the sequence.
Null: Indicates the end of the list.

Advantages of Linked Lists

Dynamic Size: Unlike arrays, linked lists can grow and shrink in size by allocating and deallocating memory as needed.
Ease of Insertion/Deletion: Elements can be inserted or removed without reorganizing the entire data structure. This is particularly useful for applications where frequent addition and removal of elements occur.
Efficient Memory Utilization: Memory is allocated as needed. There is no need to allocate memory for a fixed size in advance.

Disadvantages of Linked Lists

Memory Overhead: Each node requires additional memory for storing the reference to the next node.
Sequential Access: Accessing an element requires traversing from the head to the desired node, resulting in O(n) time complexity for access operations.
Cache Performance: Linked lists may exhibit poor cache performance due to non-contiguous memory allocation, leading to more frequent cache misses.

Applications of Linked Lists

Implementation of Stacks and Queues: Linked lists are used to implement these abstract data types due to their dynamic size and ease of insertion and deletion.
Graph Adjacency List Representation: Linked lists are used to represent adjacency lists in graph algorithms, providing efficient storage and traversal of adjacent vertices.
Dynamic Memory Allocation: Linked lists are used in dynamic memory management systems to keep track of free and allocated memory blocks.
Polynomial Manipulation: Linked lists are used to represent and manipulate polynomials, where each node represents a term of the polynomial.

Representation of Linked Lists

A linked list can be represented as a collection of nodes, where each node contains:

Data: The actual value or information stored in the node.
Next: A reference or pointer to the next node in the list.

This is a simple representation of a singly linked list node in C-like pseudocode:

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

To create a linked list, you need to manage the head of the list and ensure that each node points to the next node. For example:

struct Node* head = NULL;  // Initialize an empty linked list

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

// Function to add a node at the beginning of the list
void insertAtBeginning(int data) {
    struct Node* newNode = createNode(data);
    newNode->next = head;
    head = newNode;
}

In this example, head points to the first node in the list, and each node points to the next node, forming the linked list structure.

Types of Linked Lists

Singly Linked List

A singly linked list is the simplest type of linked list. In this structure, each node contains data and a reference (or link) to the next node in the sequence. The list terminates with a node pointing to null, indicating the end of the list.

Structure of a Singly Linked List Node:

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

Advantages:

Simple to implement.
Efficient insertion and deletion operations, especially at the beginning of the list.

Disadvantages:

Only supports traversal in one direction (forward).
Cannot easily access the previous node without traversing from the head.

Applications:

Implementing stacks and queues.
Basic data storage when dynamic memory allocation is needed.

Doubly Linked List

A doubly linked list is an extension of the singly linked list. Each node contains data and two references: one pointing to the next node and another pointing to the previous node. This allows traversal in both directions.

Structure of a Doubly Linked List Node:

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

Advantages:

Supports efficient bidirectional traversal.
Easier to delete a node when given a reference to it, as the previous node is directly accessible.

Disadvantages:

Requires more memory per node due to the additional reference.
Slightly more complex to implement and manage.

Applications:

Implementing navigation systems (e.g., browsers' forward and backward navigation).
Managing data structures where bidirectional traversal is required.

Circular Linked List

In a circular linked list, the last node's next reference points back to the head of the list, forming a circular structure. Circular linked lists can be either singly or doubly linked.

Structure of a Circular Singly Linked List Node:

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

Advantages:

The list can be traversed from any node.
Efficient for implementing circular buffers or round-robin scheduling.

Disadvantages:

More complex to implement compared to a standard linked list.
Care must be taken to avoid infinite loops during traversal.

Applications:

Implementing circular buffers.
Scheduling algorithms like round-robin.

Header Linked List

A header linked list is a variation of the linked list where an additional node, called the header node, is introduced at the beginning of the list. This header node does not contain meaningful data but serves as a reference point for the start of the list.

Structure of a Header Linked List Node:

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

Header Node:

struct Node* header;
header = (struct Node*)malloc(sizeof(struct Node));
header->next = NULL;  // Initially, the list is empty

Advantages:

Simplifies the implementation by eliminating special cases for the head of the list.
Easier to manage an empty list.

Disadvantages:

Requires an extra node, leading to slight memory overhead.

Applications:

Used in implementations where simplifying list management is beneficial.
Useful in scenarios requiring frequent insertions and deletions at the beginning of the list.

Single Linked List Operations in C

1. Traversal

Traversal is the process of visiting each node in the linked list and performing some operation (e.g., printing the data).

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

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

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

2. Insertion

Insertion can be done at various positions: at the beginning, at the end, or at a specified position.

Insert at Beginning:

// Function to insert a node at the beginning of the linked list
void insertAtBeginning(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = *head_ref;
    *head_ref = new_node;
}

Insert at End:

// Function to insert a node at the end of the linked list
void insertAtEnd(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head_ref;

    new_node->data = new_data;
    new_node->next = NULL;

    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }

    while (last->next != NULL) {
        last = last->next;
    }
    last->next = new_node;
}

Insert at a Given Position:

// Function to insert a node after a given previous node
void insertAfter(struct Node* prev_node, int new_data) {
    if (prev_node == NULL) {
        printf("The given previous node cannot be NULL");
        return;
    }

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = prev_node->next;
    prev_node->next = new_node;
}

3. Deletion

Delete a Node at the Beginning:

cCopy code// Function to delete the first node of the linked list
void deleteAtBeginning(struct Node** head_ref) {
    if (*head_ref == NULL) return;

    struct Node* temp = *head_ref;
    *head_ref = temp->next;
    free(temp);
}

Delete a Node in the Middle (by Key):

cCopy code// Function to delete the first occurrence of a given key in the linked list
void deleteAtMiddle(struct Node** head_ref, int key) {
    struct Node* temp = *head_ref;
    struct Node* prev = NULL;

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

    // Search for the key to be deleted, keeping track of the previous node
    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);
}

Delete the Last Node:

cCopy code// Function to delete the last node of the linked list
void deleteAtEnd(struct Node** head_ref) {
    if (*head_ref == NULL) return;

    struct Node* temp = *head_ref;
    struct Node* prev = NULL;

    // If there is only one node in the list
    if (temp->next == NULL) {
        free(temp);
        *head_ref = NULL;
        return;
    }

    // Traverse to the last node
    while (temp->next != NULL) {
        prev = temp;
        temp = temp->next;
    }

    // Unlink the last node
    prev->next = NULL;
    free(temp);
}

Example program demonstrating all the operations:

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

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

// Function prototypes
void traverse(struct Node* head);
void insertAtBeginning(struct Node** head_ref, int new_data);
void insertAtEnd(struct Node** head_ref, int new_data);
void deleteAtBeginning(struct Node** head_ref);
void deleteAtMiddle(struct Node** head_ref, int key);
void deleteAtEnd(struct Node** head_ref);

int main() {
    struct Node* head = NULL;

    // Insert nodes
    insertAtBeginning(&head, 1);
    insertAtEnd(&head, 2);
    insertAtEnd(&head, 3);
    insertAtEnd(&head, 4);
    printf("Linked List after insertion: ");
    traverse(head);

    // Delete at beginning
    deleteAtBeginning(&head);
    printf("Linked List after deleting at beginning: ");
    traverse(head);

    // Delete node with data 3
    deleteAtMiddle(&head, 3);
    printf("Linked List after deleting node with data 3: ");
    traverse(head);

    // Delete at end
    deleteAtEnd(&head);
    printf("Linked List after deleting at end: ");
    traverse(head);

    return 0;
}

// Function implementations as given above

Doubly Linked List Operations in C

Structure of a Doubly Linked List Node

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

1. Traversal

Code:

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

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

// Function to traverse and print the doubly linked list from the head
void traverseForward(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// Function to traverse and print the doubly linked list from the tail
void traverseBackward(struct Node* tail) {
    struct Node* current = tail;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->prev;
    }
    printf("NULL\n");
}

2. Insertion

Insert at Beginning:

// Function to insert a node at the beginning of the doubly linked list
void insertAtBeginning(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = *head_ref;
    new_node->prev = NULL;

    if (*head_ref != NULL) {
        (*head_ref)->prev = new_node;
    }

    *head_ref = new_node;
}

Insert at End:

// Function to insert a node at the end of the doubly linked list
void insertAtEnd(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head_ref;

    new_node->data = new_data;
    new_node->next = NULL;

    if (*head_ref == NULL) {
        new_node->prev = NULL;
        *head_ref = new_node;
        return;
    }

    while (last->next != NULL) {
        last = last->next;
    }
    last->next = new_node;
    new_node->prev = last;
}

Insert at a Given Position:

// Function to insert a node after a given previous node
void insertAfter(struct Node* prev_node, int new_data) {
    if (prev_node == NULL) {
        printf("The given previous node cannot be NULL");
        return;
    }

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = prev_node->next;
    new_node->prev = prev_node;

    if (prev_node->next != NULL) {
        prev_node->next->prev = new_node;
    }

    prev_node->next = new_node;
}

3. Deletion

Delete a Node at the Beginning:

// Function to delete the first node of the doubly linked list
void deleteAtBeginning(struct Node** head_ref) {
    if (*head_ref == NULL) return;

    struct Node* temp = *head_ref;
    *head_ref = temp->next;

    if (*head_ref != NULL) {
        (*head_ref)->prev = NULL;
    }

    free(temp);
}

Delete a Node in the Middle (by Key):

// Function to delete the first occurrence of a given key in the doubly linked list
void deleteAtMiddle(struct Node** head_ref, int key) {
    struct Node* temp = *head_ref;

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

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

    // Unlink the node from the doubly linked list
    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
    }

    if (temp->prev != NULL) {
        temp->prev->next = temp->next;
    } else { // Node to be deleted is the head node
        *head_ref = temp->next;
    }

    free(temp);
}

Delete the Last Node:

// Function to delete the last node of the doubly linked list
void deleteAtEnd(struct Node** head_ref) {
    if (*head_ref == NULL) return;

    struct Node* temp = *head_ref;

    // Traverse to the last node
    while (temp->next != NULL) {
        temp = temp->next;
    }

    // Unlink the last node
    if (temp->prev != NULL) {
        temp->prev->next = NULL;
    } else { // The list only had one node
        *head_ref = NULL;
    }

    free(temp);
}

Example program demonstrating traversal, insertion at the beginning, middle, and end, and deletion at the beginning, middle, and end:

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

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

// Function prototypes
void traverseForward(struct Node* head);
void traverseBackward(struct Node* tail);
void insertAtBeginning(struct Node** head_ref, int new_data);
void insertAtEnd(struct Node** head_ref, int new_data);
void insertAfter(struct Node* prev_node, int new_data);
void deleteAtBeginning(struct Node** head_ref);
void deleteAtMiddle(struct Node** head_ref, int key);
void deleteAtEnd(struct Node** head_ref);

int main() {
    struct Node* head = NULL;

    // Insert nodes
    insertAtBeginning(&head, 1);
    insertAtEnd(&head, 2);
    insertAtEnd(&head, 3);
    insertAfter(head->next, 4);

    printf("Doubly Linked List after insertion: ");
    traverseForward(head);

    // Delete at beginning
    deleteAtBeginning(&head);
    printf("Doubly Linked List after deleting at beginning: ");
    traverseForward(head);

    // Delete node with data 3
    deleteAtMiddle(&head, 3);
    printf("Doubly Linked List after deleting node with data 3: ");
    traverseForward(head);

    // Delete at end
    deleteAtEnd(&head);
    printf("Doubly Linked List after deleting at end: ");
    traverseForward(head);

    return 0;
}

// Function implementations as given above

Circular Linked List Operations in C

Structure of a Circular Linked List Node

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

1. Traversal

Traversal in a circular linked list involves starting from the head and continuing until we reach the head again.

Code:

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

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

// Function to traverse and print the circular linked list
void traverse(struct Node* head) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node* current = head;
    do {
        printf("%d -> ", current->data);
        current = current->next;
    } while (current != head);
    printf("(head)\n");
}

2. Insertion

Insertion in a circular linked list can be done at the beginning, end, or after a given node.

Insert at Beginning:

// Function to insert a node at the beginning of the circular linked list
void insertAtBeginning(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head_ref;

    new_node->data = new_data;
    new_node->next = *head_ref;

    if (*head_ref != NULL) {
        while (last->next != *head_ref) {
            last = last->next;
        }
        last->next = new_node;
    } else {
        new_node->next = new_node; // For the first node
    }

    *head_ref = new_node;
}

Insert at End:

// Function to insert a node at the end of the circular linked list
void insertAtEnd(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head_ref;

    new_node->data = new_data;
    new_node->next = *head_ref;

    if (*head_ref == NULL) {
        new_node->next = new_node;
        *head_ref = new_node;
        return;
    }

    while (last->next != *head_ref) {
        last = last->next;
    }
    last->next = new_node;
}

Insert After a Given Node:

// Function to insert a node after a given node in the circular linked list
void insertAfter(struct Node* prev_node, int new_data) {
    if (prev_node == NULL) {
        printf("The given previous node cannot be NULL");
        return;
    }

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = prev_node->next;
    prev_node->next = new_node;
}

3. Deletion

Delete a Node at the Beginning:

// Function to delete the first node of the circular linked list
void deleteAtBeginning(struct Node** head_ref) {
    if (*head_ref == NULL) return;

    struct Node* last = *head_ref;
    struct Node* temp = *head_ref;

    if ((*head_ref)->next == *head_ref) {
        *head_ref = NULL;
        free(temp);
        return;
    }

    while (last->next != *head_ref) {
        last = last->next;
    }
    last->next = (*head_ref)->next;
    *head_ref = (*head_ref)->next;
    free(temp);
}

Delete a Node by Key:

// Function to delete the first occurrence of a given key in the circular linked list
void deleteAtMiddle(struct Node** head_ref, int key) {
    if (*head_ref == NULL) return;

    struct Node* temp = *head_ref;
    struct Node* prev = NULL;

    while (temp->data != key) {
        if (temp->next == *head_ref) {
            printf("Given node not found in the list\n");
            return;
        }
        prev = temp;
        temp = temp->next;
    }

    if (temp == *head_ref && temp->next == *head_ref) {
        *head_ref = NULL;
        free(temp);
        return;
    }

    if (temp == *head_ref) {
        prev = *head_ref;
        while (prev->next != *head_ref) {
            prev = prev->next;
        }
        *head_ref = temp->next;
        prev->next = *head_ref;
        free(temp);
    } else if (temp->next == *head_ref) {
        prev->next = *head_ref;
        free(temp);
    } else {
        prev->next = temp->next;
        free(temp);
    }
}

Delete the Last Node:

// Function to delete the last node of the circular linked list
void deleteAtEnd(struct Node** head_ref) {
    if (*head_ref == NULL) return;

    struct Node* last = *head_ref;
    struct Node* prev = NULL;

    if (last->next == *head_ref) {
        *head_ref = NULL;
        free(last);
        return;
    }

    while (last->next != *head_ref) {
        prev = last;
        last = last->next;
    }
    prev->next = *head_ref;
    free(last);
}

Example program demonstrating traversal, insertion at the beginning, middle, and end, and deletion at the beginning, middle, and end:

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

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

// Function prototypes
void traverse(struct Node* head);
void insertAtBeginning(struct Node** head_ref, int new_data);
void insertAtEnd(struct Node** head_ref, int new_data);
void insertAfter(struct Node* prev_node, int new_data);
void deleteAtBeginning(struct Node** head_ref);
void deleteAtMiddle(struct Node** head_ref, int key);
void deleteAtEnd(struct Node** head_ref);

int main() {
    struct Node* head = NULL;

    // Insert nodes
    insertAtBeginning(&head, 1);
    insertAtEnd(&head, 2);
    insertAtEnd(&head, 3);
    insertAfter(head->next, 4);

    printf("Circular Linked List after insertion: ");
    traverse(head);

    // Delete at beginning
    deleteAtBeginning(&head);
    printf("Circular Linked List after deleting at beginning: ");
    traverse(head);

    // Delete node with data 3
    deleteAtMiddle(&head, 3);
    printf("Circular Linked List after deleting node with data 3: ");
    traverse(head);

    // Delete at end
    deleteAtEnd(&head);
    printf("Circular Linked List after deleting at end: ");
    traverse(head);

    return 0;
}

// Function implementations as given above

Polynomial Representation Using Linked Lists

Polynomials can be represented using linked lists where each node represents a term of the polynomial. Each node contains the coefficient and exponent of the term, along with a pointer to the next term.

Structure of a Polynomial Node

struct Node {
    int coeff;
    int exp;
    struct Node* next;
};

Polynomial Operations

Code:

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

struct Node {
    int coeff;
    int exp;
    struct Node* next;
};

// Function prototypes
struct Node* createNode(int coeff, int exp);
void insertNode(struct Node** poly, int coeff, int exp);
void printPolynomial(struct Node* poly);
struct Node* addPolynomials(struct Node* poly1, struct Node* poly2);
struct Node* subtractPolynomials(struct Node* poly1, struct Node* poly2);
struct Node* multiplyPolynomials(struct Node* poly1, struct Node* poly2);
struct Node* dividePolynomials(struct Node* poly1, struct Node* poly2, struct Node** remainder);

// Main function
int main() {
    struct Node* poly1 = NULL;
    struct Node* poly2 = NULL;
    struct Node* quotient = NULL;
    struct Node* remainder = NULL;

    // Create first polynomial: 5x^2 + 4x + 2
    insertNode(&poly1, 5, 2);
    insertNode(&poly1, 4, 1);
    insertNode(&poly1, 2, 0);

    // Create second polynomial: x + 1
    insertNode(&poly2, 1, 1);
    insertNode(&poly2, 1, 0);

    printf("Polynomial 1: ");
    printPolynomial(poly1);

    printf("Polynomial 2: ");
    printPolynomial(poly2);

    quotient = dividePolynomials(poly1, poly2, &remainder);

    printf("Quotient: ");
    printPolynomial(quotient);

    printf

("Remainder: ");
    printPolynomial(remainder);

    return 0;
}

// Function to create a new node
struct Node* createNode(int coeff, int exp) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->coeff = coeff;
    new_node->exp = exp;
    new_node->next = NULL;
    return new_node;
}

// Function to insert a new node into the polynomial linked list
void insertNode(struct Node** poly, int coeff, int exp) {
    struct Node* new_node = createNode(coeff, exp);
    if (*poly == NULL) {
        *poly = new_node;
    } else {
        struct Node* temp = *poly;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = new_node;
    }
}

// Function to print the polynomial linked list
void printPolynomial(struct Node* poly) {
    while (poly != NULL) {
        printf("%dx^%d", poly->coeff, poly->exp);
        poly = poly->next;
        if (poly != NULL) printf(" + ");
    }
    printf("\n");
}

// Function to add two polynomials
struct Node* addPolynomials(struct Node* poly1, struct Node* poly2) {
    struct Node* result = NULL;
    while (poly1 != NULL && poly2 != NULL) {
        if (poly1->exp > poly2->exp) {
            insertNode(&result, poly1->coeff, poly1->exp);
            poly1 = poly1->next;
        } else if (poly1->exp < poly2->exp) {
            insertNode(&result, poly2->coeff, poly2->exp);
            poly2 = poly2->next;
        } else {
            insertNode(&result, poly1->coeff + poly2->coeff, poly1->exp);
            poly1 = poly1->next;
            poly2 = poly2->next;
        }
    }
    while (poly1 != NULL) {
        insertNode(&result, poly1->coeff, poly1->exp);
        poly1 = poly1->next;
    }
    while (poly2 != NULL) {
        insertNode(&result, poly2->coeff, poly2->exp);
        poly2 = poly2->next;
    }
    return result;
}

// Function to subtract two polynomials
struct Node* subtractPolynomials(struct Node* poly1, struct Node* poly2) {
    struct Node* result = NULL;
    while (poly1 != NULL && poly2 != NULL) {
        if (poly1->exp > poly2->exp) {
            insertNode(&result, poly1->coeff, poly1->exp);
            poly1 = poly1->next;
        } else if (poly1->exp < poly2->exp) {
            insertNode(&result, -poly2->coeff, poly2->exp);
            poly2 = poly2->next;
        } else {
            insertNode(&result, poly1->coeff - poly2->coeff, poly1->exp);
            poly1 = poly1->next;
            poly2 = poly2->next;
        }
    }
    while (poly1 != NULL) {
        insertNode(&result, poly1->coeff, poly1->exp);
        poly1 = poly1->next;
    }
    while (poly2 != NULL) {
        insertNode(&result, -poly2->coeff, poly2->exp);
        poly2 = poly2->next;
    }
    return result;
}

// Function to multiply two polynomials
struct Node* multiplyPolynomials(struct Node* poly1, struct Node* poly2) {
    struct Node* result = NULL;

    struct Node* poly1_temp = poly1;
    struct Node* poly2_temp = poly2;

    while (poly1_temp != NULL) {
        while (poly2_temp != NULL) {
            int coeff = poly1_temp->coeff * poly2_temp->coeff;
            int exp = poly1_temp->exp + poly2_temp->exp;
            insertNode(&result, coeff, exp);
            poly2_temp = poly2_temp->next;
        }
        poly2_temp = poly2;
        poly1_temp = poly1_temp->next;
    }

    return result;
}

// Function to divide two polynomials
struct Node* dividePolynomials(struct Node* poly1, struct Node* poly2, struct Node** remainder) {
    struct Node* quotient = NULL;
    *remainder = poly1;

    while (*remainder != NULL && (*remainder)->exp >= poly2->exp) {
        int coeff = (*remainder)->coeff / poly2->coeff;
        int exp = (*remainder)->exp - poly2->exp;
        insertNode(&quotient, coeff, exp);

        struct Node* term = createNode(coeff, exp);
        struct Node* temp = multiplyPolynomials(poly2, term);
        *remainder = subtractPolynomials(*remainder, temp);
    }

    return quotient;
}

Problems:

Reverse a Single Linked List: Develop a C function to reverse a single linked list. The function should return the head of the reversed list.
Detect a Cycle in a Single Linked List: Write a C program to detect whether a cycle (loop) exists in a single linked list. Use Floyd’s Cycle-Finding Algorithm (Tortoise and Hare).
Merge Two Sorted Single Linked Lists: Implement a function in C to merge two sorted single linked lists into one sorted list. The merged list should maintain the sorted order.
Find the Middle of a Single Linked List: Write a C function to find the middle element of a single linked list. If the list has an even number of nodes, return the second middle element.
Convert a Single Linked List into a Circular Linked List: Write a C program to convert a single linked list into a circular linked list by linking the last node to the first node.

Solutions:

1. Reverse a Single Linked List

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

// Definition for the singly linked list node
struct Node {
    int data;
    struct Node* next;
};

// Function to reverse a singly linked list
struct Node* reverseList(struct Node* head) {
    struct Node* prev = NULL;
    struct Node* current = head;
    struct Node* next = NULL;

    while (current != NULL) {
        next = current->next; // Store the next node
        current->next = prev;  // Reverse the current node's pointer
        prev = current;        // Move pointers one position ahead
        current = next;
    }
    return prev; // New head of the reversed list
}

// Utility function to print the list
void printList(struct Node* head) {
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

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

int main() {
    // Creating a simple linked list 1->2->3->4->NULL
    struct Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);

    printf("Original List: ");
    printList(head);

    head = reverseList(head);

    printf("Reversed List: ");
    printList(head);

    return 0;
}

2. Detect a Cycle in a Single Linked List (Floyd's Cycle-Finding Algorithm)

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

// Definition for the singly linked list node
struct Node {
    int data;
    struct Node* next;
};

// Function to detect a cycle in the linked list
int detectCycle(struct Node* head) {
    struct Node* slow = head;
    struct Node* fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;           // Move slow pointer by one step
        fast = fast->next->next;     // Move fast pointer by two steps

        if (slow == fast) { // Cycle detected
            return 1;
        }
    }
    return 0; // No cycle detected
}

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

int main() {
    // Creating a linked list with a cycle: 1->2->3->4->2 (cycle)
    struct Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = head->next; // Creating a cycle

    if (detectCycle(head))
        printf("Cycle detected\n");
    else
        printf("No cycle detected\n");

    return 0;
}

3. Merge Two Sorted Single Linked Lists

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

// Definition for the singly linked list node
struct Node {
    int data;
    struct Node* next;
};

// Function to merge two sorted linked lists
struct Node* mergeLists(struct Node* l1, struct Node* l2) {
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;

    struct Node* result = NULL;

    // Choose either l1 or l2, and recursively merge the remaining lists
    if (l1->data <= l2->data) {
        result = l1;
        result->next = mergeLists(l1->next, l2);
    } else {
        result = l2;
        result->next = mergeLists(l1, l2->next);
    }
    return result;
}

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

// Utility function to print the list
void printList(struct Node* head) {
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

int main() {
    // Creating two sorted lists: 1->3->5->NULL and 2->4->6->NULL
    struct Node* l1 = newNode(1);
    l1->next = newNode(3);
    l1->next->next = newNode(5);

    struct Node* l2 = newNode(2);
    l2->next = newNode(4);
    l2->next->next = newNode(6);

    printf("List 1: ");
    printList(l1);

    printf("List 2: ");
    printList(l2);

    struct Node* mergedList = mergeLists(l1, l2);

    printf("Merged List: ");
    printList(mergedList);

    return 0;
}

4. Find the Middle of a Single Linked List

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

// Definition for the singly linked list node
struct Node {
    int data;
    struct Node* next;
};

// Function to find the middle of the linked list
struct Node* findMiddle(struct Node* head) {
    struct Node* slow = head;
    struct Node* fast = head;

    // Move fast pointer by 2 steps and slow by 1 step
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow; // Slow pointer is now at the middle
}

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

// Utility function to print the list
void printList(struct Node* head) {
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

int main() {
    // Creating a simple linked list 1->2->3->4->5->NULL
    struct Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);

    printf("List: ");
    printList(head);

    struct Node* middle = findMiddle(head);
    if (middle != NULL)
        printf("Middle element is %d\n", middle->data);

    return 0;
}

5. Convert a Single Linked List into a Circular Linked List

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

// Definition for the singly linked list node
struct Node {
    int data;
    struct Node* next;
};

// Function to convert a singly linked list into a circular linked list
void convertToCircular(struct Node* head) {
    if (head == NULL) return;

    struct Node* temp = head;

    // Traverse the list till the last node
    while (temp->next != NULL) {
        temp = temp->next;
    }
    // Link the last node to the first node
    temp->next = head;
}

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

// Utility function to print the list (for circular, stops at the starting node)
void printCircularList(struct Node* head) {
    if (head == NULL) return;

    struct Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("(back to start)\n");
}

int main() {
    // Creating a simple linked list 1->2->3->4->NULL
    struct Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);

    printf("Original List: ");
    printCircularList(head);

    convertToCircular(head);

    printf("Circular List: ");
    printCircularList(head);

    return 0;
}

Introduction to Linked Lists

Comments

More from this blog

Computer Arithmetic: From Fast Adders to Floating-Point

The Complete Memory Hierarchy: From Semiconductor RAM to Virtual Memory

The Ultimate Spring Boot Guide: From Fundamentals to Production-Ready REST APIs

Understanding Functions, Memory, and Pointers in C: A Complete Guide

Datapath and Control

Overview of Linked Lists

Definition and Basic Concepts

Advantages of Linked Lists

Disadvantages of Linked Lists

Applications of Linked Lists

Representation of Linked Lists

Types of Linked Lists

Singly Linked List

Doubly Linked List

Circular Linked List

Header Linked List

Single Linked List Operations in C

1. Traversal

2. Insertion

3. Deletion

Doubly Linked List Operations in C

Structure of a Doubly Linked List Node

1. Traversal

2. Insertion

3. Deletion

Circular Linked List Operations in C

Structure of a Circular Linked List Node

1. Traversal

2. Insertion

3. Deletion

Polynomial Representation Using Linked Lists

Structure of a Polynomial Node

Polynomial Operations

Command Palette

Comments

More from this blog

Overview of Linked Lists

Definition and Basic Concepts

Advantages of Linked Lists

Disadvantages of Linked Lists

Applications of Linked Lists

Representation of Linked Lists

Types of Linked Lists

Singly Linked List

Doubly Linked List

Circular Linked List

Header Linked List

Single Linked List Operations in C

1. Traversal

2. Insertion

3. Deletion

Doubly Linked List Operations in C

Structure of a Doubly Linked List Node

1. Traversal

2. Insertion

3. Deletion

Circular Linked List Operations in C

Structure of a Circular Linked List Node

1. Traversal

2. Insertion

3. Deletion

Polynomial Representation Using Linked Lists

Structure of a Polynomial Node

Polynomial Operations