Single linked List Using Pointers In C++

Introduction to Single Linked Lists Using Pointers in C++:

A linked list is a linear data structure where each element, called a node, consists of two parts: data and a reference (or pointer) to the next node in the sequence. In a single linked list, each node contains a data field and a pointer that points to the next node in the sequence. The last node points to a special value, often nullptr, to indicate the end of the list.

Linked lists offer several advantages over arrays, including dynamic memory allocation, efficient insertion and deletion operations, and flexibility in size. However, they also have some disadvantages, such as inefficient access to arbitrary elements and extra memory overhead for storing pointers.

Here’s a breakdown of the key components and operations associated with single linked lists:

1. Node Structure:
   • A node in a single linked list typically consists of two parts: the data field and the next pointer.
   • The data field stores the actual value or information associated with the node.
   • The next pointer is a reference to the next node in the sequence. In C++, this pointer is usually of type Node* or struct Node*, where Node is the structure representing a node.
2. Traversal:
   • Traversing a linked list involves iterating through each node starting from the head (the first node) until reaching the end (where the next pointer is nullptr).
   • Traversal is essential for accessing, modifying, or performing operations on elements within the list.
3. Insertion:
   • Inserting an element into a linked list involves creating a new node, setting its data field, and updating pointers to maintain the list’s integrity.
   • Insertion can occur at the beginning, end, or middle of the list, depending on the specific requirement.
4. Deletion:
   • Deleting an element from a linked list involves finding the node to be removed, adjusting pointers to bypass the node, and deallocating its memory to prevent memory leaks.
   • Deletion can also occur at the beginning, end, or middle of the list.
5. Search:
   • Searching for an element in a linked list requires traversing the list and comparing the target value with the data field of each node until a match is found or the end of the list is reached.

Now, let’s see a C++ program that implements a single linked list and provides a line-by-line explanation:

#include <iostream>

// Define a Node structure
struct Node {
    int data;       // Data stored in the node
    Node* next;     // Pointer to the next node
};

int main() {
    // Initialize an empty linked list (head pointer is nullptr)
    Node* head = nullptr;

    // Insert nodes at the beginning of the list
    for (int i = 5; i >= 1; --i) {
        // Create a new node
        Node* newNode = new Node;
        newNode->data = i;
        newNode->next = head;

        // Update head pointer to point to the new node
        head = newNode;
    }

    // Traverse the linked list and print its elements
    Node* current = head;
    std::cout << "Linked List: ";
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;

    // Deallocate memory by deleting all nodes
    while (head != nullptr) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

Line-by-Line Explanation:

1. #include <iostream>: This line includes the necessary header file for input/output operations.
2. struct Node { ... };: This defines a structure named Node representing a node in the linked list. It contains two fields: data to store the value of the node and next to store a pointer to the next node.
3. Node* head = nullptr;: This initializes the head pointer of the linked list to nullptr, indicating an empty list.
4. for (int i = 5; i >= 1; --i) { ... }: This loop inserts nodes at the beginning of the linked list. It iterates from 5 down to 1, creating a new node for each iteration and inserting it at the beginning of the list.
5. Node* newNode = new Node; ...: Inside the loop, a new node is created, its data field is set to the current value of i, and its next pointer is set to the current head of the list.
6. head = newNode;: The head pointer is updated to point to the newly created node, effectively making it the new head of the list.
7. Node* current = head; ...: This initializes a pointer current to traverse the list, starting from the head.
8. while (current != nullptr) { ... }: This loop traverses the linked list and prints the data of each node until current becomes nullptr, indicating the end of the list.
9. std::cout << current->data << " ";: Inside the loop, the data of the current node is printed.
10. current = current->next;: The current pointer is updated to point to the next node in the list.
11. while (head != nullptr) { ... }: This loop deallocates memory by deleting all nodes in the list. It iterates until the head pointer becomes nullptr, indicating that all nodes have been deleted.
12. Node* temp = head;: Inside the loop, a temporary pointer temp is used to store the current head node.
13. head = head->next;: The head pointer is updated to point to the next node in the list.
14. delete temp;: The memory allocated for the current node (pointed to by temp) is deallocated.

This program demonstrates the creation, traversal, and deletion of a single linked list in C++, illustrating the fundamental operations associated with linked lists using Pointers in C++