What is wrong with my iterate function

Question

I am attempting to iterate over a simple linked list. This should be so simple, but it's not working. The iterate function contains the issue.

package main

import (
    "fmt"
    "time"
)

type Node struct {
    Next  *Node
    Value int
}

func main() {
    //Load up 100 *Node in a linked list (albeit a simple one)
    head := &Node{Value: 0}
    current := head
    for i := 1; i < 100; i++ {
        current.Next = &Node{Value: i}
        current = current.Next
        fmt.Printf("current %p %+v\n", current, current)
    }

    iterate(head)
}

//Iterate through the list starting at head. It never 
//advances past the first "Next", loops forever.
func iterate(head *Node) {
    for n := head.Next; n != nil; head = n {
        fmt.Printf("head %+v n %+v\n", head, n)
        time.Sleep(time.Second * 1)
    }
}

The output of iterate looks something like:

head &{Next:0x20818c230 Value:0} n &{Next:0x20818c280 Value:1}
head &{Next:0x20818c280 Value:1} n &{Next:0x20818c280 Value:1}
head &{Next:0x20818c280 Value:1} n &{Next:0x20818c280 Value:1}
head &{Next:0x20818c280 Value:1} n &{Next:0x20818c280 Value:1}
head &{Next:0x20818c280 Value:1} n &{Next:0x20818c280 Value:1}

For kicks I tried another version of the iterate loop that uses a function to fetch .Next. My thinking was that maybe head.Next was always pointing at my original head due to some sort of loop optimization. That theory seems incorrect.

func iterate(head *Node) {
    getNext := func (n *Node) *Node {
        return n.Next
    }

    for n := getNext(head); n != nil; head = n {
        fmt.Printf("head %+v n %+v\n", head, n)
        time.Sleep(time.Second * 1)
    }
}

Gosh, am I just not seeing it? I set head to n after the loop body executes which is equal to the next Node. Shouldn't the next head.Next return the subsequent Node until we get to a nil node and exit the loop?

--- Update ---

I've come up with the following modification to iterate which is so much cleaner and actually correct now:

func iterate(head *Node) {
    for ; head != nil; head = head.Next {
        fmt.Printf("head %+v head.Next %+v\n", head, head.Next)
    }
}

Your modification is certainly cleaner than mine ;) I just tried to modify as little as possible your initial version of the loop. — VonC

VonC VonC · Accepted Answer · 2015-02-27T07:07:39

Looking at the For statement spec:

The "init statement" part of your loop (n := head.Next) is evaluated only once.
The post statement keeps resetting head to the initial value of n (getNext(head)).

Hence the inifinite loop.

Putting n := getNext(head) within the loop should be better, as in this working example:

for n := head; n != nil; head = n {
    fmt.Printf("head %+v n %+v\n", head, n)
    time.Sleep(time.Second * 1)
    n = head.Next
}

What is wrong with my iterate function

2 Answers