What are the applications of Linked Lists?

Don Hersey wrote:

 

I use them almost whenever I cannot anticipate how big my data is going to grow.  They are especially convenient when my elements can be of variable size.  I nest them pretty deeply and bizarrely when  am coding graftals.  The coming of STL has made them almost as easy as a regular-old data type.  Vector is a type that is internally dynamic, but allows for integer indexing.  This allows for the ease of an array for a linked type.  I use doubly-linked ones if my traversals are as likely to be backward as forward.

I may have misunderstood you, but in case I didn't: std::vector is not implemented as a linked list. The reason you get to access it just as an array, is because that's exactly what it is (or more precisely what it is an interface for).

It interfaces like an array, but AFIK it is implemented internally as a list. 
This is what allows for vector::resize.

In the case of std::vector, resize() will re-allocate (edit: if necessary) a new block of memory, big enough to hold the entire data and then relocate all the elements in there, in consecutive order.

Edit 2: If you don't believe me, try this:

vector<char> v;

v.push_back('h');

v.push_back('e');

v.push_back('l');

v.push_back('l');

v.push_back('o');

v.push_back('!');

v.push_back(0);

cout << &v[0] << endl;

" If n is greater than the current container size, the content is expanded by inserting at the end as many elements as needed to reach a size of n. If val is specified, the new elements are initialized as copies of val, otherwise, they are value-initialized. "

vector::resize - C++ Reference

The next line after what you just quoted is: "If n is also greater than the current container capacity, an automatic reallocation of the allocated storage space takes place."

From the same site you linked:

vector - C++ Reference

"Vectors are sequence containers representing arrays that can change in size.

Just like arrays, vectors use contiguous storage locations for their elements, which means that their elements can also be accessed using offsets on regular pointers to its elements, and just as efficiently as in arrays. But unlike arrays, their size can change dynamically, with their storage being handled automatically by the container.

Internally, vectors use a dynamically allocated array to store their elements. This array may need to be reallocated in order to grow in size when new elements are inserted, which implies allocating a new array and moving all elements to it. This is a relatively expensive task in terms of processing time, and thus, vectors do not reallocate each time an element is added to the container."

I stand corrected. 

I don't use them anyway.  They don't offer any advantages.

A really fun use of dynamic data structures is to make a bunch of verbs as freight for the list.  Let's keep it simple and consider graphics operations in the two space.  The affine transformations correlate to multiplications by a matrix, so you probably wouldn't implement this particular case this way, but conceptually. . .

You could have verbs like scale, rotate, duplicate, stuff you might see in CorelDraw, say.  By going through the list of verbs, acting upon a list of nouns, behaviors can be executed.  Through insertion, we have something like 'behavioral DNA,' so rather complicated behaviors can be generated in a rather simple way.

This is a fairly good way to construct an L-grammar visualizer, for example.

With more sophisticated STL types, you can implement DSs that are two-way associative, like CAMs.

These can be very useful when constructing parsers, for example.

The real fun comes in when we combine them with functors and pointers-to-function.

Let me give a brief example of a use of a linked list:  Let's say I want to draw a Koch snowflake.  Let's say I already have code for a turtle.  The initiator can be a linked list with three elements.  The data elements are an angle to turn, and a distance to draw, for my initiator, these elements are identical: 2pi/3,1.0.  If this is an input to the draw function, an equilateral triangle is generated.  Then I need an iterator function, but for generality's sake it should also be data-driven.  Another linked list, 0,1/4, pi/6,1/4 pi/3, -2pi/3,1/4, pi/3,1/4 serves as the iterator data.  Running the iterator substitutes the iterator for each element in the initiator, this structure becomes the new initiator, if we want.  We have to add the amt of turn from the original segment to the amt of turn in the new elements to get the total turn for a given element.  Now we have a twelve-element (for we have substituted 4 new segments for 3 old ones) list that renders a star-of-David when fed into the draw function.

To render successive iterations of the snowflake, we only have to re-run the iterator function and draw.  We have to multiply the segment lengths by the new segment lengths if we want to maintain scaling.  Else we can construct an auto-zoom viewer.

Then we can have some 425 and play with both data sets 'til mom or the kids come home.

If we can make the draw function, play a glissando out 'da speaker, rather than draw a line segment on da' monitor, we have crude models for both ontogeny and phylogeny.

//Apologies for my error above, sadly haven't played with any of this stuff for over a decade!  Rusty, rusty rusty.  Thanks for the correction.