Home

Blogs

Forums

News

Portfolios

Projects

Tutorials

18 users logged in

New? Learn about game development.

Before posting, review our community guidelines.

Support GameDev.net with a monthly GDNet+ subscription!

Chat in the GameDev.net Discord!

Back to For Beginners

Is this a faster way to go through a linked list?

Jeff D · 2002-02-01T09:46:26

Lets say you have a struct like this: struct Node { ItemClass Item; Node* next; }; Now lets say you have 100000 Items. I know 100000 items sounds like a lot im using this as an example. Now you have to go through it like this: while(LinkedItems->next) { CurrentItem = CurrentItem->next } Now to my knowledge that could get slow if you are going through the list a lot. But would this make it faster? add a long ID. Now lets say I wanted to goto item 4500. Would this be faster?? long ID; int IDRemains int i; ID = 4500; IDRemains = ID % 5; ID = ID / 5; for(i = 0; i < ID; i++) { CurrentItem = CurrentItem->next->next->next->next->next; } if(IDRemains != 0) { For(i = 0; i < IDRemains; i++) { CurrentItem = CurrentItem->next; } } Kinda after posting and coding I believe my second way is slower because it uses more code. But GameDev has helped me a lot so far so maybe Im right the first time. Thx. Jeff D Suffered seven plagues, but refused to let the slaves go free. ~ Ross Atherton Edited by - Jeff D on January 31, 2002 8:36:00 AM Edited by - Jeff D on January 31, 2002 8:37:19 AM

For Beginners

Started by Jeff D January 31, 2002 07:34 AM

16 comments, last by Jeff D 22 years, 7 months ago

Jeff D

Author

122

January 31, 2002 04:18 PM

Hash tables never used em. Ill search them up right now on Google. Perhaps you are right.

Thx

Jeff D

Suffered seven plagues, but refused to let the slaves go free. ~ Ross Atherton

Suffered seven plagues, but refused to let the slaves go free. ~ Ross Atherton

Michalson

1,657

January 31, 2002 04:21 PM

If need to go through the list fast but it must still be a linked list (so it can grow to any size<total memory) while not try creating a class around it that allows you to either iterate through it or to access it by ID. When access it by ID you can use a fixed array of "Last Search" pointers. Each stores a pointer to an item along with that items ID. Whenever you want to access an item by ID just check to see which pointer is closest (include the head/first item pointer and the tail pointer if the list is reverse transversable) and go from there. Once the item is found same its pointer and ID to the "Last Search" table, replacing the item to do the search or better (but harder) by timestamping each item in the "Last search" array whenever it is used so you can delete the most useless one. One of the Java linked-list classes does something like this though it only keeps one "last search" pointer.

Floppy

122

January 31, 2002 04:26 PM

quote: Original post by Fruny
What if, say CurrentItem->next->next == NULL ?
CurrentItem = CurrentItem->next->next->next->next->next will send you on a one-way trip to Segfaultland.

Haha, Segfaultland. Very original

.

I would suggest using a hash table.

Jeff D

Author

122

January 31, 2002 05:14 PM

I looked up things about hash tables they seem quite advanced for me. heheh Im still quite new to C++. Well I was sitting down and thought. Im gonna make the weapons, armor, items, spells. I know the amount so why not just create them with arrays. Is this like a bad habit to get into with programming

Hash tables seemed confusing, maybe I''m just tired right now.

Jeff D

Suffered seven plagues, but refused to let the slaves go free. ~ Ross Atherton

Suffered seven plagues, but refused to let the slaves go free. ~ Ross Atherton

Symphonic

313

February 01, 2002 01:07 AM

It''s not a bad idea, but take the time to look up the basics on making a template class. Then use the code I gave you, because it will save you some trouble.

If you REALLY don''t know up from down yet, I can give you a complete Array template class that I have written.

George D. Filiotis
Are you in support of the ban of Dihydrogen Monoxide? You should be!

Geordi
George D. Filiotis

Jeff D

Author

122

February 01, 2002 09:13 AM

Hey I take all the code I can get if its to big to put on here send to domon_m@hotmail.com. Thx

About template classes I got Teach yourself c++ in 24 hours ill take a look at it.

Jeff D

Suffered seven plagues, but refused to let the slaves go free. ~ Ross Atherton

Suffered seven plagues, but refused to let the slaves go free. ~ Ross Atherton

CaptainJester

523

February 01, 2002 09:14 AM

You could also use the builting vector class. Of course there is no hashing, but it can be treated just like an array. That way you have 2 options: you could make a vector for each category, ie weapons, armour, etc... or you could make a root object like CharacterStuff, derive the character items and spells from that and save them all in one vector.

---
Make it work.
Make it fast.

"Commmmpuuuuterrrr.." --Scotty Star Trek IV:The Voyage Home

"None of us learn in a vacuum; we all stand on the shoulders of giants such as Wirth and Knuth and thousands of others. Lend your shoulders to building the future!" - Michael Abrash[JavaGaming.org][The Java Tutorial][Slick][LWJGL][LWJGL Tutorials for NeHe][LWJGL Wiki][jMonkey Engine]

Symphonic

313

February 01, 2002 09:46 AM

That''s also a good idea, when I can I''ll send you my Array class (i''m still completing some finishing touches) and then you can pick from your options

George D. Filiotis
Are you in support of the ban of Dihydrogen Monoxide? You should be!

Geordi
George D. Filiotis

Is this a faster way to go through a linked list?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Is this a faster way to go through a linked list?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines