Today's lesson will build upon our foundational understanding of linked lists by diving into practical implementation exercises using Go. These problems will sharpen your coding skills and prepare you for scenarios you might encounter in technical interviews.

Picture a scenario in which you have a sequence of events stored in a linked list. Your task is to look back in time — essentially, to reverse the chronology of these events. In technical terms, this means traversing a singly linked list in reverse order while keeping its structure intact. This skill is critical, whether for reversing transaction logs or simply navigating through a playlist from end to start.

Consider a browser's back-button functionality, where the most recently visited pages must be revisited in reverse order. This operation mirrors our task of reverse traversal in a linked list, capturing the essence of a real-world application. It’s crucial to differentiate between reverse traversal and reversing the linked list itself. For this problem, we essentially want to print out the elements in reverse order, keeping the structure intact.

Once approach to this problem can involve using a slice in Go. We navigate the linked list, storing the node values within the slice. Once the traversal is complete, we can extract the values in reverse by iterating over the slice backward.

Think of it like stacking books: each book (node value) goes sequentially into a stack, and then we iterate from the last added book to the first, "popping" them off one by one.

Go
Copy to clipboard
1type ListNode struct {
2    Value int
3    Next  *ListNode
4}
5
6func ReversePrintLinkedList(head *ListNode) {
7    // Use a slice to simulate stack behavior
8    var stack []int
9
10    // Traverse the linked list and append values to the slice
11    for currentNode := head; currentNode != nil; currentNode = currentNode.Next {
12        stack = append(stack, currentNode.Value)
13    }
14
15    // Iterate over the slice backward to simulate popping from a stack
16    for i := len(stack) - 1; i >= 0; i-- {
17        fmt.Println(stack[i])
18    }
19}
20
21func main() {
22    // Sample linked list: 1 -> 2 -> 3 -> nil
23    head := &ListNode{1, &ListNode{2, &ListNode{3, nil}}}
24    ReversePrintLinkedList(head)
25}

In this code, we utilize a slice called stack to store integers. As we traverse the linked list, each node's value is appended to stack. After collecting all values, we employ a reverse iteration to simulate the Last-In, First-Out (LIFO) order provided by stack operations. The solution has a time complexity of $O(n)$.

Next, we face a seemingly simple task: determining the size of a linked list. Imagine it as a conga line at a party. You'd like to know how many people are in the line without disturbing the dance. Start at the beginning and count each person until you reach the end.

In scenarios such as buffering data streams or executing batch operations, we often need to know the size of a list of tasks to allocate resources efficiently. This real-world implication highlights the utility of accurately determining the length of a linked list.

Unlike arrays or slices, where the length is readily available, linked lists require traversal to calculate their length. This is because linked lists are dynamically allocated structures without a centralized index or size property.

To calculate the length efficiently, we'll employ a classic traversal technique. It's a counting exercise: start at the first node (like the first person in the conga line) and increment a counter as we follow the links until we reach the end. The counter then reflects the conga line's length.

Go
Copy to clipboard
1func GetLength(head *ListNode) int {
2    // Initialize a counter for the length
3    length := 0
4
5    // Iterate through the list, incrementing the length counter
6    for currentNode := head; currentNode != nil; currentNode = currentNode.Next {
7        length++
8    }
9
10    // Return the final count
11    return length
12}
13
14func main() {
15    // Sample linked list: 1 -> 2 -> 3 -> nil
16    head := &ListNode{1, &ListNode{2, &ListNode{3, nil}}}
17    fmt.Println("Length of linked list:", GetLength(head))
18}

In this code, we initialize an integer length to zero, which serves as our counter. We then loop through each node of the linked list, incrementing length by one on each node visit. When the end of the list is reached, we return the total count. The solution has a time complexity of $O(n)$.

Today, we practiced critical operations on linked lists using Go, namely reversing a list's traversal and calculating its length. Both solutions involved traversing the linked list but with different goals in mind. We efficiently solved these problems using slices and straightforward iteration techniques in Go. We will transition to a series of exercises designed to reinforce your understanding of linked lists and prepare you for tackling similar problems in real-world scenarios or technical challenges with Go.