Simple Linked List in C#

Before I start interviewing in earnest, I need to be well-versed on some widely-used data structures and algorithms. We covered all of them (and more) as part of UM’s CS curriculum, but that was long enough ago that I wouldn’t pass the finals now. Implementing these data structures will grant me enough familiarity with them that I’ll feel comfortable answering relevant questions in an interview.

The necessary data structures are linked lists, binary trees, tries, stacks, queues, vectors, and hash tables, as suggested by McDowell’s Cracking the Coding Interview. I intend to cover them in order, rotating between C#, Java and PHP. As I continue this process, I may repeat the exercises in other languages.

I’m not going to duplicate the functionality available in .NET, Java or PHP’s built-in data structures. Even if I could write a better ArrayList than Microsoft, the effort would not bear much fruit. Instead, I’m going to illustrate my understanding of the core functionality of each data structure, with no regard for whether the results are useful.

At its core, a linked list is a collection of nodes, each of which stores a piece of data and a link to another node. In order to illustrate the concept, the list class should also have methods to add or delete nodes. I’ll define each node’s data as a generic in order to build good habits, and provide a GetEnumerator() method in order to more quickly display the contents of the list.

A linked list with two nodes

A linked list with two nodes

Here’s the linked list itself:

And a simple test in the console:

The output of the test is as expected:

Because we Insert() nodes at the head of the list, we end up enumerating the nodes in the opposite order of insertion, as if we’d pushed and popped to and from a stack. We also Delete() from the head of the list.

Making this basic linked list into something we’d actually use for a more extensive application would mean adding most or all of the methods Microsoft exposes in their LinkedList(T) class. Perhaps my most notable omission is that I don’t track the last (or ‘tail’) node, which I’d want to do in order to use this list as anything other than a stack. After adding a ‘last’ member, I’d add InsertAtLast() and DeleteLast() methods, then rename the existing Insert() and Delete() to InsertFirst() and DeleteFirst(). I’d also certainly want Find(), AddAfter() and Remove(T) methods.

The code could also be made more robust with some exception handling, especially for dealing with empty lists.

Microsoft’s Introduction to Generics and the StackOverflow question “How do I implement a Linked List in Java?” helped me write this post.