My First Data Structure: Linked Lists
If you, like me, are a developer whose primary coding languages are either JavaScript or Ruby, I’m guessing you’ve probably never used a Linked List before. Much like arrays (which I’m sure you are familiar with) and hashes (checkout my post about hash tables!), Linked Lists are a very useful data structure and knowing about them will not only help you ace a technical interview, but will also help you writer smarter, better code.
Although neither JavaScript or Ruby offer us a built-in LinkedList class, don’t worry! In this post I’m going to walk you through how to implement your own LinkedList class in JavaScript so you can become a LinkedList expert and enjoy the many benefits of this elusive data structure.
Why LinkedLists?
As I mentioned in my previous post on hash tables, arrays have some issues. One major issue is that an array is of a fixed size and when an array gets filled it will have to undergo a costly resizing operation. LinkedLists on the other hand are flexible, meaning that elements can be added indefinitely without said costly resizing operation.
LinkedLists are also more agile than arrays when it comes to inserting or deleting elements. In an array, when an element is inserted or deleted, all of the elements and their associated indexes will have to be shifted and adjusted accordingly. LinkedLists on the other hand can have elements inserted or deleted without shifting other elements, making the runtime performance of those operations much more efficient.
What is a LinkedList?
A linkedList is a linear data structure, containing nodes wherein each node contains data and a pointer (or a reference) to the next node in the list.
In the diagram above, the nodes are represented by the rectangles and each, as you can see, contains two sections: a data section and a “next” section. The data section of a node can contain data of pretty much any type and the next section is purely a reference to the next node in the list.
Written out in JavaScript, a very simple LinkedList might look something like this:
{ val: 2, next: { val: 17, next: { val: 23, next: null } } }As the diagram shows, the first node in a LinkedList is referred to as the head. Similarly, though not shown in our diagram, the last node in the list is called the tail and is indicated by a “next” value of null.
LinkedLists in JS: My implementation
As I mentioned before, JavaScript does not come with a built-in LinkedList class, however, we can implement our own LinkedList class in Javascript fairly easily.
To get started, as we would with most classes, we want to build a constructor:
class LinkedList { constructor(val) {
this.head = {
value: val,
next: null
}
this.tail = this.head
this.length = 1
}}
As you can see, our constructor, will initialize our class with three properties: head, tail, and length. As I explained above, the head is the first node in a list and the tail is our last value. Of course, when we are creating a new list, we will have only one node and thus the head and the tail will be the same. We also are initializing our new list with a length of one, which again makes sense given that upon creation we will have only a single node in our list.
Now that we have our constructor written, we can write some methods that will allow us to add elements to our linked lists: append and prepend.
Append
When we call on the append function, we will want to pass in a value and add that value to the end of our list. So, how do we go about doing this?
First, we will want to create a node with the two properties all nodes must have: value and next. Value, of course, will be passed in as an argument when the function is called, but what will next be?
I mentioned above that the final node in a LinkedList is referred to as the tail and that the tail is indicated by having a next value of null. Since we are adding this new node to the end of our list, it will, of course, become our new tail and thus we can give it a next value of null:
append(val) {
let newNode = {
value: val,
next: null
}
}Now that we have our new node created, we will want to connect this new node to the previous final node aka the current tail of our linked list:
append(val) {
let newNode = {
value: val,
next: null
}
this.tail.next = newNode
this.tail = newNode
this.length++
}As you can see, first we replaced our tail’s next value with our new node. Then, we updated our tail, by setting it equal to our new node. Quick note: It’s important that we do those actions in that specific order as if we were to try and make our new node the tail before setting the previous tales next value to our newNode, we would not be appending a node, but instead just losing our previous tail and replacing it with our new node.
Prepend
The next, and final, method we are going to look at today for LinkedLists is prepend, wherein we want to add a node to the beginning of our list.
We will start this function similarly to how we started our append function: by creating a new node. Given, however, that we are going to be adding this new node to the start of our list, and not the end, we will want to reconsider what the next value of our new node will be.
prepend(val) {
let newNode = {
value: val,
next: this.head
}
this.head = newNode
this.length++
}As you might have guessed, since we are adding our new node to the start of the list, then the new node’s next value will be the current starting node in our list (aka the head).
Just as we did with the tail in our append function, we will want to replace our current head with our new node and, as it did before, order matters. To reiterate: we cannot replace the head of our list before we have that head saved as the next value in our new node.
Next week on LinkedLists
Now that you know how to create a LinkedList and add elements to both the end and beginning of said list, think about other methods that we might want to give our list. Some common ones include: insert (which would allow us to add nodes at any point in our list), delete/remove (which would allow us to remove nodes from our list) and lookup (which would allow us to search our list for a specific node).
I’ve said this before, and I’m sure I will say it again, but getting better at solving algorithms and understanding data structures really just takes practice. I’ll be writing a separate blog post on the implement of some other LinkedList methods, but before I do, definitely take a chance and try implementing these new methods on your own!
Good luck and happy coding!
