Linked List Operations in Go

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:

package main

import "fmt"

type ListNode struct {
    value int       // Holds the value or data of the node
    next  *ListNode // Points to the next node in the linked list; default is nil
}

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:

func main() {
    head := &ListNode{1, 
        &ListNode{2, 
            &ListNode{3,
                &ListNode{4,
                    &ListNode{5, nil}}}}}
                    
    current := head
    for current != nil {
        fmt.Print(current.value, " ")
        current = current.next
    }
    // Prints: 1 2 3 4 5
}

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:

package main

import "fmt"

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    current := head
    for current != nil {
        nextNode := current.next
        current.next = prev
        prev = current
        current = nextNode
    }
    return prev
}

// Test
func main() {
    head := &ListNode{1, &ListNode{2, &ListNode{3, &ListNode{4, &ListNode{5, nil}}}}}
    reversedHead := reverseList(head)
    
    for reversedHead != nil {
        fmt.Print(reversedHead.value, " ")
        reversedHead = reversedHead.next // Output: 5 4 3 2 1
    }
}