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.

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)

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