quote:
Original post by Forcas
In some situations you really have to learn linked lists. It''s a lot better than making an array that''s way too big and eats up all your RAM. If you''re making a game, you''ll want as much free RAM as possible.
The bottom line is this: If you''re making an insanely large structure that will grow and shrink use linked lists. If you''re making a smaller structure that you''re pretty sure won''t surpass a certain size, use collections or dynamic arrays. If you''re making something that always stays the same size, just use an array.
I thought the same thing about size comparisons between dynamic arrays and linked lists. Then I learned something interesting. This depends on your interface with the array/linked list. In particular, this is true when your list/array stores pointers to objects, rather than the object themselves. In that case, if you use n elements, the amount of memory used by those n objects is the same, regardless of how you store the list of pointers to them. So all that matters is comparing the memory used by the linked list to the memory used by the array. Now, consider the node structure for a typical doubly linked list. It contains a pointer to its contents, a pointer to the previous, and a pointer to the next. Given that most compilers align structures to power of 2 boundries, that will usually end up being 16 bytes, and it would require 12 at minimum on a 32 bit machine. So that''s 12 * n or 16 * n bytes for the nodes. Now consider an array of pointers. Each pointer is 4 bytes. In a growing only dynamic array, the array will never be larger than double the number of elements, or 8 * n bytes. In a dynamic array that grows and shrinks, the array''s size will never be more than 4 times the number of elements, or 16 * n bytes.
Are you still sure linked lists are more memory efficient?
Ok, then, you might be wondering "what if you store the object directly in the linked list nodes and array?" Well, there''s no point storing directly into the array unless the objects are only 4 bytes. It''s still faster to iterate over an array of pointers than to iterate over a linked list. It might potentially reduce the overhead for a linked list node by 4 bytes, but that''s not likely due to the overhead imposed by aligning to a power of 2 boundry as most compilers do. Switching to a singly linked list can cut the overhead further, but the power of 2 boundry is still an issue, and it significantly removes functionality as opposed to a dynamic array or doubly linked list.
The only advantages linked lists really have over dynamic arrays are these:
1. They are better when order matters, and many elements are being inserted/removed from the middle. However, if you have to search for the insert/remove position, (balanced) binary search trees are even better than linked lists. If elements are only being inserted and removed from the ends, dynamic arrays can do better. If order doesn''t matter, dynamic arrays do better.
2. You have a HARD real-time constraint. Dynamic arrays are faster on average for the above operations. However, every O(n) operations, you have one particular insert/delete that takes O(n) time. In most situations, this doesn''t matter. When it does, linked lists are superior.
It might seem like I''m kind of against linked lists... I suppose I am. They are incredibly overused structures, and I''ve taken enough data structures courses to see that there are better structures for the majority of their common uses. That caught me by surprise when I realized it, because I''d been a big fan of linked lists before that. However, dynamic arrays are really a lot more efficient than I had thought, and I found them to be superior to linked lists in most cases.
