链表实现的指针故障

Question

Trying to implement LinkedList with simple addToLast function (which adds the new node to the end of the linkedlist) instead of using the inbuilt list) Below is the code (removed print statements which I used for debugging):

package main

import "fmt"

var first *Link
var last Link

func main() {
    AddToLast(10)
    AddToLast(20)
}

func AddToLast(d int) {
    if first == nil {
        last = Link{d, new(Link)}
        first = &last
    } else {
        last.next = &Link{d, new(Link)}
        last = *last.next
    }
}

type Link struct {
    data int
    next *Link
}

My understanding of the above code:

Inside AddToLast functions - After checking if 'first' is nil i.e. it doesn't have any element, 'last' is created with 10 as the data and new empty Link as the next. Now 'first' is assigned the same value as 'last' but using memory address(as reference - I'm not sure if my understanding is incorrect here)

Now when we try to insert 20 (the next new element) the else part in the 'AddToLast' is executed. 'last.next' is assigned a link with value as 20 and it's next as nil. Now 'last' is moved to 'last.next', to make sure 'last' always points to the last node.

However since I moved 'last' to 'last.next', 'last'('s) memory address changes which is obvious and this also causes first to point to the new last i.e. with value as 20.

In order to avoid this, I tried declaring 'first' as Link instead of *Link. However, doing this doesn't make first.next point to new node i.e. 20. I'm confused as to where I'm not thinking correct.

Answer 1

Don't mutate the element value in last, since that element is already created. Make a new last, and set the previous next pointer to point to it. Here is a modified version: http://play.golang.org/p/-X5RayC0gU

var first *Link
var last *Link

func AddToLast(d int) {
    next := &Link{d, nil}
    if first == nil {
        first = next
    } else {
        last.next = next
    }
    last = next
}

type Link struct {
    data int
    next *Link
}