What is a linked list? A singly-linked list is a data structure represented by a collection of nodes that are connected to one another through a “next” pointer. They contain the following properties:
- head: The first node in the linked list.
- tail: The last node in a linked list.
- length: the total amount of nodes in the list.
What are nodes? Nodes are what makeup a linked list. Each node is connected to the other by a unidirectional connection. A node has the following properties:
- next: The next node in the list. If the node is the last node in the list, this value is null.
Linked lists are very similar to arrays. They represent a contiguous collection of data where order matters. They do have their differences, however.
Unlike arrays, lists are not indexed. This means random access by a certain index is not allowed. It also means that adding and removing data from the front of a list is cheap. Normally when dealing with arrays, the entire collection would have to be reindexed if you unshifted an element to the front of the collection. Therefore, adding something to the front of an array would always be done in linear time. Linked lists can handle the addition of data at the beginning of the collection in constant time. The same truth can be held when deleting an element from the front of a collection.
So let’s start implementing a singly linked list!
Here we create a Node class (or structure). We are giving our constructor function a value (some integer, string or object) and a next value. The next value gets set to default to begin with as a Node can be independent. It does not necessarily need to exist within a linked list.
Next we setup our list constructor.
As stated before, we are giving this a tail, head and length property. The head and tail get defaulted to null because the list is empty upon creation. The length gets set to zero for the same reason.
Now that we have the container (the list) and the nodes all setup, let’s start implementing methods we can use to add and remove items to the list.
Because we are writing this code within a class, we are able to define the following methods as instance methods.
Firstly, we will take a look at pushing a value on to the end of the list.
The push/1 method has one parameter: the value to be added to the end of the list.
It first creates a new node using the value provided by the original argument. It then checks to see if any other nodes already exist in the list. If there are none, it makes the newly created node both the head and the tail. This makes sense as there is only one element in the list. As a result, both the first and last element would be same.
If an element already does exist in the list, it will first make the next pointer of the tail the newly created node. It will then make the tail value the newly created node. Awesome! After it passes through this logic loop, it will increment the length property of the list by one, and then return this.
What is this you might be wondering? In this case (hah), and in every other method moving forward, this refers to the instance of the list class we have created. We return the newly updated list at the end of the function.
Next lets implement a pop method!
Much like our push/1 method, we are first checking to see if the list is empty. If the list is empty, there will be no element returned by the pop method and therefore we return undefined.
The only way to get to the tail of a list is iterating through the entire collection. Because there are no indices, we cannot simply say list[-1]. So we start out by setting a variable (current) equal to the head value.
We then set another variable (newTail) equal to the same value. Next we enter a while loop. The while loop states that as long as the next property of a node returns a truthy value, set newTail equal to the current node we are on, and set the new current node to newTail’s next value. We are doing this because in order to fully remove the last element of a list we need to remove its connection to the second to last node, not just remove it from the list entirely.
Once we are done iterating through the entire collection, we set the tail equal to the newTail value (the second to last element in the collection) and then set newTail’s next property to null. This effectively severs the connection between the second to last and last element in the collection. We then decrement the length of the collection.
Because this might be the only element left in the collection, we must take into consideration what happens when we remove that item from the collection. We check the length to see if it has been decremented down to the default value of 0 and if that check succeeds we set the tail and head back to the default values of null. We then return current, which is still holding the value of the last removed node. We then are able to manipulate that data point in any way we deem necessary.
As you might have noticed, lists take a linear time to remove an element from the end of a collection. Take this into consideration when contemplating between using an array or a list for your projects. If you are going to constantly be removing only the last element in a collection, it might be wiser to utilize an array as opposed to a list.
Now we will focus on adding and removing elements to the front of a collection.
First let’s talk about shift/0.
We make a check to see if any elements exist in the list. If we can’t find any we return undefined as there are no values to remove from the front of a list.
Shift is where lists shine in comparison to arrays. We are able to remove items from the beginning of a collection in constant time as opposed to linear time. We want to keep track of the current head value so we set that equal to the appropriately named currentHead variable. We then set the list’s head property to that of currentHead’s next property (i.e. the second item in the collection).
Next, we decrement the length by one and make the same conditional check for an empty list that we made for pop/0.
Finally, we return the currentHead variable which holds the item we removed from list. Much more simple than pop!
Unshifting is just as simple as shifting!
Note: I am no longer able to fit the entire class into a single screenshot so it is implied that any new methods talked about are being added to the end of the class.
Adding an element to the beginning of a list is just as easy as removing one. We create a new Node instance using the value provided to us by the arguments given.
Next, we check to make sure the list isn’t empty. If it is, we set both the head and tail value of the list to the newly created node.
If it isn’t empty, we make our newly created node’s next property our list’s current head, and then update the head property to be our new node. We increment the length of the list by one and return the newly updated list.
This is where I will leave off for now. I hope to create a part two about updating, inserting and even reversing elements in linked list!