Linked Lists Operations

Index

Operations

Linked lists support various operations for manipulating the data they contain. Here are some common operations performed on linked lists:

Traversal

2. Insertion

3. Deletion

4. Sorting

1. Traversal of a linked list

Traversal of a linked list involves visiting each node in the list in order to access or manipulate its data. This process typically requires starting from the head (or start) of the list and moving through each node until the end of the list is reached. Here’s a basic example of how traversal of a singly linked list can be implemented in C:

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

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

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

int main() {
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    struct Node* second = (struct Node*)malloc(sizeof(struct Node));
    struct Node* third = (struct Node*)malloc(sizeof(struct Node));

    head->data = 1;
    head->next = second;
    second->data = 2;
    second->next = third;
    third->data = 3;
    third->next = NULL; // End of the list

    printf("Linked list elements: ");
    traverseLinkedList(head);

    free(head);
    free(second);
    free(third);

    return 0;
}

Output:

Linked list elements: 1 2 3

Code Explanation

Defining a Node Structure

A linked list consists of nodes, where each node contains data and a pointer to the next node.

struct Node {
    int data; // Stores the data value
    struct Node* next; // Pointer to the next node
};

Here, struct Node* next points to the next node in the linked list.

2. Function to Traverse the Linked List

void traverseLinkedList(struct Node* head) {
3. Creating Nodes Dynamically    struct Node* current = head; // Start from the head node
    while (current != NULL) { // Loop until the end of the list
        printf("%d ", current->data); // Print the current node's data
        current = current->next; // Move to the next node
    }
    printf("\n");
}

This function starts from the head node and moves through each node while printing its data.

3. Creating Nodes Dynamically

Inside the main() function, we dynamically allocate memory for three nodes:

struct Node* head = (struct Node*)malloc(sizeof(struct Node));
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
struct Node* third = (struct Node*)malloc(sizeof(struct Node));

malloc() is used to allocate memory for each node.
Each node stores an integer value and a pointer to the next node.

4. Linking the Nodes

head->data = 1; 
head->next = second; // Link first node to second

second->data = 2;
second->next = third; // Link second node to third

third->data = 3;
third->next = NULL; // Marking end of the list

The first node (head) contains 1 and points to second.
The second node contains 2 and points to third.
The third node contains 3 and points to NULL, indicating the end of the list.

5. Traversing and Printing the Linked List

printf("Linked list elements: ");
traverseLinkedList(head);

Calls the function to print the linked list elements.

Output

Linked list elements: 1 2 3

6. Freeing the Allocated Memory

free(head);
free(second);
free(third);

Since we used malloc(), we must free() the memory to prevent memory leaks

2. Delete a Node in a Linked List

Deleting a node in a linked list involves removing a specific node from the list while maintaining the integrity of the list’s structure. There are several cases to consider when deleting a node:

Deleting the head node.
Deleting a node in the middle of the list.
Deleting the last node in the list.

Here’s how you can implement a function to delete a node with a given value from a singly linked list in C:

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

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

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

Node* deleteSpecificNode(Node* head, Node* nodeToDelete) {
    if (head == nodeToDelete) {
        Node* newHead = head->next;
        free(head);
        return newHead;
    }

    Node* currentNode = head;
    while (currentNode->next && currentNode->next != nodeToDelete) {
        currentNode = currentNode->next;
    }

    if (currentNode->next == NULL) {
        return head;
    }

    Node* temp = currentNode->next;
    currentNode->next = currentNode->next->next;
    free(temp);

    return head;
}

int main() {
    Node* node1 = malloc(sizeof(Node));
    node1->data = 3;
    Node* node2 = malloc(sizeof(Node));
    node2->data = 1;
    Node* node3 = malloc(sizeof(Node));
    node3->data = 6;
    Node* node4 = malloc(sizeof(Node));
    node4->data = 7;
    Node* node5 = malloc(sizeof(Node));
    node5->data = 9;

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;

    printf("Before deletion:\n");
    traverseAndPrint(node1);

    node1 = deleteSpecificNode(node1, node4);

    printf("\nAfter deletion:\n");
    traverseAndPrint(node1);

    free(node1);
    free(node2);
    free(node3);
    free(node5);

    return 0;
}

Output:

Before deletion:
3 -> 1 -> 6 -> 7 -> 9 -> null

After deletion:
3 -> 1 -> 6 -> 9 -> null

Code Explanation

Defining a Node Using typedef struct

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

Here, Node is a structure that contains:

data: an integer to store the value of the node.
next: a pointer to the next node in the linked list.

2. Function to Traverse and Print the Linked List

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

This function prints the elements of the linked list.
It starts from the head node and follows the next pointers until it reaches NULL.

3. Function to Delete a Specific Node

Node* deleteSpecificNode(Node* head, Node* nodeToDelete) {
    if (head == nodeToDelete) { // If the node to delete is the head
        Node* newHead = head->next;
        free(head);
        return newHead;
    }

    Node* currentNode = head;
    while (currentNode->next && currentNode->next != nodeToDelete) {
        currentNode = currentNode->next;
    }

    if (currentNode->next == NULL) { // If node not found, return head unchanged
        return head;
    }

    Node* temp = currentNode->next;
    currentNode->next = currentNode->next->next; // Bypass the node to delete
    free(temp);

    return head;
}

How the deletion works:

If the node to delete is the head:
- Update head to head->next and free the old head.
Traverse the list to find the node to delete:
- Stop at the node just before the target node.
If the node is found:
- Change currentNode->next to currentNode->next->next, effectively skipping the node.
- Free the memory of the deleted node.

4. Creating and Linking Nodes in main()

Node* node1 = malloc(sizeof(Node));
node1->data = 3;
Node* node2 = malloc(sizeof(Node));
node2->data = 1;
Node* node3 = malloc(sizeof(Node));
node3->data = 6;
Node* node4 = malloc(sizeof(Node));
node4->data = 7;
Node* node5 = malloc(sizeof(Node));
node5->data = 9;

Five nodes are dynamically allocated using malloc().
Each node stores a different integer value.

Linking the nodes

node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node5;

This forms a linked list:
3 -> 1 -> 6 -> 7 -> 9 -> null

5. Printing the List Before Deletion

printf("Before deletion:\n");
traverseAndPrint(node1);

Output:

Before deletion:
3 -> 1 -> 6 -> 7 -> 9 -> null

6. Deleting a Specific Node (node4, which has value 7)

node1 = deleteSpecificNode(node1, node4);

This removes the node with value 7 from the list.
The new linked list:
3 -> 1 -> 6 -> 9 -> null

7. Printing the List After Deletion

printf("\nAfter deletion:\n");
traverseAndPrint(node1);

Output:

After deletion:
3 -> 1 -> 6 -> 9 -> null

8. Freeing Remaining Nodes

free(node1);
free(node2);
free(node3);
free(node5);

Since node4 was already freed inside deleteSpecificNode(), we only free the remaining nodes.

3. Insert a Node in a Linked List

To insert a node into a linked list, you typically need to consider a few scenarios:

Insertion at the Beginning: Inserting a node at the beginning of the linked list.
Insertion at the End: Inserting a node at the end of the linked list.
Insertion at a Specific Position: Inserting a node at a specific position within the linked list.

Here’s how you can implement these insertion operations in C:

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

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

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

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

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

    if (currentNode != NULL) {
        newNode->next = currentNode->next;
        currentNode->next = newNode;
    }
    return head;
}

int main() {
    Node* node1 = malloc(sizeof(Node));
    node1->data = 4;
    
    Node* node2 = malloc(sizeof(Node));
    node2->data = 9;
    
    Node* node3 = malloc(sizeof(Node));
    node3->data = 5;
    
    Node* node4 = malloc(sizeof(Node));
    node4->data = 8;

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;

    printf("Original list:\n");
    traverseAndPrint(node1);

    // Insert a new node with value 97 at position 2
    Node* newNode = malloc(sizeof(Node));
    newNode->data = 70;
    node1 = insertNodeAtPosition(node1, newNode, 2);

    printf("\nAfter insertion:\n");
    traverseAndPrint(node1);

    free(node1);
    free(node2);
    free(node3);
    free(node4);
    free(newNode);

    return 0;
}

Output:

Original list:
4 -> 9 -> 5 -> 8 -> null

After insertion:
4 -> 70 -> 9 -> 5 -> 8 -> null

Code Explanation

1. Include Header Files

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

stdio.h: Provides input/output functions like printf.
stdlib.h: Provides memory allocation functions like malloc and free.

2. Define the Node Structure

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

A Node structure is defined with two members:
- data: Stores the integer value of the node.
- next: A pointer to the next node in the list.
typedef is used to create an alias Node for struct Node.

3. Function: traverseAndPrint

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

Purpose: Traverses the linked list and prints its elements.
Steps:
1. Start from the head node.
2. Use a while loop to traverse the list until currentNode becomes NULL.
3. Print the data of each node.
4. Print null at the end to indicate the end of the list.

4. Function: insertNodeAtPosition

Node* insertNodeAtPosition(Node* head, Node* newNode, int position) {
    if (position == 1) {
        newNode->next = head;
        return newNode;
    }
 
    Node* currentNode = head;
    for (int i = 1; i < position - 1 && currentNode != NULL; i++) {
        currentNode = currentNode->next;
    }
 
    if (currentNode != NULL) {
        newNode->next = currentNode->next;
        currentNode->next = newNode;
    }
    return head;
}

Purpose: Inserts a new node at a specified position in the linked list.
Parameters:
- head: The starting node of the list.
- newNode: The new node to be inserted.
- position: The position where the new node should be inserted.
Steps:
1. If position == 1, insert the new node at the beginning:
  - Set newNode->next to head.
  - Return newNode as the new head.
2. Otherwise, traverse the list to the node just before the desired position.
3. Insert the new node:
  - Set newNode->next to currentNode->next.
  - Set currentNode->next to newNode.
4. Return the original head.

5. Main Function

int main() {
    Node* node1 = malloc(sizeof(Node));
    node1->data = 4;
     
    Node* node2 = malloc(sizeof(Node));
    node2->data = 9;
     
    Node* node3 = malloc(sizeof(Node));
    node3->data = 5;
     
    Node* node4 = malloc(sizeof(Node));
    node4->data = 8;
 
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
 
    printf("Original list:\n");
    traverseAndPrint(node1);
 
    // Insert a new node with value 70 at position 2
    Node* newNode = malloc(sizeof(Node));
    newNode->data = 70;
    node1 = insertNodeAtPosition(node1, newNode, 2);
 
    printf("\nAfter insertion:\n");
    traverseAndPrint(node1);
 
    free(node1);
    free(node2);
    free(node3);
    free(node4);
    free(newNode);
 
    return 0;
}

Steps:
1. Create Nodes:
  - Allocate memory for 4 nodes (node1, node2, node3, node4).
  - Assign values to their data fields (4, 9, 5, 8).
2. Link Nodes:
  - Set node1->next to node2.
  - Set node2->next to node3.
  - Set node3->next to node4.
3. Print Original List:
  - Call traverseAndPrint to display the original list.
4. Insert New Node:
  - Allocate memory for a new node (newNode).
  - Assign 70 to its data field.
  - Call insertNodeAtPosition to insert newNode at position 2.
5. Print Updated List:
  - Call traverseAndPrint to display the list after insertion.
6. Free Memory:
  - Deallocate memory for all nodes to prevent memory leaks.
7. Return:
  - End the program by returning 0.

4.Sorting

Sorting a linked list involves arranging the elements of the list in a specific order, such as ascending or descending order. One common sorting algorithm used for linked lists is Merge Sort, which is efficient for linked lists due to its divide-and-conquer approach.

Here’s how you can implement Merge Sort for sorting a singly linked list in C:

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

// Define a structure for a node
struct Node {
    int data;
    struct Node* next;
};

// Function to merge two sorted linked lists
struct Node* merge(struct Node* left, struct Node* right) {
    // Base cases
    if (left == NULL) return right;
    if (right == NULL) return left;

    struct Node* result = NULL;

    // Pick either left or right and recur
    if (left->data <= right->data) {
        result = left;
        result->next = merge(left->next, right);
    } else {
        result = right;
        result->next = merge(left, right->next);
    }

    return result;
}

// Function to perform Merge Sort on linked list
void mergeSort(struct Node** head_ref) {
    struct Node* head = *head_ref;
    struct Node* left;
    struct Node* right;

    // Base case: If the list is empty or has only one node
    if (head == NULL || head->next == NULL) {
        return;
    }

    // Split the list into two halves
    struct Node* slow = head;
    struct Node* fast = head->next;

    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }

    left = head;
    right = slow->next;
    slow->next = NULL;

    // Recursively sort the two halves
    mergeSort(&left);
    mergeSort(&right);

    // Merge the sorted halves
    *head_ref = merge(left, right);
}

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

    // Assign data to the new node
    new_node->data = new_data;

    // Set the next of the new node to the current head
    new_node->next = *head_ref;

    // Move the head to point to the new node
    *head_ref = new_node;
}

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

// Main function
int main() {
    // Start with an empty linked list
    struct Node* head = NULL;

    // Insert some elements into the linked list
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 6);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 9);
    insertAtBeginning(&head, 1);

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

    // Perform Merge Sort
    mergeSort(&head);

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

    return 0;
}

Output:

Original linked list: 1 9 2 6 3 
Sorted linked list: 1 2 3 6 9

Code Explanation

1. Function: merge

struct Node* merge(struct Node* left, struct Node* right) {
    // Base cases
    if (left == NULL) return right;
    if (right == NULL) return left;
 
    struct Node* result = NULL;
 
    // Pick either left or right and recur
    if (left->data <= right->data) {
        result = left;
        result->next = merge(left->next, right);
    } else {
        result = right;
        result->next = merge(left, right->next);
    }
 
    return result;
}

Purpose: Merges two sorted linked lists into a single sorted linked list.
Parameters:
- left: The head of the first sorted linked list.
- right: The head of the second sorted linked list.
Steps:
1. Base Cases:
  - If left is NULL, return right.
  - If right is NULL, return left.
2. Compare Nodes:
  - If left->data is smaller, set result to left and recursively merge left->next with right.
  - Otherwise, set result to right and recursively merge left with right->next.
3. Return Result:
  - Return the merged list.

2. Function: mergeSort

void mergeSort(struct Node** head_ref) {
    struct Node* head = *head_ref;
    struct Node* left;
    struct Node* right;
 
    // Base case: If the list is empty or has only one node
    if (head == NULL || head->next == NULL) {
        return;
    }
 
    // Split the list into two halves
    struct Node* slow = head;
    struct Node* fast = head->next;
 
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
 
    left = head;
    right = slow->next;
    slow->next = NULL;
 
    // Recursively sort the two halves
    mergeSort(&left);
    mergeSort(&right);
 
    // Merge the sorted halves
    *head_ref = merge(left, right);
}

Purpose: Sorts a linked list using the Merge Sort algorithm.
Parameters:
- head_ref: A pointer to the head of the linked list.
Steps:
1. Base Case:
  - If the list is empty or has only one node, return.
2. Split the List:
  - Use the slow and fast pointer technique to find the middle of the list.
  - Split the list into two halves: left and right.
3. Recursively Sort:
  - Call mergeSort on the left half.
  - Call mergeSort on the right half.
4. Merge the Sorted Halves:
  - Call merge to merge the two sorted halves.
  - Update head_ref to point to the merged list.

3. Function: insertAtBeginning

void insertAtBeginning(struct Node** head_ref, int new_data) {
    // Allocate memory for a new node
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
 
    // Assign data to the new node
    new_node->data = new_data;
 
    // Set the next of the new node to the current head
    new_node->next = *head_ref;
 
    // Move the head to point to the new node
    *head_ref = new_node;
}

Purpose: Inserts a new node at the beginning of the linked list.
Parameters:
- head_ref: A pointer to the head of the linked list.
- new_data: The data to be inserted.
Steps:
1. Allocate memory for a new node.
2. Assign new_data to the data field of the new node.
3. Set the next of the new node to the current head.
4. Update head_ref to point to the new node.

4. Function: printList

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

Purpose: Prints the elements of the linked list.
Steps:
1. Traverse the list starting from node.
2. Print the data of each node.
3. Print a newline at the end.

5. Main Function

int main() {
    // Start with an empty linked list
    struct Node* head = NULL;
 
    // Insert some elements into the linked list
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 6);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 9);
    insertAtBeginning(&head, 1);
 
    // Print the original linked list
    printf("Original linked list: ");
    printList(head);
 
    // Perform Merge Sort
    mergeSort(&head);
 
    // Print the sorted linked list
    printf("Sorted linked list: ");
    printList(head);
 
    return 0;
}

Steps:
1. Start with an empty linked list.
2. Insert elements (3, 6, 2, 9, 1) at the beginning of the list.
3. Print the original list.
4. Perform Merge Sort on the list.
5. Print the sorted list.

Linked Lists Operations

Operations

1. Traversal of a linked list

Code Explanation

2. Delete a Node in a Linked List

Code Explanation

3. Insert a Node in a Linked List

Code Explanation

4.Sorting

Code Explanation

Leave a Reply Cancel reply

Pointers

Functions

EXAMPLES

Quick Links

Courses

CONTACT