Sign in to follow this  

Linked list allocations

This topic is 2857 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

A vector stores it's content contiguously, similar to an array of objects. When you're pushing more objects into it than it's capacity allows, it will resize itself. This involves allocating a larger block of memory, copying the old content over to the new memory block and then deallocating the old block. That can be an expensive operation, so it makes sense to reserve some more space beforehand.

A linked list is of a different nature: it's content can be stored all over the place. Each node simply points to the next. Adding and removing objects never requires such an expensive resize operation, so there's no reason to allocate multiple nodes by default.

Share this post


Link to post
Share on other sites
Quote:
Original post by Storyyeller
Why do linked lists perform an allocation after every insertion? Why don't they allocate space for multiple nodes at once like a vector does?
I actually believe that std::deque is fairly close to what you might be thinking of.

Share this post


Link to post
Share on other sites
Quote:
Original post by Captain P
This involves allocating a larger block of memory, copying the old content over to the new memory block and then deallocating the old block. That can be an expensive operation, so it makes sense to reserve some more space beforehand.
You've touched on an important reason there, but there's more to it than simply making sense. A std::vector allocates space for items in advance because it must do so in order to provide an amortised-constant-time push_back operation.
A std::list implementation by contrast, generally does not because it is not necessary to do so in order to fit any performance constraints.
For a std::list it is the job of the supplied allocator to allocate the list item's themselves from a memory pool if so desired for performance reasons. That makes it pretty redundant for the list code itself to also do it.

Or, if you were thinking of a list being represented by small linked arrays, then yet another reason is that you would most likely break the iterator invalidation rules. An erase from a list must only invalidate iterators to that item. The only ways not to break the iterator invalidation rules would mean potentially wasting far more space in the worst case than you can potentially save in the best case. Not to mention the extra overhead of that code that ensures correct iterator invalidation rules.

Share this post


Link to post
Share on other sites

This topic is 2857 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this