Applications for linked lists
I have a class that creates files and stores graphics inside. It can also load the files and read graphics into a dynamic array. Each graphic has a unique ID but to reference the graphic I have been using a loop to find the first occurrence of the ID.
Now I want to know if a linked list would be a better structure for this than a dynamic array? Is it easier or faster to search a linked list the way I need to? What are the advantage of a linked list over a dynamic array?
I would prefer to implement this myself instead of use STL or some other library.
Now I want to know if a linked list would be a better structure for this than a dynamic array? Is it easier or faster to search a linked list the way I need to? What are the advantage of a linked list over a dynamic array?
I would prefer to implement this myself instead of use STL or some other library.
An array is probably faster for searching.
A linked list is more useful when you need to either add or remove items somewhere in the middle of the list, which would require shuffling every element along if an ordinary array was used.
A linked list is more useful when you need to either add or remove items somewhere in the middle of the list, which would require shuffling every element along if an ordinary array was used.
A search will be faster in an array, assuming its sorted. If not, they're both O(n) search times. The advantage of linked lists is every other operation on it O(1) time, and obviously you don't need to reallocate it. But a dynamic array reallocation can be amortized O(1) time.
EDIT:
Insertion at the head is constant, and tail assuming you have a tail pointer. Otherwise tail insertion is O(n)
EDIT:
Insertion at the head is constant, and tail assuming you have a tail pointer. Otherwise tail insertion is O(n)
Last edited on
Topic archived. No new replies allowed.