Linked List Operations in C++

Welcome to our lesson focusing on Linked List Operations in C++. Singly-Linked Lists (or just Linked Lists) are among the most fundamental data structures used in computer science. They provide an efficient way to store and access data that is not necessarily contiguous in memory. This ability separates linked lists from arrays, making them an indispensable tool in a programmer's toolkit.

A linked list is a linear data structure where each element is a separate object known as a ListNode. The ListNode class contains 2 fields, a value holding the data, and next which is a pointer to the next ListNode in the linked list. The ListNode constructor takes in a value and pointer to another ListNode. The default values are 0 and nullptr, respectively. The first element in the list is called the head, and the last element is called the tail, which points to nullptr. Let's take a look at the ListNode class:

#include <iostream>

class ListNode {
public:
    int value;      // Holds the value or data of the node
    ListNode* next; // Points to the next node in the linked list; default is nullptr

    // Constructor
    ListNode(int val = 0, ListNode* nxt = nullptr) : value(val), next(nxt) {}
};

The algorithm to iterate over a Linked List is:

1. Initialize Pointer: Start with a pointer at the head of the list.
2. Traversal Loop: Use a loop to iterate through the nodes while the current node is not nullptr.
3. Process Node: Perform operations on the current node (e.g., print value).
4. Advance Pointer: Move the pointer to the next node.

The code to print out the value of each node is:

// Initialization of linked list
int main() {
    ListNode* head = new ListNode(1, 
                            new ListNode(2, 
                                new ListNode(3,
                                    new ListNode(4,
                                        new ListNode(5)))));
    
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->value << " ";
        current = current->next;
    }
    // Prints: 1 2 3 4 5
}