C# Tutorial: Linked List

For archive purposes, I am posing a custom, generic, sortable, event-driven, doubly-linked list. In the future I will run some tests on it to see if it beats the current linked list implementation provided by the .NET framework. For those unsure of what a linked list is, here is a small tutorial on it.

Collections

When programming a computer, it is very common to store many items of the same type. Some different types of storing methods include array’s, lists, and linked lists. The array is probably the most common for those attempting to store items. When an array of items is specified, the computer goes into memory and searches for a place to allocate the array. If it cannot allocate the entire array, it will keep searching. until it can.

Now the problem with the array rises when someone runs out of room in their array. If they have an array that is 5 items large, and they want to hold a 6th, they must now re-define an entirely new array that can hold the new information. This requires the computer to go through and find another spot in memory that is big enough, place the new array in there, and then copy the elements from the original array to the new array. This problem is where a linked list comes in handy.

The Linked List

When a linked list is used, every item is stored in a chain of items. The linked list works by housing the references to the next (and previous in doubly linked lists) items in the chain. To do this, it is common to house your value inside a node. That node contains a reference in memory to the next node. Thus, you can define nodes anywhere you want in memory as long as you link to it making it easy to add and remove any amount of elements in the chain. The code would look something like this if you are trying to store integers:

Problems

With anything in computer science, there are downfalls to using Linked Lists. In order to get to an element in the linked list, you must traverse the entire list until you get to that element. This can be time consuming if there are a lot of nodes. Another problem is if you lose a reference to one of the nodes, you break the entire list. However, in a lot of circumstances, it is very useful to be able to add and remove items on the fly just by changing references.

Source

Here is an example doubly linked list example that I wrote. Thank dusda for the event driven idea. It is a doubly linked list that will convert to an array if needed. It supports any data type, and automatically sorts if specified. There is even support for getting an item by it’s location (index). I hope you all find it useful.