How to Implement a Linked List in C++

Linked lists are a fundamental data structure in computer science, providing a way to organize and store data efficiently. Unlike arrays, linked lists are dynamic, allowing for flexible memory allocation and easy insertion and deletion of elements. In this article, we will explore how to implement a linked list in C++, highlighting definitions, use cases, and providing actionable insights through clear code examples.

What is a Linked List?

A linked list is a linear data structure where elements, known as nodes, are stored in separate locations in memory. Each node contains two components:

• Data: The value stored in the node.
• Pointer: A reference (or link) to the next node in the sequence.

Types of Linked Lists

There are several types of linked lists:

1. Singly Linked List: Each node points to the next node, allowing traversal in one direction.
2. Doubly Linked List: Nodes contain two pointers, one pointing to the next node and another pointing to the previous node, enabling bidirectional traversal.
3. Circular Linked List: The last node points back to the first node, creating a circular structure.

Use Cases of Linked Lists

Linked lists are widely used in various applications, including:

• Dynamic Memory Allocation: Unlike arrays, linked lists can grow and shrink in size, making them suitable for applications where the size of data is unpredictable.
• Implementing Data Structures: They are often used to create more complex data structures like stacks, queues, and hash tables.
• Real-Time Applications: Their dynamic nature allows for efficient data management in situations where performance is critical.

Implementing a Singly Linked List in C++

Let’s dive into the implementation of a singly linked list in C++. We will cover the following key operations:

• Insertion
• Deletion
• Traversal

Step 1: Define the Node Structure

First, we need to define a structure for our node.

struct Node {
    int data;       // Data part
    Node* next;     // Pointer to the next node

    Node(int val) : data(val), next(nullptr) {} // Constructor
};

Step 2: Create the Linked List Class

Next, we will create a class to manage our linked list.

class LinkedList {
private:
    Node* head; // Pointer to the head of the list

public:
    LinkedList() : head(nullptr) {} // Constructor

    void insert(int val);
    void remove(int val);
    void display();
    ~LinkedList(); // Destructor
};

Step 3: Implement Insertion

The insert function adds a new node to the end of the list.

void LinkedList::insert(int val) {
    Node* newNode = new Node(val);
    if (!head) {
        head = newNode; // If the list is empty
        return;
    }
    Node* temp = head;
    while (temp->next) {
        temp = temp->next; // Traverse to the end
    }
    temp->next = newNode; // Link the new node
}

Step 4: Implement Deletion

The remove function deletes a node with a specific value.

void LinkedList::remove(int val) {
    if (!head) return; // If the list is empty

    if (head->data == val) { // If the node to delete is the head
        Node* temp = head;
        head = head->next; // Update head to the next node
        delete temp;       // Free memory
        return;
    }

    Node* current = head;
    Node* previous = nullptr;

    while (current && current->data != val) {
        previous = current;
        current = current->next; // Traverse the list
    }

    if (current) {
        previous->next = current->next; // Bypass the node to delete
        delete current;                  // Free memory
    }
}

Step 5: Implement Traversal

The display function prints all elements in the linked list.

void LinkedList::display() {
    Node* temp = head;
    while (temp) {
        std::cout << temp->data << " -> ";
        temp = temp->next;
    }
    std::cout << "nullptr" << std::endl; // End of list
}

Step 6: Destructor

To avoid memory leaks, implement a destructor to free all nodes.

LinkedList::~LinkedList() {
    Node* current = head;
    Node* nextNode;
    while (current) {
        nextNode = current->next;
        delete current;
        current = nextNode; // Move to the next node
    }
}

Example Usage

Here’s how you can utilize the LinkedList class in your main program:

int main() {
    LinkedList list;

    list.insert(10);
    list.insert(20);
    list.insert(30);

    std::cout << "Linked List: ";
    list.display(); // Output: 10 -> 20 -> 30 -> nullptr

    list.remove(20);
    std::cout << "After Deletion: ";
    list.display(); // Output: 10 -> 30 -> nullptr

    return 0;
}

Conclusion

Implementing a linked list in C++ is a valuable skill that enhances your understanding of dynamic data structures. By mastering linked lists, you can optimize your coding practices, improve memory management, and efficiently solve problems that require flexible data storage.

As you continue to explore C++, consider experimenting with different types of linked lists, such as doubly or circular linked lists, to further expand your programming toolkit. Happy coding!