I decied to move to FB and i cant say i regret it!
I started to implement one of these for my inventory system in my little game and so far its working great!
My next question is what are some other logical uses for Linked lists? I think these are very sexy ways to dynamically update things.
Just a query is all
Personally I'm not all that happy about linked lists. To me it seems like an awful lot of allocate / deallocate to save a few bytes here and there. And I imagine a load of small elements must fragment memory a lot, slowing allocations (of which you need a lot with linked lists) down even more ...correct me if I'm wrong.
I prefer dynamic arrays implemented in the std::vecotr way, where you resize the array (double the size) every time you run out of elements. And if I need to sort it a lot, I create an additional array which has pointers to the array elements in the first array and sort that. That way one doesn't need to allocate a new chunk of memory each time you need a new element, and you don't have to deallocate it when you're done (hail freebasic). The downside is that you will most likely use more memory than you really need (but hey - elements will be one or two pointers smaller).
[syntax="freebasic"]
' Initial stuff (1 to anything that is greater than 0 will do of course):
redim Array(1 to 16) as SomeType
dim Index as uinteger
Index = 1
' Adding an element (if there is no more space, double the array size):
if Index > ubound(Array) then
redim preserve Array(1 to ubound(Array) * 2) as SomeType
end if
Array(Index) = Value
Index += 1
[/syntax]
i may experiment to see what one is faster. IM trying to find a fast way to manage a players inventory (and to a lesser degree the inventory of the villians)
Im all about being dynamic and NOT HARDCODING any game content unless it cannot be added afterwords. Linked lists seemed like the way to go...
My game is basically a single player MUD i am a horrid artist... iI am absolutly aweful at composing sound.. im VERY against "borrowing" it. Im sure updating the game at a later date to use graphics wont be all that hard... I have made tile engines before...never tried 3d though (shudders)
The best use of linked lists is in a queue. For example, if you have a list of objects on the screen, you could add and delete items from that list without having to go through the hassle of defragmenting an array
If you have some big objects that need individual allocation anyway, it is smart to create the linked list within the object (just provide a next pointer). Instead of a generic linked list mplementation with pointer to objects
Well as opposed to a dynamic array, if the need to sort the list of items I can tell you that the linked list will run circles around the dynamic array.
Even with quicksort on an array of pointers? I have a hard time beliveing that...
no sorting with linklist are far faster since you can pull a link and move and add it to another part of the list easly.
Consider an example of an array of big elements and an array of pointers to these elements.
[syntax="freebasic"]
type CType
Value as integer
' Other data
end type
redim Storage(1 to 5) as CType
redim Pointers(1 to 5) as CType ptr
Storage array:
1: value: 10
2: value: 15
3: value: 7
4: value: 8
5: value: 20
Pointers array before ascending sort:
1: -> Storgage(1) ( value: 10 )
2: -> Storgage(2) ( value: 15 )
3: -> Storgage(3) ( value: 7 )
4: -> Storgage(4) ( value: 8 )
5: -> Storgage(5) ( value: 20 )
Pointers array after ascending sort:
1: -> Storgage(3) ( value: 7 )
2: -> Storgage(4) ( value: 8 )
3: -> Storgage(1) ( value: 10 )
4: -> Storgage(2) ( value: 15 )
5: -> Storgage(5) ( value: 20 )
[/syntax]
Ie. only pointers needs to be swapped around, which eliminates the slow copy of huge elements if you only had the storage array.
Now that I tried to visualize the concept, can you explain to me in what way linked list would be faster at anything?
Quote:Now that I tried to visualize my idea, can you explain to me in what way linked list would be faster at anything?
Linked lists are faster for removing and inserting elements from/to the middle of the list. Just a matter of changing 2 pointers (assuming bidirectional linked list... because with a single direction, I can see the method of removing an element being implemented really horribly
).
Linked lists are funky, but I think binary trees are even cooler.
-shiftLynx