LinkedList

[Techno]

It's been a while for me and wondered if someone could refresh my mind:

what exactly is a linkedlist?
How does it work?
Why would you use a LinkedList?

[PENNYSTOCK]

http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

[jmcilhinney]

It's a bunch of objects, each with a reference to the next item in the list, so you can navigate from the first to the last by following the chain of references. It's the original way to create a dynamic list, because you can insert an item simply by manipulating a couple of references. .NET collections are easier to use but not necessarily more efficient in execution. The Framework actually has a LinkedList class but I haven't had cause to use it ever.

[Techno]

Neither have I, just thought I would learn a bit more and refresh my memory :) (not linked list type of memory!)

[chemicalNova]

Sounds to me like that question on your homework just got answered :p

chem

[Techno]

:) far from it my friend ;)

all I can understand is that each element contains a reference to the previous and next element...have i missed something big out of that?

[jmcilhinney]

No, that's about it. Each item in the list has two properties: one is the data and the other is a reference to the next item. To be able to access the list you need to keep a reference to the head or first item. From there you can navigate the entire list by following the references in each item and getting the data as you go. Once you find an item with no reference you know you're at the end of the list.

To add an item you just create a new item and assign it to the reference of the current last item. To insert an item between item N and item N+1 you copy the reference from item N to the new item, so the new item now has a reference to item N+1, and then assign the new item to item N's reference.

You can also have a double linked list where each item has a reference to its predecessor and successor in the list, so you can navigate both ways.

[wossname]

You can create lists of enormous complexity just by adding extra references into your items. So you can end up with circular lists (very useful for expiring data), binary trees, ternary trees, quad trees and so on.

For large binary trees, its handy to have an extra references for linking to nodes at the same level as the current one but is otherwise not directly connected to it, many optimisations can be made by sacrificing a bit of RAM in order to gain traversal speed.

Whole books have been written on the basics of linked lists. Knuth's "The art of computer programming" is a fine example.