Linked List Benchmarking..
Hardly the most scientific based analysis - but it makes the point:
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:
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 = DateTime.Now;
LinkedList<System.String> myList = new LinkedList<System.String>();
for (int x = 0; x < 10000; x++)
{
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++)
{
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
|
2:14.3
|