Linked List: Single Linked List

Overview

Single linked lists are a versatile data structure commonly used in computer science and programming. In this article, we will explore different approaches to implement single linked lists in C++. Each method provides a unique perspective on how to manage linked data structures, giving you the flexibility to choose the one that best suits your needs. By the end, you will have a solid understanding of how to use and manipulate single linked lists in your C++ programs.

What is a Single Linked List?

A single linked list is a linear data structure consisting of a sequence of elements called nodes. Each node contains two parts: the data or value it holds and a reference (a pointer)  to the next node in the list. The last node typically points to a null reference, indicating the end of the list. This linked structure allows for efficient insertions and deletions.

Implementation of Single Linked Lists

Method 1: Using Structs

One of the most straightforward ways to create a single linked list in C++ is by using structs to define nodes and a class to manage the list.

#include <iostream>

// Define the Node structure
struct Node {
    int data;
    Node* next;
};

// Define the Linked List class
class LinkedList {
public:
    LinkedList() : head(nullptr) {}

    // Append a new element to the end of the list
    void append(int value) {
        Node* newNode = new Node{value, nullptr};
        if (!head) {
            head = newNode;
        } else {
            Node* current = head;
            while (current->next) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    // Display the elements in the list
    void display() {
        Node* current = head;
        while (current) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }

private:
    Node* head;
};

int main() {
    LinkedList myList;
    myList.append(1);
    myList.append(2);
    myList.append(3);
    myList.display();

    return 0;
}

Method 2: Using Custom Classes

Another way to implement a single linked list is by creating custom classes for nodes and the linked list. This approach provides more encapsulation and can be useful in complex scenarios.

#include <iostream>

// Define the Node class
class Node {
public:
    int data;
    Node* next;

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

// Define the Linked List class
class LinkedList {
public:
    LinkedList() : head(nullptr) {}

    // Append a new element to the end of the list
    void append(int value) {
        Node* newNode = new Node(value);
        if (!head) {
            head = newNode;
        } else {
            Node* current = head;
            while (current->next) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    // Display the elements in the list
    void display() {
        Node* current = head;
        while (current) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }

private:
    Node* head;
};

int main() {
    LinkedList myList;
    myList.append(1);
    myList.append(2);
    myList.append(3);
    myList.display();

    return 0;
}

Method 3: Using Templates

C++ templates provide a way to create a generic linked list that can store elements of any data type. This approach is highly flexible and can be adapted for various use cases.

#include <iostream>

// Define the Node template
template <typename T>
struct Node {
    T data;
    Node* next;

    Node(T value) : data(value), next(nullptr) {}
};

// Define the Linked List template
template <typename T>
class LinkedList {
public:
    LinkedList() : head(nullptr) {}

    // Append a new element to the end of the list
    void append(T value) {
        Node<T>* newNode = new Node<T>(value);
        if (!head) {
            head = newNode;
        } else {
            Node<T>* current = head;
            while (current->next) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    // Display the elements in the list
    void display() {
        Node<T>* current = head;
        while (current) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }

private:
    Node<T>* head;
};

int main() {
    LinkedList<int> intList;
    intList.append(1);
    intList.append(2);
    intList.append(3);
    intList.display();

    LinkedList<std::string> strList;
    strList.append("Hello");
    strList.append("World");
    strList.display();

    return 0;
}

Single Linked List Operations and Their Complexities

Single linked lists support various operations, and it's important to understand their time complexities.

Insertion (at the beginning):

• Operation: insertAtBeginning(value)
• Time Complexity: O(1)
• Explanation: Adding a node at the beginning involves changing a few pointers.

Insertion (at the end):

• Operation: append(value)
• Time Complexity: O(n)
• Explanation: To add an element at the end, you need to traverse the entire list to find the last node, making it a linear-time operation.

Deletion (from the beginning):

• Operation: deleteFromBeginning()
• Time Complexity: O(1)
• Explanation: Removing the first element requires updating the head pointer.

Deletion (from a specific position):

• Operation: deleteAtPosition(position)
• Time Complexity: O(n)
• Explanation: Deleting a node at a specific position involves traversing the list to find the previous node.

Traversal:

• Operation: display()
• Time Complexity: O(n)
• Explanation: To display all elements, you need to traverse the entire list.

Searching:

• Operation: search(value)
• Time Complexity: O(n)
• Explanation: In the worst case, you may have to search through the entire list to find a specific value.

Below is the code implementation that includes common operations:

#include <iostream>

// Define the Node structure
struct Node {
    int data;
    Node* next;
    Node(int value) : data(value), next(nullptr) {}
};

// Define the Linked List class
class LinkedList {
public:
    LinkedList() : head(nullptr) {}

    // Append a new element to the end of the list
    void append(int value) {
        Node* newNode = new Node(value);
        if (!head) {
            head = newNode;
        } else {
            Node* current = head;
            while (current->next) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    // Insert a new element at the beginning of the list
    void insertAtBeginning(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }

    // Delete the first element from the list
    void deleteFromBeginning() {
        if (head) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }

    // Display the elements in the list
    void display() {
        Node* current = head;
        while (current) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }

    // Search for a specific value in the list
    bool search(int value) {
        Node* current = head;
        while (current) {
            if (current->data == value) {
                return true;
            }
            current = current->next;
        }
        return false;
    }
};

int main() {
    LinkedList myList;
    myList.append(1);
    myList.append(2);
    myList.append(3);

    std::cout << "Original List: ";
    myList.display();

    myList.insertAtBeginning(0);
    std::cout << "After Insertion at Beginning: ";
    myList.display();

    myList.deleteFromBeginning();
    std::cout << "After Deletion from Beginning: ";
    myList.display();

    int searchValue = 2;
    if (myList.search(searchValue)) {
        std::cout << searchValue << " found in the list." << std::endl;
    } else {
        std::cout << searchValue << " not found in the list." << std::endl;
    }

    return 0;
}

• append: Adds an element at the end of the list.
• insertAtBeginning: Inserts an element at the beginning of the list.
• deleteFromBeginning: Removes the first element.
• display: Displays the elements in the list.
• search: Searches for a specific value in the list.

Difference between arrays and linked lists:

Memory Allocation:

• Arrays: Arrays are allocated in contiguous memory locations. The size of an array is fixed when it is declared.
• Linked Lists: Linked lists do not require contiguous memory. They are dynamically allocated as new elements are added, making them more flexible in terms of size.

Insertions and Deletions:

• Arrays: Insertions and deletions in an array can be slow because elements may need to be shifted to maintain the contiguous memory layout. This can result in a time complexity of O(n) in the worst case.
• Linked Lists: Linked lists excel at insertions and deletions, as they only require changing a few pointers. Insertions and deletions can be performed in O(1) time, assuming you have a reference to the element to be modified.

Access Time:

• Arrays: Accessing elements in an array is fast and has a constant time complexity of O(1), assuming you know the index.
• Linked Lists: Accessing elements in a linked list is slower because you must traverse the list from the beginning. The time complexity for access is O(n) in the worst case.

Dynamic Sizing:

• Arrays: Arrays have a fixed size, which makes dynamic resizing complex and potentially inefficient. You may need to allocate a new array, copy elements, and deallocate the old array.
• Linked Lists: Linked lists are dynamic in size and can easily accommodate the addition or removal of elements without resizing concerns.

Random Access:

• Arrays: Arrays support efficient random access to elements using indices.
• Linked Lists: Linked lists do not support efficient random access; you must traverse the list sequentially to access an element.