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:

C++
Copy to clipboard
1#include <iostream>
2
3class ListNode {
4public:
5    int value;      // Holds the value or data of the node
6    ListNode* next; // Points to the next node in the linked list; default is nullptr
7
8    // Constructor
9    ListNode(int val = 0, ListNode* nxt = nullptr) : value(val), next(nxt) {}
10};

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:

C++
Copy to clipboard
1// Initialization of linked list
2int main() {
3    ListNode* head = new ListNode(1, 
4                            new ListNode(2, 
5                                new ListNode(3,
6                                    new ListNode(4,
7                                        new ListNode(5)))));
8    
9    ListNode* current = head;
10    while (current != nullptr) {
11        std::cout << current->value << " ";
12        current = current->next;
13    }
14    // Prints: 1 2 3 4 5
15}

One example of a problem to practice involves reversing a linked list, a common operation in interviews and industry. Reversing a linked list involves changing the direction of the next pointers of the nodes so that they point to the previous node instead of the next one. Here is a step-by-step explanation of the algorithm:

1. Initialize Pointers:

   • Start with three pointers: prev, current, and next_node.
   • Set prev to nullptr (indicating the new end of the list).
   • Set current to the head of the linked list (the starting node).

2. Traversal Loop:

   • Iterate through the list until current becomes nullptr.

3. Reverse the Pointer:

   • Inside the loop:
     • Store the next node in next_node to keep track of the remaining list: next_node = current->next.
     • Reverse the next pointer of the current node to point to prev: current->next = prev.

4. Advance Pointers:

   • Move the prev pointer to the current node: prev = current.
   • Move the current pointer to the next node: current = next_node.

5. Update Head:

   • After the loop completes, prev will be pointing to the new head of the reversed list.

Yes, that's a good description. Here's a slightly refined version with minor tweaks for readability:

Here is what the code might look like. Note that this code uses $O(1)$ of additional memory, as the algorithm utilizes three pointers (prev, current, and next_node), and the space used by these pointers does not increase with the size of the linked list. Thus, the memory consumption remains constant, making it highly efficient:

C++
Copy to clipboard
1#include <iostream>
2
3ListNode* reverseList(ListNode* head) {
4    ListNode* prev = nullptr;
5    ListNode* current = head;
6    while (current != nullptr) {
7        ListNode* next_node = current->next;
8        current->next = prev;
9        prev = current;
10        current = next_node;
11    }
12    return prev;
13}
14
15// Test
16int main() {
17    ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
18    ListNode* reversed_head = reverseList(head);
19    
20    while (reversed_head != nullptr) {
21        std::cout << reversed_head->value << " ";
22        reversed_head = reversed_head->next;  // Output: 5 4 3 2 1
23    }
24
25    return 0;
26}

Take time to analyze and understand the problem and the corresponding solution. This practice will facilitate a well-rounded understanding of linked list operations and their applications. By the end of the tutorial, you should feel more comfortable tackling linked list problems, allowing you to handle similar tasks in technical interviews. Let's get started with practical exercises!