Skip to main content

3. Singly Linked List Operations

3.1 Creating an Empty List

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

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

// Initialize head pointer
struct Node *head = NULL;

3.2 Insertion Operations

3.2.1 Insert at Beginning

void insertAtBeginning(struct Node **head, int value) {
    // Create new node
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        return;
    }
    
    // Set data and next pointer
    newNode->data = value;
    newNode->next = *head;
    
    // Update head
    *head = newNode;
}

// Usage
int main() {
    struct Node *head = NULL;
    
    insertAtBeginning(&head, 30);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 10);
    
    // List now: 10 → 20 → 30 → NULL
    
    return 0;
}

Visual Steps:

Initial: head → NULL

Step 1: Create node with data = 10
newNode → [10|NULL]

Step 2: Point newNode->next to current head
newNode → [10|●] → NULL

Step 3: Update head to newNode
head → [10|NULL]

Step 4: Insert 20
head → [20|●] → [10|NULL]

Step 5: Insert 30
head → [30|●] → [20|●] → [10|NULL]

Time Complexity: O(1) Space Complexity: O(1)

3.2.2 Insert at End

void insertAtEnd(struct Node **head, int value) {
    // Create new node
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        return;
    }
    
    newNode->data = value;
    newNode->next = NULL;
    
    // If list is empty
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    // Traverse to last node
    struct Node *temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    
    // Insert at end
    temp->next = newNode;
}

Visual Steps:

List: head → [10|●] → [20|●] → [30|NULL]

Step 1: Create newNode with data = 40
newNode → [40|NULL]

Step 2: Traverse to last node
temp moves: [10] → [20] → [30]

Step 3: Connect last node to newNode
head → [10|●] → [20|●] → [30|●] → [40|NULL]

Time Complexity: O(n) - must traverse entire list Space Complexity: O(1)

3.2.3 Insert at Position

void insertAtPosition(struct Node **head, int value, int position) {
    // Create new node
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        return;
    }
    
    newNode->data = value;
    
    // Insert at beginning (position 0)
    if (position == 0) {
        newNode->next = *head;
        *head = newNode;
        return;
    }
    
    // Traverse to position-1
    struct Node *temp = *head;
    for (int i = 0; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    
    // Check if position is valid
    if (temp == NULL) {
        printf("Invalid position!\n");
        free(newNode);
        return;
    }
    
    // Insert node
    newNode->next = temp->next;
    temp->next = newNode;
}

Visual Steps (Insert 25 at position 2):

Initial: head → [10|●] → [20|●] → [30|NULL]
                  0        1        2

Step 1: Create newNode [25|NULL]

Step 2: Traverse to position 1 (position - 1)
temp → [20|●]

Step 3: Connect newNode
newNode->next = temp->next  (points to 30)
[25|●] → [30|NULL]

Step 4: Connect temp to newNode
temp->next = newNode
head → [10|●] → [20|●] → [25|●] → [30|NULL]

Time Complexity: O(n) Space Complexity: O(1)

3.3 Deletion Operations

3.3.1 Delete from Beginning

void deleteFromBeginning(struct Node **head) {
    // Check if list is empty
    if (*head == NULL) {
        printf("List is empty!\n");
        return;
    }
    
    // Store current head
    struct Node *temp = *head;
    
    // Move head to next node
    *head = (*head)->next;
    
    // Free old head
    free(temp);
}

Visual Steps:

Initial: head → [10|●] → [20|●] → [30|NULL]

Step 1: temp = head
temp → [10|●] → [20|●] → [30|NULL]
head → [10|●] → [20|●] → [30|NULL]

Step 2: head = head->next
head → [20|●] → [30|NULL]
temp → [10|●] (to be freed)

Step 3: free(temp)
head → [20|●] → [30|NULL]

Time Complexity: O(1) Space Complexity: O(1)

3.3.2 Delete from End

void deleteFromEnd(struct Node **head) {
    // Check if list is empty
    if (*head == NULL) {
        printf("List is empty!\n");
        return;
    }
    
    // If only one node
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }
    
    // Traverse to second-last node
    struct Node *temp = *head;
    while (temp->next->next != NULL) {
        temp = temp->next;
    }
    
    // Delete last node
    free(temp->next);
    temp->next = NULL;
}

Visual Steps:

Initial: head → [10|●] → [20|●] → [30|NULL]

Step 1: Traverse to second-last node
temp → [20|●] → [30|NULL]

Step 2: Free last node
free(temp->next)

Step 3: Set second-last to NULL
head → [10|●] → [20|NULL]

Time Complexity: O(n) Space Complexity: O(1)

3.3.3 Delete at Position

void deleteAtPosition(struct Node **head, int position) {
    // Check if list is empty
    if (*head == NULL) {
        printf("List is empty!\n");
        return;
    }
    
    // Delete first node
    if (position == 0) {
        struct Node *temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }
    
    // Traverse to position-1
    struct Node *temp = *head;
    for (int i = 0; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    
    // Check if position is valid
    if (temp == NULL || temp->next == NULL) {
        printf("Invalid position!\n");
        return;
    }
    
    // Delete node
    struct Node *nodeToDelete = temp->next;
    temp->next = nodeToDelete->next;
    free(nodeToDelete);
}

Time Complexity: O(n) Space Complexity: O(1)

3.3.4 Delete by Value

void deleteByValue(struct Node **head, int value) {
    // Check if list is empty
    if (*head == NULL) {
        printf("List is empty!\n");
        return;
    }
    
    // If head node contains the value
    if ((*head)->data == value) {
        struct Node *temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }
    
    // Search for the node
    struct Node *temp = *head;
    while (temp->next != NULL && temp->next->data != value) {
        temp = temp->next;
    }
    
    // If value not found
    if (temp->next == NULL) {
        printf("Value %d not found!\n", value);
        return;
    }
    
    // Delete node
    struct Node *nodeToDelete = temp->next;
    temp->next = nodeToDelete->next;
    free(nodeToDelete);
}

Time Complexity: O(n) Space Complexity: O(1)

3.4 Traversal and Display

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

// Alternative: Using for loop
void displayList2(struct Node *head) {
    printf("List: ");
    for (struct Node *temp = head; temp != NULL; temp = temp->next) {
        printf("%d → ", temp->data);
    }
    printf("NULL\n");
}

Time Complexity: O(n) Space Complexity: O(1)

3.5 Searching

int search(struct Node *head, int value) {
    struct Node *temp = head;
    int position = 0;
    
    while (temp != NULL) {
        if (temp->data == value) {
            return position;  // Found at position
        }
        temp = temp->next;
        position++;
    }
    
    return -1;  // Not found
}

// Usage
int main() {
    struct Node *head = NULL;
    
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    
    int pos = search(head, 20);
    if (pos != -1) {
        printf("Found at position: %d\n", pos);
    } else {
        printf("Not found!\n");
    }
    
    return 0;
}

Time Complexity: O(n) Space Complexity: O(1)

3.6 Length of List

int getLength(struct Node *head) {
    int count = 0;
    struct Node *temp = head;
    
    while (temp != NULL) {
        count++;
        temp = temp->next;
    }
    
    return count;
}

// Recursive version
int getLengthRecursive(struct Node *head) {
    if (head == NULL) {
        return 0;
    }
    return 1 + getLengthRecursive(head->next);
}

Time Complexity: O(n) Space Complexity: O(1) for iterative, O(n) for recursive

No comments to display

Back to top