Welcome to our lesson focusing on Linked List Operations in Go. 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 capability distinguishes linked lists from arrays, making them indispensable tools in a programmer's toolkit.

A linked list is a linear data structure where each element is a separate object known as a ListNode. In Go, a ListNode is defined using a struct. The struct contains two fields: a value holding the data, and next, which is a pointer to the next ListNode in the linked list. The first element in the list is called the head. Here is how you can define a ListNode struct in Go:

Go
Copy to clipboard
1package main
2
3import "fmt"
4
5type ListNode struct {
6    value int       // Holds the value or data of the node
7    next  *ListNode // Points to the next node in the linked list; default is nil
8}

The algorithm to iterate over a Linked List in Go 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 nil.
3. Process Node: Perform operations on the current node (e.g., print value).
4. Advance Pointer: Move the pointer to the next node.

Here is the Go code to print out the value of each node:

Go
Copy to clipboard
1func main() {
2    head := &ListNode{1, 
3        &ListNode{2, 
4            &ListNode{3,
5                &ListNode{4,
6                    &ListNode{5, nil}}}}}
7                    
8    current := head
9    for current != nil {
10        fmt.Print(current.value, " ")
11        current = current.next
12    }
13    // Prints: 1 2 3 4 5
14}

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 nextNode.
   • Set prev to nil (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 nil.

3. Reverse the Pointer:

   • Inside the loop:
     • Store the next node in nextNode to keep track of the remaining list: nextNode = 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 = nextNode.

5. Update Head:

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

Here's how you can implement this algorithm in Go. Note that this code uses $O(1)$ additional memory, as the algorithm uses three pointers (prev, current, and nextNode), 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:

Go
Copy to clipboard
1package main
2
3import "fmt"
4
5func reverseList(head *ListNode) *ListNode {
6    var prev *ListNode
7    current := head
8    for current != nil {
9        nextNode := current.next
10        current.next = prev
11        prev = current
12        current = nextNode
13    }
14    return prev
15}
16
17// Test
18func main() {
19    head := &ListNode{1, &ListNode{2, &ListNode{3, &ListNode{4, &ListNode{5, nil}}}}}
20    reversedHead := reverseList(head)
21    
22    for reversedHead != nil {
23        fmt.Print(reversedHead.value, " ")
24        reversedHead = reversedHead.next // Output: 5 4 3 2 1
25    }
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!