Archived

This topic is now archived and is closed to further replies.

Linked lists vs. array of pointers

This topic is 5004 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

The other thread on implementing an [] operator on a linked list made me wonder how many here use linked lists, how many use an array of pointers instead, and how many use STL (vectors, etc)? For those that use linked lists, have you considered using an array of pointers, so that you can use [] easily? Personally I''m not an STL guy. And I rarely use linked lists, but use arrays of pointers all the time. What are the pros and cons of each approach? Any other techniques you use instead? Or tweaks to make the above techniques more interesting or efficient?

Share this post


Link to post
Share on other sites
Linked Lists = Fast Insertion and Removal
Vectors/Arrays = Continuos in Memory

Arrays and Vectors are also more cache concious than linked lists, but if you''re only storing pointers in your array, this doesn''t save you much.

If you have a container that will have elements being inserted and removed often, it''s a good idea to consider a linked list, as these operations are inexpensive. Another pro to linked lists, is pointers/iterators to elements are not invalidated when the container changes, where as in a vector, if you remove an element, all pointers/iterators to elements beyond the one that is removed are invalidated.

When inserting an element in a vector, which causes a resize, all pointers/iterators may be invalidated as well.

Sorting a vector can be done in O(nlogn) time, where as with a linked list, most implementations can only acheive O(n^2), since a linked list is not random access.

So general rule is: If the number of elements doesn''t change often, use a vector, otherwise use a linked list.

Share this post


Link to post
Share on other sites
quote:
Original post by Krumble Sorting a vector can be done in O(nlogn) time, where as with a linked list, most implementations can only acheive O(n^2), since a linked list is not random access.


You can merge sort a linked list

Share this post


Link to post
Share on other sites
quote:
Original post by BriTeg
The other thread on implementing an [] operator on a linked list made me wonder how many here use linked lists

I use lists all over the place. I also use arrays. Creating an [] operator for a linked list may be useful on rare occasions, but isn''t a good idea in general. It hides the fact that lists aren''t random access. You don''t think you''re incurring a long traversal time when you see blah[n], but you are when blah happens to be a list.

I''ve actually see list implementations that had no support for GetHead, GetNext, etc., but only GetElement() and []. It''s like they tried to use the most inefficient way to store and retrieve data.

Lists are great to add things onto, put something in the middle of, or even move from place to place. Moving a list element is a few pointer changes, which is tiny compared to many classes. Insertion doesn''t require moving each element after it back one item, or worrying about how to allocate more space to hold the item. Removing items also doesn''t require a long copy everything down by one item process.

Lists are great, but they''re not the only data type. Use them appropriately. If anything I''ve said above seems surprising to anyone, go back to the basics and learn how these things are supposed to work.

Share this post


Link to post
Share on other sites
quote:
Original post by sjelkjd
quote:
Original post by Krumble Sorting a vector can be done in O(nlogn) time, where as with a linked list, most implementations can only acheive O(n^2), since a linked list is not random access.


You can merge sort a linked list


True, sorry forgot about that, but I believe STL''s implementation uses insertion sort for lists.

Share this post


Link to post
Share on other sites
quote:
Original post by Krumble
True, sorry forgot about that, but I believe STL''s implementation uses insertion sort for lists.


There are multiple STL implementations. Both VC7.1 and g++ 3.3.1 come with a list::sort() that uses merge sort (heck, there even is a public list::merge() function, that should be hint enough ). And the C++ standard mandated (23.2.2.4) that list::sort() be O(N log N) anyway, so that pretty much rules out insertion sort.



“Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.”
— Brian W. Kernighan

Share this post


Link to post
Share on other sites