Linked List — InsertAt

6 min readNov 5, 2020

In the interest of improving my DS&A skills, I want to walkthrough a small component of a common problem that a developer is bound to encounter, either in an interview or in the wild. Let’s take a look at the insertAt method for Linked Lists.

Problem Statement

Given an index and a value, insert a node at the specified index of a Linked List. For the purposes of this article, I am not going to walk through the LinkedList and Node classes. So, to start, this is what we should have.

Edge Cases

Any developer worth their salt will consider edge cases that can cause a break in the code. In this case, we have several. Let’s begin with the most-obvious.

Empty List

In the case that we have an empty LinkedList, we want to insert the Node at the beginning of the list. Checking for an empty list is almost universal for implementing any methods involving LinkedLists. This is relatively simple to do.

We know that an empty list will not have a head node. Therefore, we will simply use a conditional statement to determine that, and, if the list is empty, insert a new Node with the given value at the beginning of the list. Then, we return, so that no more work is done. Let’s see what that should look like.

Not too bad so far, right?

Index is 0

In this problem statement, we are going to assume that, if the given index is 0, we will simply insert a new Node with the given value at the beginning of the list.

We can do this with 2 quick lines of code. First, we create a conditional to check whether the index given is 0. If it is, we want to assign our new Node to the head of our list. Then, we return.

Note: In our Node class, each instance of Node is created with two properties:

A data property
A next property, which is a reference to the next node in the LinkedList

By default, this next property is set to null. We can utilize this in our assignment by simply referencing the head property, and assigning it to the next property of our new Node instance. That might seem a little confusing at first, but seeing the code may help. Here’s how it should look.

Great! Now, we have handled our first two edge cases. We have one more that will become apparent in just a moment. First, let’s create some pointers.

Pointers

Due to the fact that a LinkedList does not have indices like an Array does, we generally have to traverse a list one by one. However, this leaves us with an obvious problem: even if we find the node at the index we are provided, we need to insert a new node at this index, and update our references. In order to do this, we create pointer variables, which help us to keep track of the node(s) that we are working with.

The first pointer that we must define is previous. This refers to the node that comes before the current node.

In traversing a list, we want to start at the beginning. With that being said, there is not a node that precedes the head node. Thus, we will set our previous pointer to reference the head node to begin, and advance it accordingly as we traverse the list. Here’s how that should look.

OK, moving on.

Node (Current Node)

As we traverse a list, it is important to keep track of our current node, which I will refer to as simply “node.” As mentioned above, we want to start at the beginning of our list. Thus, we want our node pointer to start at the head node. So, we follow the same procedure that we did with previous.

Cool! We are almost ready to start moving through our list.

Count

As I mentioned above, one distinction between an Array and a LinkedList is the absence of indices. So, to counter this obstacle, we will create a pointer called count, which will keep track of where we are in the list.

I will say it a third time: we want to start at the beginning of our list. So, we will start our count pointer at 0, and advance it by one for each node as we traverse our list.

Just one more declaration to go! Then, we can handle the juicy stuff.

newNode

This step is not absolutely necessary, as we can simply call our Node constructor directly to create our new node. However, I find that it makes it easier to store this value in a variable, newNode.

This one is pretty simple — we simply want to create our new node with the value that we are provided.

Fantastic! Now, let’s handle the actual meat of this problem.

Looping Through

As we traverse our list, it is important to know when we have reached the end. In this case, we know that the end of the list will be indicated by the node that has a next property of null, meaning that there is not another node to which it points. We will handle this in just a minute.

Now, onto the loop. We want to continue along the list until we reach the index that we are provided. Once there, we need to break and create new references between the 3 nodes:

The previous node, which will point at the newNode.
The newNode, which will point to the current node, or simply node.
Node, which will remain unchanged — it will maintain the same next property as before.

In this case, it is best to use a while loop, which will handle two potential outcomes:

We have reached the end of the list, in which case we add newNode to the end.
We reach our index, in which case we follow steps 1–3 above.

Almost there. Now, we know that we have reached the end of our list when the next property of node is null. So, as long as node.next is not null (or it is “truthy”), we will continue to traverse the list. Once we reach the end, we will exit the loop. Let’s set this up.

We are getting there.

We are ready to loop through our list. Let’s handle our first case — if/when we reach the given index in the list. As we said before, we do not have a “true” index, but our count variable is there to save the day. Once we reach the index (index equals count), let’s do some more assignment!

Caution: if you are coding along, don’t run this code! You will hit an infinite loop in the case that our given index value is “out of bounds.” For the purpose of this problem, if our index is beyond the bounds of our list size, then we will simply tack on the newNode to the end, and return. We will handle this at the end of our method.

Keep it Moving

As we move along the list, we are looking for the node at the index (count) that we are given. If we don’t find it with the current node (node), then we want to keep traversing our list. We can do this by incrementing and reassigning the values of previous and node.

We want count to increase by one as we loop through each node. Simple enough. Then, we want to update the previous node to look at node. Finally, we want node to look at the next node, effectively moving all of our pointers forward by one for each iteration.

One last case to handle, and we’re on the Gravy Train with Biscuit Wheels.

The Final Curtain

As we discussed above, we will know that we are at the end of the list when node.next equals null. When this happens, we will exit our while loop. This means that we did not find the index, meaning it is looking for a node beyond the size of our list. We have one last thing to do — add newNode to the end. We can do this by updating the next reference of node, our current node.

And, as always, don’t forget to return!

There it is! You can now insert a node at a given index of your LinkedList!

Note: I passed in index as index to the method, but referenced it as idx on line 31. Make this change, and your code should run fine.

Refactor

I know that this solution is not the prettiest, so I will give you a refactor. It may take a few seconds to understand how it approaches the problem, but the code will run the same.

As always, Happy Coding!