-
Notifications
You must be signed in to change notification settings - Fork 17.9k
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
Labels
Comments
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. |
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) |
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. |
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. |
This issue was closed.
Sign up for free
to subscribe to this conversation on GitHub.
Already have an account?
Sign in.
by Fersca:
Attachments:
The text was updated successfully, but these errors were encountered: