What are linked lists all about?

Linked lists are a data structure that utilize non-contiguous memory. Made up of nodes, each node will contain a piece of data and a pointer.

We can see here that nothing is pointing to the first node. This is the head, while the last node’s pointer is null. This is the tail.

Alright, let’s look at some code!

Above we can see two class definitions: one for the linked list itself and one for the nodes. The LinkedList class shows us that each instance will default to no head, unless specified. The Node class shows us that each node will accept the data being passed in as its own and has a ‘next’ attribute set to null. We’ll look at setting the next pointer shortly.

So now that we’ve taken a look at the pieces, let’s put it all together. We’re going to use a linked list to represent our grocery list.

We can see here that after we’ve defined our first node on line 37 (setting its data as the string ‘Apples’ ), we can define a grocery list as a new instance of the LinkedList class and set its head to node1. After the second node has been defined we are able to set node1.next to point to node2.

Now that we’ve put this list together, the next reasonable question is: “What can we ACTUALLY do with it?” To demonstrate some functionality of a linked list, we’re going to add a method to the LinkedList constructor.

Looking at this method, we can see that we’ll simply iterate through the groceryList incrementing count as we go, and log a string to the console.

We can call this method with ‘groceryList.size();’ and expect to see ‘This linked list has 5 nodes.’ printed to the console.

So, this is pretty interesting stuff here, but let’s kick it up a notch!

Doubly linked list

Up until recently, we have been working with a singly linked list. That is to say we have been looking at a single pointer which directs us to the next node. Now we will include a second pointer which directs us to the previous node. Below we will update our code to reflect this.

So you can see we’ve added prev (previous) in our Node constructor giving us the opportunity to add our second pointer. Additionally, after defining each new Node, we set our previous node.

You may have noticed by now that we have beans listed twice in our list. That’s a lot of beans… so we’re going to write another method. This time it will be to remove duplicate nodes.

In this method, we will store the data of each node in an array. As we iterate through the nodes, we can compare each node’s data to the contents of the array. If a duplicate is found, re-arrange the pointers to remove the duplicate.

Before we remove the duplicate node, we’ll run a simple method to display the data in each node in the console. After this, we will then run our removeDuplicates method and again display the data of each node noting the difference.

At this point we should consider if there are any distinct advantages of using a linked list rather than an array. After all, both data structures organize separate pieces of data in an iterable fashion. In JavaScript there are helpful methods to push or pop elements to, or off, the end of an array, but adding new elements in the middle of an array is quite the challenge. This is where linked lists shine.

We are going to accomplish this in a few steps:

• Define the new node (basil).
• Iterate through our groceryList from the head until we have found the appropriate index.
• Disconnect the existing pointers, rearrange, and then create two new ones.

In the above graphic, we can see the existing black arrows have been rearranged to connect to our newly inserted node, and new red arrows have been added to complete the new relationship between affected nodes.

You may observe in the above code that a linked list does not have an assigned index number for each node, but we’re able to increment a counter (indexTracker) to keep track of where we are.

Finally we will log the data of each existing node in groceryList, insert the basil node, and log the data of all groceryList nodes.

The complete code for this walkthrough can be found here.

Hopefully this article has shed a little light on an interesting topic that is well-covered in the book, “Cracking the Coding Interview” by Gayle Laakmann Mcdowell.