Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

container/list: Back() method doesn't work in linked list #5731

Closed
gopherbot opened this issue Jun 19, 2013 · 4 comments
Closed

container/list: Back() method doesn't work in linked list #5731

gopherbot opened this issue Jun 19, 2013 · 4 comments

Comments

@gopherbot
Copy link

by Fersca:

What steps will reproduce the problem?

When you create a list with the src/pkg/container/list/list.go and you start adding
elements to the list, when you ask for the last element you will get a nil

http://play.golang.org/p/bbGiL2-_ok

What is the expected output?

back:  &{0xc0100420c0 0xc0100420f0 <nil> <nil>} Value:  1

What do you see instead?

back:  &{0xc0100420c0 0xc0100420f0 <nil> <nil>} Value:  <nil>

Which compiler are you using (5g, 6g, 8g, gccgo)?

I'm compiling with "go run .... "

Which operating system are you using?
Linux Ubuntu 13.04 

Which version are you using?  (run 'go version')
go1.1 linux/amd64

Please provide any additional information below.

I don't understand why it doesn't work, the back() method is very simple.

In previous versions I could get the last element of the list, now you are implementing
a link as a ring, so the examples of how to iterate the link doesn't work any more
because the next() method is not going to give you a nil

for e := l.Front(); e != nil; e = e.Next() {
    // do something with e.Value
}

Attachments:

  1. prubaList.go (459 bytes)
@adg
Copy link
Contributor

adg commented Jun 19, 2013

Comment 1:

You shouldn't be using the list like that. The first thing you do is dereference the
*list.List returned from list.New:
  lista = *list.New()
When really, your lista type should be a *list.List and the line should be
  lista = list.New()
This program works: http://play.golang.org/p/hGVK4uONiy
However, it is puzzling that it's broken, even with your unconventional approach. The
methods PushFront, Front, and Back all have *List as the receiver, and so they should
each be called with a pointer to the same list.List value (lista).
For now, make the change I suggested. We'll try to figure out why this problem arose.

Status changed to Accepted.

@gopherbot
Copy link
Author

Comment 3 by martisch@uos.de:

i try to explain it:
see pointer addresses in http://play.golang.org/p/viY64hWXiT
func New() *List { return new(List).Init() }
will give back a pointer to List that is also the same address as the root element.
when dereferencing lista = *New() we throw away knowledge of that pointer in the main
function and create a local copy of the list struct. 
the local address of lista struct is taken for the l in func (l *List) PushFront then.
however when insertValue in PushFront we dont want that address of the local struct but
the pointer address to the List struct that was used in Init()!
so fix i guess is to make list.root a pointer to the root element where a local copy
does not hurt and do return l.insertValue(v, l.root) in PushFront and accordingly change
the other functions?
root is an internal data field so changing its type should not effect users of the list
package.
i would be happy to build a patch and test it if the above fix sounds right. 
(Do have to get accompanied to submitting patches to the golang project first)

@gopherbot
Copy link
Author

Comment 4 by martisch@uos.de:

on second thought that doesnt work for the len field ... 
Other thing is to initialize l.root.list in Init and always do l.root.list instead of l.

@griesemer
Copy link
Contributor

Comment 5:

Here is a simpler example that illustrates the problem in individual steps:
http://play.golang.org/p/7C5Tf3xTO3
The real issue is that the list is used incorrectly. You cannot create a list on the
heap (using New), and then make a memory copy of that data structure: The data structure
on the heap contains pointers into itself, and now you've got a copy that you are using
where those internal data structures still point to the one in the heap. When you now
use it, you are party updating your copy, and party updating the heap copy. It's a
wonder it doesn't crash...
The example above is simple enough such that it is possible to follow each individual
assignment in the List implementation and make a drawing with all the pointers involved.
When you call Back(), it returns l.root.prev where l.root is your copy of the original
data structure, and that prev happens to still point to the original prev which is the
internal sentinal (root) element and which has a nil value. Hence the result. It's a
good exercise to learn about pointers...
Here's a simple version of the code that works: http://play.golang.org/p/qgo7QoWUrR
Note that there's no need to heap-allocate the list, and it lazily initializes itself
too.

Status changed to WorkingAsIntended.

@golang golang locked and limited conversation to collaborators Jun 24, 2016
This issue was closed.
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

3 participants