Linked List Implementation in C++

1. Introduction

A Linked List is a linear data structure where elements are stored in nodes. Each node contains two fields: one for storing the data and the other for storing the reference to the next node in the sequence. In this blog post, we will walk through a simple implementation of a singly linked list using C++.

2. Implementation Steps

1. Declare a Node class to represent individual elements in the list.

2. Declare a LinkedList class that will encapsulate the list behavior.

3. Define methods for adding an item to the list (append), removing an item from the list (remove), displaying the list (display), and other utility functions.

4. Showcase the usage of the LinkedList through a demonstration.

3. Implementation in C++ Programming

#include<iostream>
class Node {
public:
    int data;          // Holds the data
    Node* next;        // Holds the reference to the next node
    Node(int value) {
        data = value;
        next = nullptr;
    }
};

class LinkedList {
private:
    Node* head;
public:
    LinkedList() {
        head = nullptr;
    }
    
    void append(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
    
    void display() {
        Node* temp = head;
        while (temp != nullptr) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "nullptr" << std::endl;
    }
    
    void remove(int value) {
        if (head == nullptr) return;
        if (head->data == value) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }
        Node* prev = nullptr;
        Node* curr = head;
        while (curr != nullptr && curr->data != value) {
            prev = curr;
            curr = curr->next;
        }
        if (curr != nullptr) {
            prev->next = curr->next;
            delete curr;
        }
    }
};


// client code to test Linked List Implementation in C++
int main() {
    LinkedList ll;
    ll.append(10);
    ll.append(20);
    ll.append(30);
    std::cout << "Linked List: ";
    ll.display();
    ll.remove(20);
    std::cout << "After removing 20: ";
    ll.display();
    return 0;
}

Output:

Linked List: 10 -> 20 -> 30 -> nullptr
After removing 20: 10 -> 30 -> nullptr

Explanation:

1. The Node class represents individual elements of the linked list. It contains the data and a pointer to the next node.

2. LinkedList class encapsulates the behavior of the list.

3. append(int value): This method adds a new node with the provided value to the end of the list.

4. display(): This traverses the list and prints each node's data.

5. remove(int value): This searches for a node with the given value and removes it from the list. It handles three cases: when the list is empty, when the head node is the target, and when the target node is in the middle or at the end of the list.

6. main(): Demonstrates the usage of the linked list by adding nodes and then removing a node.