C++ Program to Implement a Singly Linked List

A singly linked list is a fundamental data structure in computer science, where each element (node) contains a value and a pointer to the next node in the sequence. This structure is useful for various applications, including dynamic memory allocation, efficient insertion and deletion operations, and implementing other data structures like stacks and queues. In this article, we will explore the implementation of a singly linked list in C++, demonstrating various operations through multiple examples.

Table of Contents

Prerequisites

Before diving into the implementation, you should have:

Basic understanding of C++ programming.
Familiarity with pointers and dynamic memory allocation.
Knowledge of linked lists and their basic operations.

With these prerequisites, you will be able to grasp the concepts and code implementations discussed here.

1. Basic Singly Linked List Implementation

1.1 Node Structure and List Initialization

Let’s start by defining the structure of a node in the singly linked list and initializing the list.

C++

#include <iostream>

struct Node {
    int data;
    Node* next;

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

class SinglyLinkedList {
public:
    SinglyLinkedList() : head(nullptr) {}

    void insertAtEnd(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
        } else {
            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 << std::endl;
    }

private:
    Node* head;
};

int main() {
    SinglyLinkedList list;
    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    list.insertAtEnd(40);

    std::cout << "Singly Linked List: ";
    list.display();

    return 0;
}

1.2 Output Explanation

In this example, the singly linked list is structured as follows:

C++

10 -> 20 -> 30 -> 40

The output will display: 10 20 30 40

2. Advanced Singly Linked List Operations

2.1 Insertion at Beginning

Let’s add a method to insert a node at the beginning of the list.

C++

class SinglyLinkedList {
    // ... (previous code remains the same)

public:
    void insertAtBeginning(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
        } else {
            newNode->next = head;
            head = newNode;
        }
    }
};

int main() {
    SinglyLinkedList list;
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    list.insertAtBeginning(10);
    list.insertAtEnd(40);
    list.insertAtBeginning(5);

    std::cout << "Singly Linked List after insertions: ";
    list.display();

    return 0;
}

2.2 Output Explanation

In this example, the singly linked list after the insertions is structured as follows:

C++

5 -> 10 -> 20 -> 30 -> 40

The output will display: 5 10 20 30 40

3. Deletion in Singly Linked List

3.1 Deletion of a Specific Node

Next, we will implement a method to delete a specific node from the list.

C++

class SinglyLinkedList {
    // ... (previous code remains the same)

public:
    void deleteNode(int key) {
        if (head == nullptr) return;

        if (head->data == key) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }

        Node* current = head;
        Node* prev = nullptr;

        while (current != nullptr && current->data != key) {
            prev = current;
            current = current->next;
        }

        if (current == nullptr) return; // Node not found

        prev->next = current->next;
        delete current;
    }
};

int main() {
    SinglyLinkedList list;
    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    list.insertAtEnd(40);

    std::cout << "Singly Linked List: ";
    list.display();

    list.deleteNode(20);
    std::cout << "List after deleting 20: ";
    list.display();

    list.deleteNode(10);
    std::cout << "List after deleting 10: ";
    list.display();

    return 0;
}

3.2 Output Explanation

In this example, the singly linked list after the deletions is structured as follows:

After deleting 20:10 -> 30 -> 40 The output will display: 10 30 40
After deleting 10:30 -> 40 The output will display: 30 40

4. Reversal of Singly Linked List

4.1 Reversal Method

Let’s implement a method to reverse the singly linked list.

C++

class SinglyLinkedList {
    // ... (previous code remains the same)

public:
    void reverse() {
        Node* prev = nullptr;
        Node* current = head;
        Node* next = nullptr;

        while (current != nullptr) {
            next = current->next;
            current->next = prev;
            prev = current;
            current = next;
        }
        head = prev;
    }
};

int main() {
    SinglyLinkedList list;
    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    list.insertAtEnd(40);

    std::cout << "Singly Linked List: ";
    list.display();

    list.reverse();
    std::cout << "Reversed Singly Linked List: ";
    list.display();

    return 0;
}

4.2 Output Explanation

In this example, the singly linked list after reversal is structured as follows:

C++

40 -> 30 -> 20 -> 10

The output will display: 40 30 20 10

Conclusion

A C++ program to implement a singly linked list involves defining the node structure and implementing various operations such as insertion, deletion, traversal, and reversal. This article provided a detailed implementation of these operations along with multiple examples to illustrate their functionality.