Linked Lists

[ResidentBiscuit]

Ok so I know that they are a container, and they are different then vectors, that about all I know. I'm starting on this graduation program at http://www.cplusplus.com/articles/N6vU7k9E/ and it says I'll need linked lists. It's the only thing I have no experience with, and I've looked it up. All I find is just lists though, I'm assuming they're about the same thing, but is there a difference? Are they just like parallel arrays?

Thanks
-Biscuit

[ResidentBiscuit]

Not sure if I should trust you, with the caps and all :p

[ResidentBiscuit]

Hmm. Prove it. Gimme an example

[Moschops]

Imagine a structure of type X whose contents include a pointer to an object of type X. Make one, then make another one, and make the first one's X pointer point at the second one.

That's a linked list. Extend to as many objects of type X as you like, each one pointing to the next. If you make one of them point at one that's already in the list, it's a circular linked list.

A linked list is not just like a parallel array.

Not all lists are linked lists.

[ResidentBiscuit]

That kind of confused me :/ I think I almost get it, but not quite

[Moschops]

struct X
{
  int a;
  X* theNextItemInTheLinkedList;
};

X firstItem;
X secondItem;

firstItem.theNextItemInTheLinkedList = &secondItem;

[ResidentBiscuit]

So, that sounds like I'll have to write each link manually

[ResidentBiscuit]

Framework, what's your deal?

[Moschops]

People generally end up with helper functions; things like addToEndOfList and putAtHeadOfList. Where linked lists are really helpful, though, is for reordering the list, inserting items into the middle, and removing items. Because the actual objects sit anywhere in memory, if you want to remove item n, you can just make (n-1) point at (n+1) and you're done. Compare that with, say, storing everything in order in an array.

Likewise for reordering the items; you just have to change the values of pointers.

Need to insert a new one at position n? Just make (n-1) point at it, and make n point at n+1. Done.

As with all data structures, there are tasks it suited for, and tasks for which you have better options.