Using C#

The LinkedList Class

We'll first explore the doubly-linked list implementation built into .Net:

Create a console application

Repeat the following 20 times (using a for loop on the variable n):

Use the DateTime.Now attribute to store the start time

Create a new LinkedList

Add 1,000,000 * n integers (random or fixed - it doesn't matter) to the LinkedList via the AddFirst method Record the end time using the DateTime.

Now attribute Print out how long it took (using end.Subtract(start) to get the TimeSpan)

Take these results and plot them in a spreadsheet application (you can click on the "C:\" icon in the console application and select "Edit | Mark", highlight the data, then press "Enter" to get the results in the clipboard) You might need to save the "output" into a TXT file and then open it in Excel to have it parse the results into individual cells. Using the ":" as a delimiter can be useful in separating the data into columns.

Rolling our Own List Class

Now let's use our own Node class and measure its performance

Continue with your console application, but comment out your LinkedList code from above.

Define a new class, "Node", and add data (integer) and next (Node) attributes.

Declare two Node references/objects in the main program called "first" and "temp".

Repeat the following 20 times (using a for loop on the variable n):

Use the DateTime.Now attribute to store the start time

Set "first" to null.

Add 1,000,000 * n Nodes. This can be done by "new"ing temp to a new Node, filling in its data, and pointing its "next" to first. Then make "first" point to "temp". This adds a new node to the front of the list.

Record the end time using the DateTime.Now attribute

Print out how long it took (using end.Subtract(start) to get the TimeSpan)

Take these results and plot them in a spreadsheet application in a new series and compare these times to the earlier times.

How did your Node class implementation do relative to the built-in LinkedList class? Why the difference? What would make yours better/worse?

The List Class

So your Node performed better... so you're better than the programmers at the Microsoft .Net team, right? Let's wait before we reserve judgment. Let's explore another collection class built in to .Net... the List class.

Continue with your console application, but comment out your code from above.

Repeat the following 20 times (using a for loop on the variable n):

Use the DateTime.Now attribute to store the start time

Create a new List

Add 1,000,000 * n integers (random or fixed - it doesn't matter) to the List via the Add method

Record the end time using the DateTime.Now attribute

Print out how long it took (using end.Subtract(start) to get the TimeSpan)

Take these results and plot them in a spreadsheet application in a new series and compare these times to the earlier times.

How did the List class do?

Plot the timing results for all three data structures. Which one is the best? Why?

Bursting the Bubble

OK - so the List is the best, right? Let's see..

Repeat the code you did on the List class above, but this time, use the Insert method and place the new numbers at the front of the list (the Add method places the numbers at the end)

Rerun, and measure the performance. But DON'T repeat 1,000,000 times each loop - only repeat 10,000 times. Otherwise, you'll be waiting for quite a while!

Search on the concept of capacity and how this adjusts to determine why this collection class performed as it did. Knowing what you know about the List class and capacity and how it resizes itself and "makes room" for new elements, why did this perform as it did when inserting into the front as opposed to inserting at the end?