Introduction to Linked List Data Structure with Practical Examples

• Linked List
  • Types of Linked List
• Structure of a Linked List
  • Components of a Linked List
  • Node Representation in C/C++
• Insert a Node in a Linked Lists
  • Insertion at the Beginning:
  • Insertion in the Middle:
  • Insertion at the End:
• Linked List Traversal
• Delete a Node from a Linked Lists
  • Delete from the Beginning:
  • Delete from the Middle:
  • Delete from the End:
• Linked List Real-Life Example
• Run C Programming Online Compiler
• Difference between Singly, Doubly and Circular linked list
• Tags

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 .

¶Types of Linked List

Linked lists come in several variations, each offering unique advantages and use cases. Here are the main types of linked lists:

1. Singly Linked List: In a singly linked list, each node contains a reference only to the next node in the sequence. It is the simplest form of a linked list. Traversal in a singly linked list starts from the head node and progresses through each subsequent node until the end of the list is reached. Insertions and deletions can be performed efficiently at the beginning or end of the list, but random access and deletion of specific nodes require traversing the list from the beginning.

2. Doubly Linked List: In a doubly linked list, each node contains references to both the next and the previous nodes in the sequence. This allows for traversal in both forward and backward directions. Insertions and deletions at any position in the list can be performed efficiently since each node maintains references to its adjacent nodes. However, doubly linked lists require more memory due to the additional reference in each node.

3. Circular Linked List: A circular linked list is a variation of a singly or doubly linked list where the last node’s reference points back to the first node, forming a circular structure. This means that there is no distinct “end” of the list; traversal can continue indefinitely by following the node references. Circular linked lists are useful in scenarios where continuous looping through the elements is required, such as in circular buffers or for implementing round-robin scheduling algorithms.

In the below lecture, we’ll discuss only the Singly Linked List. Let’s start -

¶Structure of a 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

¶Difference between Singly, Doubly and Circular linked list

¶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, doubly linked list, last element retrieval, insertion, remove first item, add node, delete node, find node, list methods, singly linked list, circular linked list, merge sorted linked list, reverse linked list, difference between array and linked list, data structure, stack, deletion, implementation, programming, visualization