Operations on a Linked List: Insertion, Deletion, and Traversal

 Operations on a Linked List: Insertion, Deletion, and Traversal

A linked list is a fundamental data structure that allows dynamic memory allocation and efficient insertions and deletions. Unlike arrays, linked lists do not require contiguous memory allocation, making them flexible for handling data in real-time applications. In this post, we will explore the three primary operations on linked lists: Insertion, Deletion, and Traversal.

---

1. Insertion in a Linked List

Insertion refers to adding a new node at various positions in a linked list. There are three common ways to insert a node:

(a) Insertion at the Beginning (Head Insertion)

• The new node becomes the head of the list.
• The new node's next pointer is assigned to the previous head.
• The head pointer is updated to the new node.

Example (C Code for Head Insertion in a Singly Linked List):

void insertAtBeginning(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

🔹 Time Complexity: O(1) (Constant time insertion)

---

(b) Insertion at the End (Tail Insertion)

• The new node is appended after the last node.
• The last node's next pointer is updated to point to the new node.

Example (C Code for Tail Insertion in a Singly Linked List):

void insertAtEnd(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;

    if (*head == NULL) {
        *head = newNode;
        return;
    }

    struct Node* temp = *head;
    while (temp->next != NULL)
        temp = temp->next;

    temp->next = newNode;
}

🔹 Time Complexity: O(n) (Requires traversing to the last node)

---

(c) Insertion at a Specific Position

• The new node is inserted after a given position in the list.
• The next pointer of the new node is set to the next node in the list.
• The previous node’s next pointer is updated to point to the new node.

Example (C Code for Insertion at a Specific Position):

void insertAtPosition(struct Node** head, int data, int position) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;

    if (position == 1) {
        newNode->next = *head;
        *head = newNode;
        return;
    }

    struct Node* temp = *head;
    for (int i = 1; temp != NULL && i < position - 1; i++)
        temp = temp->next;

    if (temp == NULL) return;

    newNode->next = temp->next;
    temp->next = newNode;
}

🔹 Time Complexity: O(n) (Worst case requires traversing to the desired position)

---

2. Deletion in a Linked List

Deletion involves removing a node from the linked list. There are three common ways to delete a node:

(a) Deletion at the Beginning (Head Deletion)

• The head pointer is updated to the next node.
• The old head node is freed from memory.

Example (C Code for Head Deletion in a Singly Linked List):

void deleteAtBeginning(struct Node** head) {
    if (*head == NULL) return;

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

🔹 Time Complexity: O(1) (Constant time deletion)

---

(b) Deletion at the End (Tail Deletion)

• The last node is removed.
• The second last node's next pointer is updated to NULL.

Example (C Code for Tail Deletion in a Singly Linked List):

void deleteAtEnd(struct Node** head) {
    if (*head == NULL) return;
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }

    struct Node* temp = *head;
    while (temp->next->next != NULL)
        temp = temp->next;

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

🔹 Time Complexity: O(n) (Requires traversing to the second last node)

---

(c) Deletion at a Specific Position

• The previous node’s next pointer is updated to skip the node to be deleted.
• The node is freed from memory.

Example (C Code for Deletion at a Specific Position):

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

    struct Node* temp = *head;

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

    for (int i = 1; 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;
}

🔹 Time Complexity: O(n) (Worst case requires traversing to the position)

---

3. Traversal in a Linked List

Traversal means accessing each node in the linked list sequentially.

(a) Iterative Traversal

• Use a loop to visit each node.

Example (C Code for Iterative Traversal):

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

🔹 Time Complexity: O(n)

---

(b) Recursive Traversal

• Uses function recursion to traverse each node.

Example (C Code for Recursive Traversal):

void recursiveTraverse(struct Node* head) {
    if (head == NULL) {
        printf("NULL\n");
        return;
    }
    printf("%d -> ", head->data);
    recursiveTraverse(head->next);
}

🔹 Time Complexity: O(n)