What are the applications of Linked Lists?

A bit of a late reply, but here it is.

Inserting an element inside a linked list is as simple as assigning the previous node's "next" property to point to this new element and the "next" property of this element to whatever the previous node's "next" was pointing to.

elm->next = prev->next;

prev->next = elm;

Removing an element from the list is equally light:

prev->next = elm->next;

If you had a std::vector for example, all the elements after the insertion or deletion position would have had to be moved and possibly a new block allocated to fit the new size of the vector (the vector guarantees that all the elements are one after the other in memory).

The downside is that if you want to access the n-th element, you'll have to go trough all the elements before it.

To answer your question: you go for linked lists when you care more about insertion and deletion performance, than for random access.

Thanks for the replay, I appreciate.

why do you wish to use a "linked-list"?? "linked-lists" comes in many flavors, FIFO (First-In-First-Out), FILO, LIFO. A FIFO in real life would be a plate holder in your cafeteria. ie the one on top is always first. You can find out more in any good college text dealing with "Data Structures" some are very practical and some show you the math behind them.. I like C & Data Structures (P.S. Desbpande) or if you really want more look through Fundamental Algorithms (D. Knuth) its a 4 volume set.. hey I survived volume 1.  

Try this:

Linked list - Wikipedia, the free encyclopedia

@Christina - A FILO implented as a linked list will make your brain hurt - since you would have to traverse the list backwards.

The plate holder is a FILO - First In (at the bottom of the pile) is Last Out, the plate holder is most often used as a stack illustration.

MK

There's nothing wrong with a FILO container implemented as a linked list, in fact it's the preferred approach. The elements can always point both ways so there's no trouble with that.

Razvan

Well, yes and no, to work as  a FILO you need to be a Doubly or Multiply linked list which isn't quite the same thing. (I'm not sure how frequently the distinction is made.)

Of course, since I "code" more in VHDL than anything else the idea of linked lists is pretty abhorent to me - I'm used to FIFOs that can provide one result per clock cycle - containers sound like something from the OOP world

MK

duh, brain fart your quite right... almost never use them..

there is not distinction between single or double linked list.. they are all inclusive.

nope they were here before OOP.. They where here in BASIC (Dartmouth), and FORTRAN (well before 77)

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.