top of page

Write Code for a Linked List in C with Functionalities to Add, Delete, and Find Nodes

A linked list in C is a fundamental data structure used to organize a collection of elements. Unlike arrays, linked lists allow dynamic memory allocation and efficient insertion and deletion operations. In this article, we’ll focus on implementing a singly linked list in C and explore how to add, delete, and find nodes within it.


Importance of Linked List in C:

  • Dynamic Size: Linked list can grow or shrink dynamically as needed, making them suitable for scenarios where the size of the data structure is unknown in advance.

  • Efficient Insertions and Deletions: Adding or removing elements from a linked list in C is efficient because it involves adjusting pointers rather than shifting memory blocks.

  • Versatility: Linked list in C serve as building blocks for other data structures like stacks, queues, and graphs.

  • Memory Allocation: Linked list in C allows for non-contiguous memory allocation, overcoming the limitations of fixed-size arrays.



Linked List Node Structure

A linked list consists of nodes, where each node contains two fields:

  • Data: Holds the actual value.

  • Next: Points to the next node in the list.


Data Field (Value):

  • The data field (also known as the value or payload) holds the actual information associated with the node. It can be any type of data, such as an integer, string, or a custom-defined structure.

  • For example, in a list of integers, the data field would store the numeric value itself.


Next Field (Pointer):

  • The next field (often called the next pointer) is crucial for maintaining the linkage between nodes in the list.

  • It contains the memory address (or reference) of the next node in the sequence.

  • Essentially, it points to the following node, allowing us to traverse the list from one node to the next.

  • In the last node of the list, the next field typically points to a special value (often NULL or nullptr) to indicate the end of the list.


Let’s define the structure for our linked list node:

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

Basic Operations for Linked List in C


Insertion Operation

Linked list allow dynamic memory allocation and efficient insertion of elements. Key insertion scenarios:

  • Insertion at the Beginning: Create a new node and update the head pointer.

  • Insertion at the End: Traverse the list and append the new node.

Insertion in the beginning

When adding a new node at the beginning of the linked list, follow these steps:

  1. Create a new node (let’s call it newNode).

  2. Set the data field of newNode to the desired value.

  3. Update the next field of newNode to point to the current head of the list.

  4. Update the head pointer to point to newNode.


Here’s the C code snippet for inserting a node at the beginning:

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

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

// Global variable head
struct Node* head = NULL;

// Function to insert a node at the beginning of the linked list
void insertAtBeginning(int value) {
    // Allocate memory for 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 of new node
    newNode->data = value;
    newNode->next = head;

    // Update head to point to new node
    head = newNode;
}

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

// Main function
int main() {
    // Inserting elements at the beginning of the linked list
    insertAtBeginning(3);
    insertAtBeginning(5);
    insertAtBeginning(7);
    insertAtBeginning(10);

    // Printing the linked list
	printf("Each element is inserted at the beginning of the list\n");
    printf("Linked list: ");
    printLinkedList();

    return 0;
}
Inserting elements at the beginning of the linked list in c

Insert at the End

To insert a node at the end of the linked list, follow these steps:

  1. Create a new node (again, let’s call it newNode).

  2. Set the data field of newNode to the desired value.

  3. If the list is empty (i.e., head is NULL), make newNode the new head.

  4. Otherwise, traverse the list until you reach the last node (where next is NULL).

  5. Update the next field of the last node to point to newNode.


Here’s the C code snippet for inserting a node at the end:

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

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

// Global variable head
struct Node* head = NULL;

// Function to insert a node at the end of the linked list
void insertAtEnd(int value) {
    // Allocate memory for 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 of new node
    newNode->data = value;
    newNode->next = NULL;

    // If the list is empty, make the new node the head
    if (head == NULL) {
        head = newNode;
        return;
    }

    // Traverse to the end of the list
    struct Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    // Insert the new node at the end
    temp->next = newNode;
}

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

// Main function
int main() {
    // Inserting elements at the end of the linked list
    insertAtEnd(3);
    insertAtEnd(5);
    insertAtEnd(7);
    insertAtEnd(10);

    // Printing the linked list
    printf("Each element is inserted at the end of the list\n");
    printf("Linked list: ");
    printLinkedList();

    return 0;
}
inserting elements at the end of the linked list in c


Delete by Value

The deleteNode function removes the first occurrence of a given value from the linked list. Here’s how it works:

  1. Initialize two pointers: temp (to traverse the list) and prev (to keep track of the previous node).

  2. While temp is not NULL and the data in the current node (temp->data) is not equal to the target value:

  • Update prev to temp.

  • Move temp to the next node.

  1. If temp becomes NULL, the value was not found in the list. Print an appropriate message.

  2. Otherwise:

  • If prev is NULL, the target value is in the head node. Update head to point to the next node.

  • Otherwise, update prev->next to skip the node containing the target value.

  1. Free the memory occupied by the removed node.


Here’s the C code snippet for deleting a node by value:

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

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

// Global variable head
struct Node* head = NULL;

// Function to delete a node with given value from the linked list
void deleteNode(int value) {
    // Initialize pointers for traversal
    struct Node* temp = head;
    struct Node* prev = NULL;

    // Traverse the list to find the node to delete
    while (temp != NULL && temp->data != value) {
        prev = temp;
        temp = temp->next;
    }

    // If node with given value is not found
    if (temp == NULL) {
        printf("Value %d not found in the list.\n", value);
        return;
    }

    // If the node to be deleted is the head node
    if (prev == NULL) {
        head = temp->next;
    } else {
        // Update the previous node's next pointer to skip the node to be deleted
        prev->next = temp->next;
    }

    // Free the memory occupied by the node to be deleted
    free(temp);
}

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

// Main function
int main() {
    // Code for testing deleteNode function
    // Inserting elements into the linked list
    struct Node* node1 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* node3 = (struct Node*)malloc(sizeof(struct Node));
    
    node1->data = 3;
    node2->data = 5;
    node3->data = 7;
    
    head = node1;
    node1->next = node2;
    node2->next = node3;
    node3->next = NULL;

    // Deleting a node
    deleteNode(5);

    // Printing the linked list
    printf("Linked list after deletion: ");
    printLinkedList();

    return 0;
}
deleting element from linked list in c

Search

The search function checks whether a given value exists in the linked list. It returns 1 if the value is found and 0 otherwise:

  1. Initialize a pointer temp to traverse the list.

  2. While temp is not NULL:

  • If the data in the current node (temp->data) matches the target value, return 1.

  • Otherwise, move temp to the next node.

  1. If the loop completes without finding the value, return 0.


Here’s the C code snippet for searching a value in the list:

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

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

// Global variable head
struct Node* head = NULL;

// Function to search for a value in the linked list
int search(int value) {
    // Initialize pointer for traversal
    struct Node* temp = head;

    // Traverse the list to search for the value
    while (temp != NULL) {
        if (temp->data == value) {
            return 1; // Value found
        }
        temp = temp->next;
    }
    return 0; // Value not found
}

// Main function
int main() {
    // Code for testing search function
    // Inserting elements into the linked list
    struct Node* node1 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* node3 = (struct Node*)malloc(sizeof(struct Node));
    
    node1->data = 3;
    node2->data = 5;
    node3->data = 7;
    
    head = node1;
    node1->next = node2;
    node2->next = node3;
    node3->next = NULL;

    // Searching for values
    int value1 = 5;
    int value2 = 8;
    
    if (search(value1))
        printf("%d is found in the list.\n", value1);
    else
        printf("%d is not found in the list.\n", value1);
    
    if (search(value2))
        printf("%d is found in the list.\n", value2);
    else
        printf("%d is not found in the list.\n", value2);

    return 0;
}
search element from linked list in c

Practical Examples

Linked list is used for:

1. Implementing Stacks and Queues:

  • Stacks: A stack is a data structure that follows the Last-In-First-Out (LIFO) principle. Linked list can be used to implement stacks efficiently. The top of the stack corresponds to the head of the linked list.

  • Queues: A queue follows the First-In-First-Out (FIFO) principle. Linked list can serve as the underlying data structure for implementing queues.



2. Dynamic Memory Allocation:

  • Linked list allow dynamic memory allocation, which means you can create and remove nodes as needed during program execution.

  • When you allocate memory for a new node, it doesn’t have to be contiguous with other nodes, unlike arrays.

  • This flexibility is especially useful when dealing with variable-sized data or when memory requirements change dynamically.


3. Preparing for More Complex Data Structures:

  • Linked list serve as building blocks for more advanced data structures:

  • Graphs: Graphs can be represented using linked list (adjacency lists) to store connections between nodes (vertices).

  • Trees: Some tree structures (e.g., binary trees) can be implemented using linked list.

  • Hash Tables: Separate chaining in hash tables often uses linked list to handle collisions.


Conclusion

In this article, we explored the intricacies of linked list in C. These dynamic data structures play a pivotal role in programming, offering flexibility and efficient memory management. Linked list serve as building blocks for more complex data structures like graphs and trees.

Commentaires


bottom of page