Building a Linked List System From Scratch in C#, Part 1
A fun exercise for practice juggling variable references
I have written about the usefulness of Linked Lists in the past. Today, I want to get into the mechanics of how a linked list works by creating my own implementation of linked list functionality.
NOTE: Linked Lists are already implemented in C#. This exercise will duplicate that functionality, but it is not at all necessary for you to implement your own version of this for your work. I did this as an exercise in understanding how some features might work, for educational purposes not for practical purposes.
What is a Linked List?
The title image gives the gist of how a linked list operates. Rather than a simple list of values, a linked list maintains references to other values. This forms a chain of “links” between the values. The image above represents a “doubly linked list,” in that each value node references the nodes before AND after it, making traversal in either direction simple. Singly linked lists (which point only to the next node in the chain), and circular linked lists (in which the last node points to the first node, forming a circle) are two other kinds of linked lists.
Because of the chain of references, it is easy to insert or remove values from the middle of the list with no added complexity. Similar operations on traditional lists would require iterating through the entire list, but with a linked list we can accomplish the same result without any iteration at all.
The Doubly Linked List
For the next several articles we’ll be creating a DoublyLinkedList<T> class. The goal is to reverse engineer each of the the public methods and properties of C#’s LinkedList<T>() class. Namely:
- First and Last properties pointing to the respective ends of the chain.
- Count property to reference the number of links in the chain.
- AddFirst(T t) and AddLast(T t) methods, to add new nodes at the ends of the chain.
- AddBefore(Node node) and AddAfter(Node node) methods, to add nodes somewhere between the ends of the chain.
- Remove(Node node), RemoveFirst(), and RemoveLast() methods, which nullify the references to a specific node in the chain and close the gap in the chain, if necessary.
- Contains(T t) bool return method to find if a value exists in the chain.
- Find(T t) and FindLast(T t) methods for searching from either end of the chain.
- CopyTo(T array, int index) method to copy the values from each node into an array at a specific index of the array.
The Node Class
We start with the Node class. This class defines the necessary properties of an element in our linked list, and provides the constructor for creating new nodes.
This class goes inside the DoublyLinkedList<T> class, for easy reference. The constructor accepts a single argument representing the intended value of the node. The adjacent node reference properties (Previous and Next) begin as null.
The DoublyLinkedList<T> Class
Now that we have nodes defined, we can create some properties and fields within the DoublyLinkedList<T> class itself.
Here we first define the front of the list to be a Node variable called _head. The First property naturally needs to point to this field. To find the Last node requires some logic, which we will get to in the next section (for now, we can tolerate some red squiggles).
The Next and Previous properties in this class are then set to point at the head node’s Next and Previous properties.
Finally, we define a _count field with a counterpart property containing logic to constrain the count to above 0. We only want this class instance to set the value of its count, so we make the setter private.
The GetLastNode() Method
In order to get the Last property working, let’s start with the GetLastNode() method.
Here we simply start at the _head and move forward one node at a time until the Next node is null (meaning there are no more nodes in the chain). Once we have that, we return the node. Easy!
The AddFirst(T t) and AddLast(T t) Methods
Now, how about we actually create some nodes?
To add a node, we pass the method’s argument into the Node constructor and increment the Count property.
If this node is meant to be the new head, we first check if the current head is null. If it isn’t, we point our new node’s Next property at the head node, and the head node’s Previous property at the new node. Finally, whether the head was null or not, we make the new node the head.
If this node is meant to be the new tail, we first check and see if the head is null — if it is, then the list is empty and we only need to designate the new node as the head. Otherwise, we’ll need to run the GetLastNode() method. Once we have the last node, we can assign the new node to the last node’s Next property and then assign the last node to the new node’s Previous property. This effectively makes the new node the last node.
Testing the Class So Far
We now have enough basic functionality to run a few unit tests and make sure everything is working. If you need to know how to set up unit testing in Unity, be sure to check out my article on the topic.
Since I know I’ll be testing all of my Doubly Linked List methods I’ll start by creating a helper method to build testing data. This method will create an array of 10 integers with values from 0–9.
For the first test method we will test AddLast(T t), Count, and Next since they all come into play when creating a new list. I’ll create some test data and then attempt to AddLast(T t) until all the data from the array is in the linked list.
Along the way, we will check that the value added matches the expected value. We will also compare the Count property to the length of the array to make sure we’re properly tracking nodes as they are added.
Finally, we’ll call one more helper method to compare the test data array to the test list. We’ll end up using this method for almost all of our future tests.
As we iterate through the indices we’ll check if we’ve reached an unexpected null node before the end of the array. If that goes smoothly, we’ll then compare the test data at the current index to the current node. If they match, we move to the next node and iterate the index. Otherwise the Assert() method will tell us where the data doesn’t match.
We’ll also make a similar test method to check that the AddFirst(T t) class and Previous property work.
Once again, we build the test data and use it to populate a list. We make sure as we do, that the data matches what we expect. Rather than use the forward progressing helper we created above, we’ll need to progress backwards through this list to confirm the data matches. While we are iterating through indexes, we make sure the list is also iterating apace. Finally, we confirm the values of the nodes match the respective indices of the array and that the Previous property works as intended.
Now, let’s see how those tests turn out:
That’s it for this first part. In the next article we’ll tackle AddBefore(Node node), AddAfter(Node node) and our three search methods: Contains(T t), Find(T t), and FindLast(T t).