Singly Linked List in JavaScript
Linked List, like arrays, is a linear data structure. It contains head, tail and length properties. As shown below, each element in linked list is a node, which has a value and a reference to next node, or if it’s tail, points to null.
Why do we need linked list if we have arrays?
For data insertion and deletion, arrays can be expensive. Linked list, on the other hand, has dynamic size and makes insertion and deletion so easy. One disadvantage though, unlike arrays, elements in linked list doesn’t have indexes in order, which doesn’t allow random access.
There are different types of linked list, such as, singly linked list, doubly linked list and circular linked list. Since singly linked list is most common, let’s talk about singly linked list in JavaScript.
To have a clear understanding of singly linked list, I’ll implement LinkedList class in JavaScript.
Each node of Linked list will have two attributes: value & next, and linked list will have head, tail and length attribute.
Push
How can we push a new node into the end of our list? Let’s make a push function. First, we need to create a new node using the given value, check if the list has a head (is it empty?) and don’t forget to increment the size of the list.
Pop
With pushing, we need to think about popping, deleting the last element. If there is no node, return undefined, else, loop through the list until we reach the tail, set the next property of the second last node to be null, make the second last to be the tail, don’t forget to decrement the size of the list.
Shift
For deleting the first element, shifting, as usual, check if the list is empty. First, store the current head in a variable, set the head to be the current head’s next, decrement the length.
Unshift
To insert a node at the beginning of the list, check if the list is empty, if not, we set the current head to be the next attribute of the incoming node, increment the size.
Get
Even though linked list doesn’t have indexes, we are still able to find the node by given index. First make sure the given index is greater than zero and smaller or equal to the length of the list. Than we loop through the list until we reach the index.
Set
What if we want to change a node in our list? We find the node with get(), and set the node with given data.
Insert
When we want to insert a new node into the list, first check if the index is greater than 0 and smaller than the length. If index is the length, we just use push(), if the index is 0, we use unshift(). For other indexes, we need to get the node at the index-1, and set the next property of that node to be the new node, and the next property of the new node to be the previous next property, then we increment the length.
Remove
Unlike pop and unshift, remove function will remove the node by given index. As usual, check if the index is valid, if index equals to length-1 or 0, use pop or shift. Otherwise, we get the node at the index-1, set the next property on that node to be the next of the next property, after, we decrement the size.
Reverse
The ultimate reverse question! How do we reverse the list? First, we swap head and tail, declare next and previous, set the previous as null. We loop through the list.
What is the Big O complexity of singly linked list?
With a table, it will be more clear.
With these basic functions, we’ll be able to handle linked list problems.
References:
