Help with linked lists

The Partridge Family were neither partridges nor a family. Discuss.
Post Reply
User avatar
YoMomIsANiceLady
Posts: 33
Joined: February 2nd, 2017, 8:20 am

Help with linked lists

Post by YoMomIsANiceLady » February 23rd, 2017, 6:29 am

Hello guys, so I've been trying to convert my snake's game menu into a linked list to make it more flexible and easier to control in terms of adding / removing menu items. Linked lists have always been a slightly confusing subject for me so could you please check my code if it's written properly?

I have tested it with debugger and it seems to be linking fine. I just want to make sure I'm not unnecessarily allocating more memory than I should and that I'm releasing pointers properly. Basically how I wanted it to look is to have a cyclic infinite menu. So the last menu item points to the first one. I wasn't sure whether or not I did it correctly with the root node. SO

For my MenuItem class, I have 3 members:

Code: Select all

MenuItem* next;
MenuItem* previous;
std::string label;
This is a picture showing how I imagine the menu should look like: http://i.imgur.com/mEF6Ia5.jpg
The green arrow represents NEXT, the blue arrow represents PREVIOUS.

So the previous of root is always a nullptr.
The next of root always points to the first item in the menu.
The next of the last item in the menu always points to the first item in the menu

This is my code implementation: http://pastebin.com/3gvxzATU

I wasn't sure how to go about deleting the pointers. Do they not get deleted automatically by garbage collection? Do I have to do it manually? If I delete the first and current pointers at the end of the else statement, the code won't work (Throws bad alloc or something).

So is this correct or do I need to change something? Is there a better way of doing this?

EDIT:
And yes, adding a new item should add it as the first item, so to the very top of the menu.

EDIT 2:
I have updated the code. I was told, I don't need to make current and first on the heap. Also I didn't need current to traverse the menu at all! Here's the new code: http://pastebin.com/hPYtk5sL
"Life is like death, but completely different"
- Ivan Gašparovič

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Help with linked lists

Post by albinopapa » February 23rd, 2017, 8:08 am

The only thing I have to offer is if you are concerned with mem leaks, use unique_ptr instead of raw pointers.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
YoMomIsANiceLady
Posts: 33
Joined: February 2nd, 2017, 8:20 am

Re: Help with linked lists

Post by YoMomIsANiceLady » February 23rd, 2017, 9:23 am

Okay, I removed the root node that is sort of being useless in there and just pretending to be the appendix.

I replaced the root node with "top". So now anything that is on top of the menu is what root was before. I also added it to the cycle, so now it's just a pure infinite circle, no weird root nodes. This seems a lot simpler: http://pastebin.com/NwxHkwiw
"Life is like death, but completely different"
- Ivan Gašparovič

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Help with linked lists

Post by chili » February 25th, 2017, 5:22 am

The problem with linked lists is that they are: slow (because of memory allocation/caching issues) and they are very easy to fuck up if you try and roll your own. In most situations, a vector-type container will perform better. And when you actually have a use case that is better for linked list (more rare than you would think), std::list<> has got your back.

That said, if you're just making a list as an exercise for yourself, it's not a terrible idea. But I wouldn't do weird things like make the list circular in that case. Not until I've mastered the basic linked list structure ;)
Chili

User avatar
BurakCanik
Posts: 250
Joined: February 8th, 2014, 9:16 pm
Location: Istanbul, Turkey

Re: Help with linked lists

Post by BurakCanik » March 3rd, 2017, 3:54 pm

Adding to Chili's reply, a quote from "Game Programming Patterns" (great book by the way, shout out to AlbinoPapa for recommending it): "Life is too short to code linked lists from scratch."
If real is what you can feel, smell, taste and see, then 'real' is simply electrical signals interpreted by your brain" - Morpheus

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Help with linked lists

Post by albinopapa » March 3rd, 2017, 6:04 pm

:)
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

Post Reply