Linked List in the 2.0 Framework All that stuff we learned in school is true after all by William Ryan

I've just started getting back into the 2.0 Framework and came across my old friend the linked list. The linked list was one of those data structures that was actually fun to program in C++, mainly because it was really cool and hyper efficient.  Well, by using Generics, the LinkedList is now supported in the 2.0 Framework - and you'll probably want to forget that you ever knew of such a thing as the ArrayList:

Back in CS class - you no doubt learned about the LinkedList and how cool it is - particularly from an efficiency perspective.  Well, although you were certainly free to implement your own, the good folks at MS built one for us in the newest release of the framework - and it's cool.

Just check out the performance difference on something as small as this (and let there be no more arguments in favor of ambiguous typing):

DateTime now = DateTimeNow; LinkedList<System.String> myList = new LinkedList<System.String>(); for (int x = 0; x < 10000; x++)<BR> {       myList.AddHead("Bill");       myList.AddTail("Sahil");       myList.AddTail("KC");       myList.AddTail("Andy");                       myList.RemoveTail();       myList.AddHead("Skicow"); } TimeSpan tp = DateTime.Now - now; MessageBox.Show(tp.ToString());  //.01000 seconds DateTime now2 = DateTime.Now; ArrayList al = new ArrayList(); for (int x = 0; x < 10000; x++)<BR> {      al.Add("Bill");      al.Add("Sahil");      al.Add("KC");      al.Add("Andy");                      al.RemoveAt(al.Count - 1);      al.Insert(0, "Skicow"); } TimeSpan tp2 = DateTime.Now - now2; MessageBox.Show(tp2.ToString());  //.29 seconds Now, here's the impressive part.  Move the counter up to 20,000.  You'll get .02 on the LinkedList but 2.2383 on the ArrayList Bump the counter to 50,000 and you get .07 on the LinkedList and 22.93 on the ArrayList. At 100,000 you get .14 on the LinkedList (just about exactly double) - With the ArrayList 2:14.333 seconds.  Even if I adjust the ArrayList's constructor to accomdodate the 100,000 expected elements, the change is virtually indistinguishable.

         1,000    10,000    20,000   40,000    50,000 100,000
Linked List 0.001 0.01 0.02 0.12 0.7 0.14
ArrayList 0.001 0.36 2.283 10.81 22.93 214.3

The reason is that each time you add something to an arraylist, it needs to destroy the object and rebuild it - hence the exponential curve on time.  The linkedlist uses pointers so to remove an item, it simply substitutes the pointer and viola.  Very very cool indeed.