C++ Program to Implement a Singly Linked List

1. Introduction

A singly linked list is a linear data structure where each element is a separate object, and each of these objects is termed a node. Each node contains a data part and a reference (or link) to the next node in the sequence. In this post, we'll implement a basic singly linked list in C++.

2. Program Overview

Our singly linked list implementation will provide the following operations:

1. insert: Adds a node at the end of the list.

2. display: Prints all the nodes in the list.

3. deleteNode: Deletes a node given its data value.

4. search: Checks if a data value exists in the list.

3. Code Program

#include <iostream>

// Define a Node for the linked list
class Node {
public:
    int data;       // Data contained in the node
    Node* next;     // Pointer to the next node

    // Constructor to initialize node data and next pointer
    Node(int val) : data(val), next(nullptr) {}
};

// Define a Singly Linked List
class SinglyLinkedList {
private:
    Node* head;     // Pointer to the start of the list

public:
    // Constructor to initialize an empty list with head as nullptr
    SinglyLinkedList() : head(nullptr) {}

    // Member functions of the linked list
    void insert(int val);        // Insert a node at the end of the list
    void display();              // Display the contents of the list
    void deleteNode(int val);    // Delete a node with the given value
    bool search(int val);        // Search for a value in the list
};

// Function to insert a node at the end of the list
void SinglyLinkedList::insert(int val) {
    Node* newNode = new Node(val);   // Create a new node
    if (!head) {
        head = newNode;              // If list is empty, make the new node the head
        return;
    }
    Node* temp = head;
    while (temp->next) {
        temp = temp->next;           // Traverse to the end of the list
    }
    temp->next = newNode;            // Insert the new node at the end
}

// Function to display the contents of the list
void SinglyLinkedList::display() {
    Node* temp = head;
    while (temp) {
        std::cout << temp->data << " -> ";
        temp = temp->next;           // Move to the next node
    }
    std::cout << "NULL" << std::endl; // Mark the end of the list
}

// Function to delete a node with a specific value
void SinglyLinkedList::deleteNode(int val) {
    if (!head) return;                // If list is empty, simply return
    if (head->data == val) {          // If head node is to be deleted
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    Node* prev = nullptr;
    Node* curr = head;
    // Traverse the list to find the node with the given value
    while (curr && curr->data != val) {
        prev = curr;
        curr = curr->next;
    }
    if (curr) {
        prev->next = curr->next;
        delete curr;                  // Delete the node if found
    }
}

// Function to search for a specific value in the list
bool SinglyLinkedList::search(int val) {
    Node* temp = head;
    while (temp) {
        if (temp->data == val) return true;  // Return true if value is found
        temp = temp->next;
    }
    return false;                          // Return false if value is not found
}

int main() {
    SinglyLinkedList list;                  // Create an empty list
    list.insert(10);                        // Insert values
    list.insert(20);
    list.insert(30);
    list.display();                         // Display the list
    list.deleteNode(20);                    // Delete node with value 20
    list.display();                         // Display the list after deletion
    // Check if value 20 is still in the list
    std::cout << (list.search(20) ? "20 is in the list" : "20 is not in the list") << std::endl;
    return 0;
}

The program is explained with proper comments on each line.

Output:

10 -> 20 -> 30 -> NULL
10 -> 30 -> NULL
20 is not in the list

4. Step By Step Explanation

The SinglyLinkedList class encapsulates all necessary functions for basic singly linked list operations. It internally maintains a head pointer pointing to the first node in the list.

1. The insert function creates a new node and adds it at the end of the list.

2. The display function iteratively traverses the list and prints each node's data.

3. The deleteNode function searches for a node by its data value and, if found, deletes it from the list.

4. The search function checks if a node with the given data value exists in the list.

In the main function, we demonstrate these methods by inserting three nodes, displaying the list, deleting a node, and then checking if a data value exists in the list.