Linked list traversal

Linked list traversal refers to the process of visiting and accessing each node in a linked list. There are two common ways to traverse a linked list: iteratively and recursively.

Iterative traversal involves using a loop to visit each node in the list in sequence. Here is an example implementation of an iterative traversal of a singly-linked list in C++:

template <typename T>
void printLinkedList(SinglyLinkedListNode<T>* head) {
    SinglyLinkedListNode<T>* current = head;
    while (current) {
        cout << current->value << " ";
        current = current->next;
    }
    cout << endl;
}

In this example, we define a function printLinkedList that takes a pointer to the head of the list as its argument. The function uses a while loop to traverse the list, starting at the head node and continuing until the end of the list is reached. For each node, the function prints the value of the node and updates the current pointer to point to the next node.

Recursive traversal involves visiting each node in the list by recursively traversing the sub-list starting at the next node. Here is an example implementation of a recursive traversal of a singly-linked list in C++:

template <typename T>
void printLinkedListRecursively(SinglyLinkedListNode<T>* head) {
    if (head) {
        cout << head->value << " ";
        printLinkedListRecursively(head->next);
    } else {
        cout << endl;
    }
}

In this example, we define a function printLinkedListRecursively that takes a pointer to the head of the list as its argument. The function first checks if the current node is not nullptr. If it is not nullptr, the function prints the value of the current node and calls itself recursively with the next node as its argument. If the current node is nullptr, the function prints a newline character to end the line of output.

Both iterative and recursive traversal are valid ways to visit each node in a linked list. Which method is used depends on the requirements of the program and the preferences of the programmer.