Golang Pointer Reverse Linked List Confusion

Question

I'm new to Golang and am a bit confused as to how pointers work here and I'm using a reverse linked list question as an example.

func reverseList(head *ListNode) *ListNode {
  var prev *ListNode = nil
  for {
    if head == nil {
      break
    }
    temp := head
    head = head.Next
    temp.Next = prev
    prev = temp
  }
    return prev
}

In this case, temp and head is pointing to the same memory location. But if I were to put the line temp.Next = prev before head = head.Next, the head.Next will point to nil.

What is happening under the hood when we say temp.Next = prev. Are we saying that the structure temp is pointing at is now changed and thus if I were to put that line above head = head.Next then head is now pointing to this changed structure as well?

I thought in order to change the actual value of head.Next, we would have to dereference it?

I'm a little bit confused as to why this wouldn't work instead

func reverseList(head *ListNode) *ListNode {
  var prev *ListNode = nil
  for {
    if head == nil {
      break
    }
    temp := head   
    temp.Next = prev
    prev = temp
    head = head.Next <--- CHANGED ORDERING HERE
  }
    return prev
}

Unlike C, Go automatically dereferences pointers to structs. So that you can get to a struct member with p.Next if p is a pointer or if p is a struct variable. — Zan Lynx
– Zan Lynx, Commented Apr 26, 2018 at 22:27
I had no idea that was the case, I just never really questioned changing structs fields until now! — Somnium
– Somnium, Commented Apr 26, 2018 at 22:34

robbrit · Accepted Answer · 2018-04-27 17:04:48Z

1

It wouldn't work because you're invalidating head on the first iteration. Here's the flow:

temp := head   
// Since temp is a pointer, any modifications made to it will also
// impact head. So when you set temp.Next here, you're also setting
// head.Next. Since prev is always nil on the first iteration, you've
// set head.Next = nil.
temp.Next = prev
prev = temp
// This will set head to nil, always.
head = head.Next

In the correct version, updating head = head.Next before any writes happen to it means you've moved on to the next element already and so it is safe to overwrite the value.

Effectively what the second version does is snip off all elements of the list except the first one. If you didn't make a reference to the second element before calling this function, then they are now off in limbo and will get garbage-collected.

Updates based on comments:
When you do something like temp := head, you are saying "create a pointer called temp and point it to the same thing that head points to." If you then modify the thing that temp is pointing to (like for example, doing temp.Next = prev) you will also see the changes when reading the data that head points to since it is still pointing at the same place.

When you then do head = head.Next you are saying "update head to point to wherever head.Next is pointing." This updates head itself instead of the data that it is pointing to, so you won't see any changes related to temp.

Here is a good resource to learn more about pointers: https://dave.cheney.net/2017/04/26/understand-go-pointers-in-less-than-800-words-or-your-money-back

edited Apr 27, 2018 at 17:04

answered Apr 26, 2018 at 22:26

robbrit

18k4 gold badges51 silver badges68 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Somnium Over a year ago

When I set head = head.Next it should also set temp to be equal to head.Next right? But why is it that when I set temp.prev = prev afterwards it no longer affects head?

Somnium Over a year ago

is it because head = head.Next assigns it to another pointer rather then altering it? So head and temp are no longer related?

robbrit Over a year ago

I added some details about how pointers work, let me know if that helps at all. But to the second comment, yes, setting head = head.Next makes head point to different data than temp, so modifying the two are now independent.

Collectives™ on Stack Overflow

Golang Pointer Reverse Linked List Confusion

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related