Introduction to Linked List Data Structure with Practical Examples

When our program needs to smoothly handle dynamic operations like adding, updating, and removing data, linked lists come in handy. Linked lists provide a flexible way to manage information, making it easier to insert, update, or delete data elements in our program.

Linked List

A linked list is like a chain of information in a program. Each piece of data is kept in a node, and each node points to the next one in the sequence with a pointer variable. This arrangement allows for flexible data management, simplifying tasks like adding, removing, or updating information. The nodes can be manipulated easily, providing flexibility in dynamic operations.
To understand Linked List in depth, a solid understanding of pointers is essential, and we have already covered this topic in our tutorial Pointer in C Programming .

Structure of a Linked List


Linked List

The basic building block of a linked list is the node. A node is a structure that encapsulates two essential components: data and a link to the next node.
To understand the structure of a Linked List, understanding of Structure is required, and we have already covered this topic in our tutorial Structure in C Programming .

Components of a Linked List

  • Data: This field holds the actual information the node carries. It could be an integer, a character, or any other data type depending on the requirements.
  • Next Link: The next link field is a pointer that points to the next node in the sequence. This linking mechanism is what transforms a collection of nodes into a coherent linked list.
  • Head: The head of the linked list is the first node. It serves as the starting point, and its pointer points to the first element in the sequence.
  • Tail: The tail is the last node in the linked list. Its next pointer is set to NULL, indicating the end of the list. The tail is crucial for efficient operations like appending new nodes.

Node Representation in C/C++

Each node in a linked list is represented by a structure. This structure includes a data member to store the node’s information and a pointer member next, which points to the subsequent node in the linked list.

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

Insert a Node in a Linked Lists

Insertion in linked lists can occur at different positions: at the beginning, in the middle, or at the end of the list. Each type of insertion requires specific handling to maintain the integrity of the linked list.

Insertion at the Beginning:

  1. Allocate memory for the new node.
  2. Set the data of the new node.
  3. Update the new node’s next pointer to point to the current head. Update the head to the new node
// Create a new node
struct Node* newNode = malloc(sizeof(struct Node));
newNode->data = newData;
// Update pointers
newNode->next = head;
head = newNode;

Insertion in the Middle:

  1. Locate the node after which the new node will be inserted.
  2. Allocate memory for the new node. 3 Set the data of the new node.
  3. Update the new node’s next pointer to the next node. Update the previous node’s next pointer to the new node.
// Create a new node
struct Node* newNode = malloc(sizeof(struct Node));
newNode->data = newData;
// Update pointers
newNode->next = temp->next;
temp->next = newNode;

Insertion at the End:

  1. Traverse the list to find the last node.
  2. Allocate memory for the new node. Set the data of the new node.
  3. Set the new node’s next pointer to NULL to mark the end of the list.
  4. Update the last node’s next pointer to the new node. If there is no last node update head with new node.
// Create a new node
struct Node* newNode = malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = NULL;
// Update pointers
if (head == NULL) {
    head = newNode;
} else {
    struct Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

Linked List Traversal

Traversing a linked list involves navigating through each node in the sequence, exploring the data they contain. This fundamental operation allows us to inspect, manipulate, or perform various tasks on the elements within the linked list. To traverse a Linked List :

  1. Start by creating a pointer that will move through the linked list and set the pointer to the beginning of the list (head node).
  2. Use a loop to move through each node in the linked list. Continue iterating until you reach the end of the list (when the pointer points to NULL).
  3. At each node, access the data stored within. Perform operations or simply observe the information based on your requirements.
  4. Move the pointer to the next node in the sequence.
  5. Exit the loop when the pointer reaches the end of the list (points to NULL).
struct Node* current = head;
while (current != NULL) {
        // Access data at the current node
        printf("%d -> ", current->data);
        // Move to the next node
        current = current->next;
}

Delete a Node from a Linked Lists

Like insertion, Linked Lists allow us to delete a node from different positions: at the beginning, in the middle, or at the end of the list.

Delete from the Beginning:

  1. Update the head pointer to point to the next node.
  2. Free the memory of the deleted node.
 struct Node* temp = *head;
 head = head->next;
 free(temp);

Delete from the Middle:

  1. Traverse to the node to be deleted.
  2. Update the previous node’s next pointer to bypass the node to be deleted.
  3. Free the memory of the deleted node.
previous->next = current->next;
free(current);

Delete from the End:

  1. Traverse to the last node.
  2. Update the second-to-last node’s next pointer to NULL.
  3. Free the memory of the deleted node.
struct Node* current = *head;
    struct Node* previous = NULL;

    while (current->next != NULL) {
        previous = current;
        current = current->next;
    }

    if (previous != NULL) {
        previous->next = NULL;
        free(current);
    } else {
        free(*head);
        *head = NULL;
    }

Linked List Real-Life Example

To understand Linked List better, lets create a to-do list with insertion, traversal, and deletion operations for linked list representing our to-do items.

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

// Node structure for the linked list
struct Task {
    int taskID;
    char description[100];
    struct Task* next;
};

// Function to add a new task to the to-do list
struct Task* insertTask(struct Task* head, int id, const char* desc) {
    // Allocate memory for the new task
    struct Task* newTask = (struct Task*)malloc(sizeof(struct Task));

    // Set the task details
    newTask->taskID = id;
    strncpy(newTask->description, desc, sizeof(newTask->description));
    newTask->next = NULL;

    // If the list is empty, make the new task the head
    if (head == NULL) {
        head = newTask;
    } else {
        // Otherwise, add the new task to the end of the list
        struct Task* current = head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newTask;
    }

    return head;
}

// Function to traverse and display the to-do list
void traverseToDoList(struct Task* head) {
    if (head == NULL) {
        printf("To-Do List is empty.\n");
        return;
    }

    // Initialize a pointer to the head of the list
    struct Task* current = head;

    // Iterate through the tasks
    while (current != NULL) {
        // Display task details
        printf("Task %d: %s\n", current->taskID, current->description);

        // Move to the next task
        current = current->next;
    }
}

// Function to remove a task from the to-do list
struct Task* deleteTask(struct Task* head, int id) {
    // If the list is empty, nothing to delete
    if (head == NULL) {
        printf("To-Do List is empty. Cannot delete.\n");
        return head;
    }

    // If the task to be deleted is the head
    if (head->taskID == id) {
        struct Task* newHead = head->next;
        free(head);
        return newHead;
    }

    // Search for the task to be deleted
    struct Task* current = head;
    struct Task* previous = NULL;

    while (current != NULL && current->taskID != id) {
        previous = current;
        current = current->next;
    }

    // If the task is not found
    if (current == NULL) {
        printf("Task %d not found. Cannot delete.\n", id);
        return head;
    }

    // Remove the task from the list
    previous->next = current->next;
    free(current);

    return head;
}

int main() {
    // Initialize an empty to-do list
    struct Task* toDoList = NULL;

    // Insert tasks
    toDoList = insertTask(toDoList, 1, "Complete assignment");
    toDoList = insertTask(toDoList, 2, "Buy groceries");
    toDoList = insertTask(toDoList, 3, "Attend meeting");

    // Display the to-do list
    printf("Initial To-Do List:\n");
    traverseToDoList(toDoList);

    // Delete a task
    toDoList = deleteTask(toDoList, 2);

    // Display the updated to-do list
    printf("\nUpdated To-Do List after deletion:\n");
    traverseToDoList(toDoList);

    return 0;
}

Run C Programming Online Compiler

To make your learning more effective, exercise the coding examples in the text editor below.

Run C programming online

Tags

Data Structure, A Data Structure, Data Structure and, Data Str, Algorithm and Data Structure, Database Structure and Algorithm, Linked List, Priority Queuing, Struct in C, Structure in C Programming, C++ Linked Lists, CPP Linked List, Lists in C++, Python 3 Data Structures, Linked List in C Programming, Linked List in C, Data Structure C++, Data Structures and C++, Data Structure of C++, C++ and Data Structures, CPP Data Structure, C++ with Data Structures, Data Structure CPP, Stack Data Structure, Queue in Data Structure

Next
Introduction to Queue Data Structure with Practical Examples