Implementation of Singly Linked List in C++ Programming Language

A singly linked list is a fundamental data structure in computer science that consists of a sequence of elements, called nodes. Each node contains data and a pointer to the next node in the sequence. Unlike arrays, linked lists don’t store elements in contiguous memory locations, making them more flexible for dynamic data management.

Below is how a singly linked list looks like:

This article explores the structure and C++ implementation of singly linked lists, including key operations like insertion, deletion, searching, and traversal. It also covers time and space complexity analysis. We’ll start by declaring the base classes for the singly linked list, and then implement all the basic operations.

Prerequisites: Basics of Linked List Data Structure

Implementing the Singly Linked List Class

To implement a singly linked list in C++, we need to create two classes: SinglyLinkedNode and SinglyLinkedList.

`SinglyLinkedNode` Class

The SinglyLinkedNode class represents the structure of all individual nodes present in the Singly Linked list:

class SinglyLinkedNode {
public:
    int data;
    SinglyLinkedNode* next;

    SinglyLinkedNode(int value) : data(value), next(nullptr) {}
};

The purpose of each field in the structure is as follows:

data: Stores the actual value of the node.
next: A pointer to the next node in the list. Its value is initially set to nullptr, indicating that there are no nodes after this node.

`SinglyLinkedList` Class

The SinglyLinkedList class manages the entire list:

class SinglyLinkedList {
private:
    SinglyLinkedNode* head;
    int size;

public:
    SinglyLinkedList() : head(nullptr), size(0) {}
    ~SinglyLinkedList();

    // Member functions will be added here
};

The purpose of each field in the structure is as follows:

head: Points to the first node in the list. Its value is initially set to nullptr, indicating an empty list.
size: Keeps track of the number of nodes in the list.

Note that we’ve added a destructor to handle memory deallocation when the list is destroyed.

This base implementation of linked list class provides a foundation for adding more complex operations like insertion, deletion, and traversal, which we’ll explore in the following sections.

Implementing Basic Operations for Singly Linked List

`insertAtBeginning`

This operation adds a new node at the start of the list and makes the newly added node the new head of the singly linked list.

Algorithm:

Create a new node with the given data.
Set the new node’s next pointer to the current head.
Update the head to point to the new node.
Increment the size of the list.

Time Complexity: O(1) (constant time, as it only involves updating a few pointers)
Space Complexity: O(1) (only creates one new node, regardless of list size)

void insertAtBeginning(int data) {
    SinglyLinkedNode* newNode = new SinglyLinkedNode(data);
    newNode->next = head;
    head = newNode;
    size++;
}

`insertAtEnd`

This operation appends a new node to the end of the singly linked list.

Algorithm:

Create a new node with the given data.
If the list is empty, make the new node the head.
Otherwise, traverse to the last node and set its next pointer to the new node.
Increment the size of the list.

Time Complexity: O(n), where n is the number of nodes in the list (need to traverse the entire list to reach the end)
Space Complexity: O(1) (only creates one new node, regardless of list size)

void insertAtEnd(int data) {
    SinglyLinkedNode* newNode = new SinglyLinkedNode(data);
    if (!head) {
        head = newNode;
    } else {
        SinglyLinkedNode* current = head;
        while (current->next) {
            current = current->next;
        }
        current->next = newNode;
    }
    size++;
}

If you need to optimize the time complexity of this operation, maintaining a tail pointer is an option. By keeping track of the last node in the list and caching it, you can reduce the time complexity from O(n) to O(1). This approach allows for constant-time insertion at the end of the list, regardless of its size, making it particularly efficient for large lists or frequent end insertions.

`deleteNode`

This operation removes a specific node from the singly linked list.

Algorithm:

Check if the list is empty. If so, return without doing anything.
Check if the head node contains the data to be deleted:
- If yes, update the head to point to the next node.
- Decrement the size of the list.
- Delete the old head node.
- Return from the function.
Traverse the list to find the node to delete and its previous node:
- Start from the head and move to the next node.
- Continue until we find a node with the matching data or reach the end of the list.
If a node with matching data is found:
- Update the previous node’s next pointer to skip the node to be deleted.
- Delete the node.
- Decrement the size of the list.

Time Complexity: O(n), where n is the number of nodes in the list (may need to traverse the entire list to find the node)
Space Complexity: O(1) (only uses a few temporary variables, regardless of list size)

void deleteNode(int data) {
    if (!head) {
        return;
    }

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

    SinglyLinkedNode* current = head;
    while (current->next && current->next->data != data) {
        current = current->next;
    }

    if (current->next) {
        SinglyLinkedNode* temp = current->next;
        current->next = current->next->next;
        delete temp;
        size--;
    }
}

Note that it is possible to have multiple nodes with the same value. In such cases, the above implementation deletes only the first node with the matching value. You can also implement a similar method that takes in the actual linked list node as an input and deletes it from the list.

`searchNode`

This operation searches for a node with a given value.

Algorithm:

Traverse the list from the head.
Compare each node’s data with the search value.
Return the node if found, or nullptr if not found.

Time Complexity: O(n), where n is the number of nodes in the list (may need to traverse the entire list to find the node)
Space Complexity: O(1) (only uses a single temporary variable, regardless of list size)

SinglyLinkedNode* searchNode(int data) {
    SinglyLinkedNode* current = head;
    while (current) {
        if (current->data == data) {
            return current;
        }
        current = current->next;
    }
    return nullptr;
}

Note that the above implementation returns only the first matching node. You can extend the implementation to return all the nodes matching the given data if needed.

`getSize`

This operation returns the total number of nodes in the list.

Algorithm:

Return the size attribute of the list.

Time Complexity: O(1) (constant time, as it simply returns a pre-computed value)
Space Complexity: O(1) (no additional space used)

int getSize() const {
    return size;
}

`printList`

This operation displays all elements in the list sequentially.

Algorithm:

Traverse the list from the head.
Print each node’s data.

Time Complexity: O(n), where n is the number of nodes in the list (needs to visit every node once)
Space Complexity: O(1) (only uses a single temporary variable, regardless of list size)

void printList() const {
    SinglyLinkedNode* current = head;
    while (current) {
        std::cout << current->data << " -> ";
        current = current->next;
    }
    std::cout << "nullptr" << std::endl;
}

Destructor

To properly deallocate memory when the list is destroyed, we need to implement a destructor:

~SinglyLinkedList() {
    while (head) {
        SinglyLinkedNode* temp = head;
        head = head->next;
        delete temp;
    }
}

This destructor traverses the list and deletes each node, ensuring that all dynamically allocated memory is freed when the list object is destroyed. If this step is skipped, the memory allocated for each node in the linked list won’t be freed and memory leaks happen.

Overall Implementation with Example Usage

Here’s a complete implementation of the singly linked list class along with example usage:


#include <iostream>

class SinglyLinkedNode {
public:
    int data;
    SinglyLinkedNode* next;

    SinglyLinkedNode(int value) : data(value), next(nullptr) {}
};

class SinglyLinkedList {
private:
    SinglyLinkedNode* head;
    int size;

public:
    SinglyLinkedList() : head(nullptr), size(0) {}
    ~SinglyLinkedList() {
        while (head) {
            SinglyLinkedNode* temp = head;
            head = head->next;
            delete temp;
        }
    }

    void insertAtBeginning(int data) {
        SinglyLinkedNode* newNode = new SinglyLinkedNode(data);
        newNode->next = head;
        head = newNode;
        size++;
    }

    void insertAtEnd(int data) {
        SinglyLinkedNode* newNode = new SinglyLinkedNode(data);
        if (!head) {
            head = newNode;
        } else {
            SinglyLinkedNode* current = head;
            while (current->next) {
                current = current->next;
            }
            current->next = newNode;
        }
        size++;
    }

    void deleteNode(int data) {
        if (!head) {
            return;
        }

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

        SinglyLinkedNode* current = head;
        while (current->next && current->next->data != data) {
            current = current->next;
        }

        if (current->next) {
            SinglyLinkedNode* temp = current->next;
            current->next = current->next->next;
            delete temp;
            size--;
        }
    }

    SinglyLinkedNode* searchNode(int data) {
        SinglyLinkedNode* current = head;
        while (current) {
            if (current->data == data) {
                return current;
            }
            current = current->next;
        }
        return nullptr;
    }

    int getSize() const {
        return size;
    }

    void printList() const {
        SinglyLinkedNode* current = head;
        while (current) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }
};

// Example usage
int main() {
    // Create a new singly linked list
    SinglyLinkedList myList;

    // Insert elements at the beginning
    myList.insertAtBeginning(3);
    myList.insertAtBeginning(2);
    myList.insertAtBeginning(1);

    std::cout << "After inserting 1, 2, 3 at the beginning:" << std::endl;
    myList.printList();  // Output: 1 -> 2 -> 3 -> nullptr

    // Insert elements at the end
    myList.insertAtEnd(4);
    myList.insertAtEnd(5);

    std::cout << "After inserting 4 and 5 at the end:" << std::endl;
    myList.printList();  // Output: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr

    // Delete a node
    myList.deleteNode(3);

    std::cout << "After deleting node with value 3:" << std::endl;
    myList.printList();  // Output: 1 -> 2 -> 4 -> 5 -> nullptr

    // Search for a node
    SinglyLinkedNode* foundNode = myList.searchNode(4);
    std::cout << "Searched for 4, found: " << (foundNode ? std::to_string(foundNode->data) : "Not found") << std::endl;

    // Get the size of the list
    std::cout << "Size of the list: " << myList.getSize() << std::endl;

    return 0;
}

This implementation demonstrates the creation of a singly linked list and various operations such as insertion at the beginning and end, deletion, searching, and printing the list. The example usage shows how to create a list, add elements, delete a node, search for a value, and get the size of the list.

When you run this code, you’ll see the list’s state after each operation, allowing you to visualize how the singly linked list changes with different operations. The destructor ensures that all dynamically allocated memory is properly freed when the list object goes out of scope.

Implementation of Singly Linked List in C++ Programming Language

Implementing the Singly Linked List Class

SinglyLinkedNode Class

SinglyLinkedList Class

Implementing Basic Operations for Singly Linked List

insertAtBeginning

insertAtEnd

deleteNode

searchNode

getSize

printList

Destructor

Overall Implementation with Example Usage

`SinglyLinkedNode` Class

`SinglyLinkedList` Class

`insertAtBeginning`

`insertAtEnd`

`deleteNode`

`searchNode`

`getSize`

`printList`