Linked List in C

Introduction to Linked Lists in C

Linked List in C: A linked list is a linear data structure where elements, called nodes, are stored in a sequence, with each node containing a reference (or link) to the next node in the sequence. This makes linked lists different from arrays, which store elements in contiguous memory locations. Before going through the Linked list you must have the knowledge of pointers in C then it will be very easy to understand this example.

Types of Linked Lists in C

• Singly Linked List: Each node points to the next node and the last node points to null.
• Doubly Linked List: Each node has two links, one to the next node and one to the previous node.
• Circular Linked List: The last node points back to the first node instead of null.

In this explanation, we will focus on the Singly Linked List.

Components of a Single Linked List in C

• Node: Contains data and a reference to the next node.
• Head: The first node in the list.
• Tail: (optional) The last node in the list which points to null.

Operations on a Singly Linked List in C

Structure Definitions of Single Linked List in C

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

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

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

Inserting a Node in Singly Linked List in C

a. At the Beginning

void insert_at_beginning(struct Node** head, int data) 
{
    struct Node* new_node = create_node(data);
    new_node->next = *head;
    *head = new_node;
}

b. At the End

void insert_at_end(struct Node** head, int data) {
    struct Node* new_node = create_node(data);
    if (*head == NULL) {
        *head = new_node;
        return;
    }
    struct Node* last_node = *head;
    while (last_node->next != NULL) {
        last_node = last_node->next;
    }
    last_node->next = new_node;
}

c. After a Specific Node

void insert_after_node(struct Node* prev_node, int data) {
    if (prev_node == NULL) {
        printf("The given previous node cannot be NULL.\n");
        return;
    }
    struct Node* new_node = create_node(data);
    new_node->next = prev_node->next;
    prev_node->next = new_node;
}

Deleting a Node in Singly Linked List in C

a. By Value

void delete_node(struct Node** head, int key) {
    struct Node* temp = *head, *prev = NULL;

    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return;

    prev->next = temp->next;
    free(temp);
}

b. By Position

void delete_node_at_position(struct Node** head, int position) {
    if (*head == NULL) return;

    struct Node* temp = *head;

    if (position == 0) {
        *head = temp->next;
        free(temp);
        return;
    }

    for (int i = 0; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }

    if (temp == NULL || temp->next == NULL) return;

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

Updating a Node in Single Linked List in C

void update_node(struct Node* head, int old_data, int new_data) {
    struct Node* current = head;

    while (current != NULL) {
        if (current->data == old_data) {
            current->data = new_data;
            return;
        }
        current = current->next;
    }

    printf("Node with data %d not found.\n", old_data);
}

Printing the Single Linked List in C

void print_list(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

Example Usage

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

    // Inserting nodes
    insert_at_end(&head, 1);
    insert_at_end(&head, 2);
    insert_at_end(&head, 3);

    // Inserting at the beginning
    insert_at_beginning(&head, 0);

    // Inserting after a specific node
    insert_after_node(head->next, 1.5);

    // Printing the list
    print_list(head);  // Output: 0 -> 1 -> 1.5 -> 2 -> 3 -> NULL

    // Updating a node
    update_node(head, 1.5, 4);
    print_list(head);  // Output: 0 -> 1 -> 4 -> 2 -> 3 -> NULL

    // Deleting a node by value
    delete_node(&head, 4);
    print_list(head);  // Output: 0 -> 1 -> 2 -> 3 -> NULL

    // Deleting a node by position
    delete_node_at_position(&head, 2);
    print_list(head);  // Output: 0 -> 1 -> 3 -> NULL

    return 0;
}

This example demonstrates how to create, insert, update, and delete nodes in a singly linked list using C.