Mastering Singly Linked List: A Step-by-Step Tutorial

Photo by Markus Spiske on Unsplash

This time I want to walk you through my code, implementing a singly linked list. Linked list is a linear data structure like array, queue, tree, etc. It is a node-based data structure with value and a pointer to the next/previous data.

The advantage using this data structure is we will have O(1) time complexity in adding/removing value in both head/tails, very useful in certain use case. But for adding/removing value at specific index, we still have O(n) time complexity since we have to walk through the list until we find the desired value.

OK! Let’s get to the code!

First, we need to create a class called Node. This will be the base class for every node created. The constructor within the class will define the initial value passed through the parameter.

Now we create the class for linked list. Because we don’t want any variable of the class can be accessible from outside of the linkedList class, we use # prefix in variable declaration to make it private. Every time we access the variable also need to use prefix #. There we define size to keep track of list size and current head of the list.

Now we create length method which is simply return list size.

Now we add append method, which add a new item to the end of the list. First, we add list size by 1 (don’t forget it), then we initiate the new node by calling the class node with valparam that append method has. After that, we check if the head is null, which mean the list is empty, then we only need to assign the head to the new node.

Otherwise, we create a new head reference curr so we can walk through it, then loop as long as the next is not null, because if it’s null it means we are at the end of the list, then we have curr.next = node to assign the new node to the end of the list

Now we create another method prepend to add a new item to beginning of the list. First, of course we add the size by 1, create new node, and create a ref to the head in curr . Remember that every new Node have val and next key, now we need to link the next key of new node to current head and update the head with new node.

Now to insert at specific index, we add insertAt method. First, we check is the index bigger than current size, if it’s bigger, then we throw error since it’s impossible to do. Then we check if the index is 0, which mean we can simply call prepend method because essentially it’s the same operation. The reason count variable initialize with value 1 is because we already handle the case where index is 0, so we start at 1. Consider this case, where we want to insert 4 into index 1. (expected result: [1, 4, 2, 3])

I always have this simple illustration to imagine how to update the pointers

If the index is more than 0, we loop through the list, and break when index is equal to count variable. Once we break the loop:

• update 4’s next to 1’s next (which is point to 2) (node.next = curr.next)
• update 1’s next to 4 (curr.next = node)
• increase list size by 1 (this.#size += 1)

Now we have removeAt method. First is the same as insertAt where we check the index first is it more than the size or not. Then, if index is equal to 0, we updated current head with its next (this.#head = this.#head.next) and reduce its size. Else we loop through the list, if its already at specific index (which mean we are out of the loop) update current next with its next (curr.next = curr.next.next) and reduce its size.

Now to get value at specific index, we add get method. It's simply walk through the list until it reaches a given index and return its value.

This method is optional, but if we want to get the whole list, we simply walk through the list and save each node value to temp variable and return it.

This is how you could implement a linked list, hope it useful for someone out there trying to learn it.

Full working code: linked-list.js (github.com)