Building a Linked List System From Scratch in C#, Part 2

Inserting Values Mid-Chain and Finding Specific Values

Micha Davis
Geek Culture
Published in
6 min readSep 22, 2021

--

=[[Value]]==[[Value]]==[[Value]]==[[Value]]==[[Value]]=

Last time we covered establishing the foundations for a doubly linked list class: namely, the ability to create nodes of data with references to previous or successive nodes to form a series. Right now we can add to either end of the chain with our AddFirst(T t) and AddLast(T t) methods. Today we’ll look at inserting data into the middle of the chain based on some reference point.

A quick reminder of two things. First: I’m using Unity to develop and test this system. If you’re following along in a different development environment, you may need to adjust how errors are handled and tests are run. Second: this functionality all exists in C# already. We’re reverse-engineering it for educational purposes, not for practical purposes.

The AddBefore and AddAfter Methods

This next part can get a bit dizzying. We’re going to be using the words ‘next’ and ‘previous’ in varying combinations, and by the end it can get difficult to track. Just keep in mind that four values need to change to add a node mid-chain (two next and two previous). In the diagrams below I add a new arrow each step to show how variables are being assigned — hopefully that helps.

We’ll start with AddAfter(Node node, T t). To add a node after a specified node, we have to do the following:

  • Null check the specified node, and return an error if it is null. We can’t do anything with a null reference.
Today you get paper diagrams instead of digital diagrams because I’m away from my drawing tablet.
  • Create a new instance of the Node(T t) class and increase the list’s Count property.
A new node appears!
  • Set the new node’s Next property to the node referenced by the specified node’s Next property.
  • Set the specified node’s Next property to the new node.
  • Set the new node’s Previous property to the specified node.
  • If the new node’s new Next property isn’t null (meaning we didn’t just add a tail node) we set the Previous property of the node referenced by the new node’s Next property to the new node.

All that reference juggling should result in the new node now resting right after the specified node in the chain, fully connected to its new neighbors. If we were instead trying to AddBefore(Node node, T t), we would reverse the properties in the last four steps:

  • Set the new node’s Previous property to the node referenced by the specified node’s Previous property.
  • Set the specified node’s Previous property to the new node.
  • Set the new node’s Next property to the specified node.
  • If the new node’s new Previous property isn’t null (meaning we didn’t just add a head node) we set the Next property of the node referenced by the new node’s Previous property to the new node. Otherwise, we assign the new node to the _head variable.

In code, these methods look like this:

I know “newNode.Next.Previous” is cumbersome. If you have an easier way to reference this, drop a comment!

The Contains, Find, and FindLast Methods

The next step is to build some methods that allow us to query the contents of our list. Each of these methods works on the same general idea, but with slightly different results.

Contains(T t) is a bool return method. It starts with the first node, and then steps through each node until it reaches the end of the chain. Each step along the way, it checks to see if the value of the node equals the argument supplied in the method call. If it does, it returns true. Otherwise, false.

Find(T t) is a Node object return method. It has exactly the same code as Contains, except when it finds a matching value it returns the node containing that value. This will only ever find the first instance of a given value; successive duplicate instances will be ignored.

FindLast(T t) is a Node object return method. It begins its search at the last node, and then steps backward through the chain until it finds a node with a matching value, which it returns. This will only ever find the last instance of a given value; preceding duplicate instances will be ignored.

Testing the New Methods

Before we can test the AddBefore and AddAfter methods, we’ll need to make sure the search methods work.

To test Contains(T t) we’ll create a test data array containing the numbers 0–9 and search for three values: the first value, the last value, and a value not on the list (just in case).

The test for Find(T t) will need a unique test data array so that we can make sure we find the first instance of multiple matching results. First we’ll make sure we’re finding any valid number at all. Then, to make sure we are finding the correct value, we’ll compare the value in the found node to the value next in the chain. In this case, it should be 5. We’ll also make sure we can’t find a value that isn’t in the array (just in case).

And for FindLast(T t) we simply invert the search terms.

Let’s confirm those operate as expected:

Splendid!

Now, for AddBefore we want to check that we can AddBefore the first node, and it will replace the _head, and then we’ll check that we can add a node prior to the last node, and we’ll find a node in the middle and check that we can insert there as well.

NOW there’s a 10 in there.

Finally, let’s run a similar confirmation of AddAfter:

And the results?

We did it!

That completes our goals for today. In part three we’ll cover removing values from the list, and we will consider some extra features Microsoft didn’t see fit to include in their implementation.

--

--

Micha Davis
Micha Davis

Written by Micha Davis

Unity Developer / Game Developer / Artist / Problem Solver

No responses yet