Pratical use of link list

[agoswami]

Hi,
Could anyone proivde me some pratical scenario in code where we need to use
link list.

[bigearsbilly]

you could keep a list of replies to
a thread that is asking for a practical use for a linked list.

[agoswami]

:)

[kempofighter]

another answer would be anytime you need a collection of objects of the same type but do not need a random access operator[] for accessing each element. A linked list needs to be iterated over forwards or backwards. It allows you to move objects within the middle very easily and allow efficient insertion at any point within the list. The reason that you need a list is similar to the reason for needing an array of some kind. A list is is a very specific kind of sequence container with different performance characteristics and interfaces.

[filipe]

kempofighter wrote:

another answer would be anytime you need a collection of objects of the same type but do not need a random access operator[] for accessing each element.

A std::vector is still more appropriate than a list if you need to traverse the entire container very often, right?

[korg]

With STL added into C++ ; majority of the uses i guess are shadowed.

Vector is pratically a C++ array where as list is a doubly linked list. So vector access is indeed fast , but then you need to deal with re-allocation & invalidated iterators

[Galik]

If you are frequently inserting elements into the middle of the data then linked list looks quite attractive.

Imagine a program that records midi data into music notation. You might decide to make each bar of music a link in a linked list. That way it is quick to insert new bars of music on the fly while capturing the midi data.

With a vector you would have to constantly be shuffling memory around.

[m4ster r0shi]

Food for thought:

I've been wondering, how could I implement a container that offers both fast access and fast modification of the data held?

Would a list of static arrays be a good approach? If the array size is big, access time is improved and if it's small, modification time is improved. In the trivial case where the array size is 1, I have a simple linked list, while in the case that the array size is very big, the behavior of my container converges to the one of a vector. Depending on my problem, I could set the array size so that I have the best overall performance.

What other ways are there to do something like this?...

[rollie]

That sounds a lot like a hash table with chaining as the collision resolution mechanism, although you sacrifice maintaining list order for increased search speed.

--Rollie

[kempofighter]

A std::vector is still more appropriate than a list if you need to traverse the entire container very often, right?

It is more important to worry about how often you will be growing the container or whether you need to insert within the middle. I think that I see what you are saying but I do not know if iterating over a vector is significantly better than iterating over a list. If inserting in the middle or sorting will not be done often or never done then I would always choose deque or vector. In fact I cannot say that I have found many uses for the std::list. I almost always use deque or vector. Moreover deque is for when you want to insert at both ends because the memory doesn't need to be contiguous. A vector is not good if you are inserting in the beginning because all objects would have to be copied in order to shift them in memory. On the other hand if you need a container that is compatible with c-arrays (contiguous data storage) then vector is the only choice. In the latter choice it is sometimes a sacrifice where you choose the functionality over the performance because for whatever reason you have to have contiguous elements.

[jsmith]

m4ster r0shi: That's called a std::deque.

Inserts in the middle are faster on average than vector and slower than list, but random access
is faster than list and in theory as fast as vector. (Technically amortized constant time
versus vector's constant time).

Generally I agree with kempofighter; std::deque is almost always more appropriate than
std::list or std::vector. std::vector<> should be preferred when contiguous memory is
required (which isn't very often).

[m4ster r0shi]

jsmith wrote:

That's called a std::deque.

Indeed! But a deque doesn't allow me to set the internal array size :/ I'd really like something like this:

template < class T, unsigned int block_size, class Allocator = allocator<T> > class deque;

I know it sounds strange coming out of me but what does boost have to offer on this?

[kempofighter]

Since deque doesn't require contiguous storage the reserve function doesn't make sense. This makes me wonder when the deque decides that it needs multiple chunks of memory. Its internal organization must be much more complex. I've been meaning to write a test memory allocator to study the deque as I am curious as to how and when it requests more memory from the allocator.

Perhaps the idea is that the deque is so smart that you don't need to set the internal array size. In order to use such a feature you would have to know a lot about the internal organization of its memory. With vector there can only be one contiguous block which is why the reserve function makes sense for it. If you insert into the front the deque will probably make a new chunk of memory unless the first element already is part of a memory chunk with space. I see what m4sterr0shi is saying though. He wants to be able to give the deque instructions about how big each memory chunk should be. The block_size needs to be some multiple of sizeof(T) though doesn't it? I guess I don't know enough about the deque implementation to determine whether such a feature would be useful.

[PanGalactic]

A unique feature of std::list is the splice() member function. It permits moving nodes from one list to another. What can be done with this is to reserve all the nodes that will be needed in a pool list and then splice those nodes in as needed to a working list and then back to the pool again. This can be a huge efficiency gain for nodes that contain large objects. We use this when filtering through massive amounts of data that contain a variable number of data points. It reduces the amount of memory allocations required significantly.

[jsmith]

@m4ster r0shi:

I think you have me beat on that one...

@kempofighter:

At least in gcc:

  /**
   *  @if maint
   *  @brief This function controls the size of memory nodes.
   *  @param  size  The size of an element.
   *  @return   The number (not byte size) of elements per node.
   *
   *  This function started off as a compiler kludge from SGI, but seems to
   *  be a useful wrapper around a repeated constant expression.  The '512' is
   *  tuneable (and no other code needs to change), but no investigation has
   *  been done since inheriting the SGI code.
   *  @endif
  */
  inline size_t
  __deque_buf_size(size_t __size)
  { return __size < 512 ? size_t(512 / __size) : size_t(1); }

but the implementation is not mandated by the standard.

[agoswami]

thanks a lot for reply it is always good to understand discussion which help to increase your knowledge but I had another request .

can we concentrate to specific question which help the other people who was looking for answer.

[jsmith]

The answer, which can be inferred from the above discussion, is that there is never a time when you
need a linked list. There are times when perhaps a linked list is the best/most efficient data
structure, but other data structures can work also. The discussion centered around some of the
tradeoffs you must make as the programmer when deciding whether to use a linked list or a different
data structure.

[agoswami]

great & thanks a lot jsmith