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.

Continue Learning with Java Guides

Want to take your programming skills to the next level? Explore my practical Udemy courses on Java, Spring Boot, Microservices, Full-Stack Development, Docker, and Generative AI. You can also follow my structured learning roadmaps to become a professional developer.

Explore My Udemy Courses View Developer Roadmaps

By Ramesh Fadatare - Udemy Instructor Partner