diffrence between using list<type> and pointers (classic C) for linked lists

Question

What is the pros/cons of using the built-in std::list instead of an own linked list implementation based on pointers like in C?

Are there some special case where one is preferred over the other?

Answer 1

The answer provided by Walter covers the main reasons to prefer the stl implementation. The main reason to consider a clasic C style implementation is increased performance. The cost of this increased performance is primarily the potential for errors. This can be addressed with testing and the inclusion of some appropriate asserts (checks for null pointers..._

Contrary to the statements in Walter's answer there are cases where a high performance list is a good data structure choice.

If you need the performance of a custom list but want to avoid the work of constructing and testing your own check out the boost intrusive lists (singly and doubly linked) at: http://www.boost.org/doc/libs/1_39_0/doc/html/intrusive.html These will get you the same performance as a custom construction with (almost) the convenience of the stl versions.

Answer 2

Typically, you want to use std::list, as answered by @Walter.

However, a list implemented by "intrusively" integrating the next (and prev, if any) pointer directly into the contained objects, can avoid several disadvantages of std::list and the other STL containers, which may or may not be relevant to you (quoted from Boost.Intrusive documentation):

• An object can only belong to one container: If you want to share an object between two containers, you either have to store multiple copies of those objects or you need to use containers of pointers: std::list<Object*>.
• The use of dynamic allocation to create copies of passed values can be a performance and size bottleneck in some applications. […]
• Only copies of objects are stored in non-intrusive containers. Hence copy or move constructors and copy or move assignment operators are required. Non-copyable and non-movable objects can't be stored in non-intrusive containers.
• It's not possible to store a derived object in a STL-container while retaining its original type.

The second point is probably not applicable for most typical usages of lists, where you would dynamically allocate the elements anyway.

If the last point is relevant to you, you may be interested in Boost.PointerContainer ‒ although a std::list<std::unique_ptr<Obj>> usually also does the job well enough.

Instead of completely implementing a list yourself, have a look at the aforementioned Boost.Intrusive library.

Answer 3

There are plenty of good reasons to use std::list instead of your own linked list implementation:

1. std::list is guaranteed (via the c++ standard library's implementation of standard) to work as explained on the tin (no bugs, exception safety and thread safety as by the standard).

2. std::list does not require you to spent time developing and testing it.

3. std::list is well known so that anybody else every working with the code (or yourself later in life) can understand what's going on without the need to first get to grips with a custom linked list implementation.

I cannot really think of any good reason to use your own custom linked list.

std::list is usually implemented as a doubly-linked list. If you only need a singly-linked list, you should consider std::forward_list.

Finally, if you're concerned with performance, you shouldn't use linked lists at all. Elements in a linked list are necessarily allocated individually (and often inserted at random places), so that processing a linked list generally results in many cache misses, each giving a performance hit.