In this article, we’re going to create a singly linked list and compare it with an array. While the linked list methods used will closely resemble those of array methods, they will not be identical, so it’s important to pay attention to the differences between the methods for singly linked lists and arrays.

Writing a singly linked list is a frequent technical interview topic and I hope this article helps you prepare for the next technical interviews.

The list of the methods

Here is the complete list of the methods we are going to implement in this article. This list will give you a quicker access to each section when you revisit this page later.

push()
pop()
shift()
unshift()
length/length()
get()
set()
insertAt()
removeAt()
clear()
reverse() – 💡 a popular interview question
sort() – coming soon

What is a Linked List?

A linked list is a linear data structure which is unidirectional meaning it can only be traversed in one direction from head (first node) to tail (last node). The performance of linked list is quite efficient on insertion and deletion at arbitrary positions in the sequence. We will discuss more on how array and linked list are stored differently in memory and how it can affect in the future article.

The linked lists are one of the simplest and most common data structures and they are used to implement other data structures like Queues, Tress and Graphs.

There are different types of linked list but the singly linked list and doubly linked list are the most common ones. In this article, we are going to focus on the singly linked list. In the future article, I will write the doubly linked list so stay tuned 😀

Please note we will use both singly linked list and linked list interchangeably in this article. If it indicates another linked list (e.g., doubly linked list or circular linked list etc), I will specifically use the name of the linked list, otherwise, I will use the name, linked list, same meaning as singly linked list in this article.

The linked list in JavaScript is not available as a built-in data structure (e.g., Arrays and Hash Tables) unlike other programming languages such as C++ and Java. In this article, we will create the singly linked list in JavaScript and compare it with the array methods.

Before we dive into it, let’s take a look at how the singly linked list looks like.

Anatomy of Singly Linked List

The singly linked list is a collection of data and the collection consists of a number of different nodes. A node contains two properties, value and next.

The value property contains the data and the next property contains a pointer to another node or null.

The code for the Node isn’t anything special, it’s just a key-value pair and looks like:

Node {
  value: 'value 1',
  next: null,
}

The singly linked list consists of the nodes and it contains:

head: the first node
tail: the last node
length: the size of the linked list

The example of the above diagram would look like:

SinglyLinkedList {
  head: {
    value: 'value 1',
    next: {
      value: 'value 2',
      next: {
        value: 'value 3',
        next: {
          value: 'value 4',
          next: null,
        }
      }
    }
  },
  tail: {
    value: 'value 4',
    next: null
  },
  length: 4,
}

Based on the anatomy of the singly linked list, let’s implement its methods by comparing its corresponding array method. (Please note that the methods between the linked list and array are not 100% identical, but quite similar. I will give the details of each method of both linked list and array as much as I can throughout the article).

Let’s start with implementing the node.

Node

As we saw above, the node contains two properties, value and next. We will create a class instance for the node which accepts the value as an argument.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

That’s it for node!

To create new node (please note we won’t add new node to the linked list this way and this is just to demonstrate of creating nodes are working),

const newNode = new Node('value 1');
newNode.next = new Node('value 2');
newNode.next.next = new Node('value 3');
newNode.next.next.next = new Node('value 4');

console.log(newNode);

and it will return:

Node {
  value: 'value 1';
  next: {
    value: 'value 2',
    next: {
      value: 'value 3',
      next: {
        value: 'value 4',
        next: null,
      }
    }
  }
}

and here is the screenshot of the output.

As mentioned above, we won’t insert new node in this way and will find more about different methods to handle the data structure with the singly linked list in the following sections.

Now we can create nodes. Let’s implement methods for the linked list data structure beginning with the linked list constructor.

Singly linked list constructor

We are going to create a class for the SinglyLinkList but start with its constructor. The SinglyLinkedList instance will have three properties, head, tail and length as discussed above.

The details of each property are:

head: is a reference to the first node of the linked list and by default, it is null
tail: is a reference to the last node of the linked list and by default, it is null
length: is the size (number of nodes) of the linked list and by default, it is 0

And here is the code for the constructor:

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

Now we are all prepared and ready to build the first method, push().

push()

Array

The array push method adds new elements at the end of the array and it returns the new length of the array.

Here is an example.

const values = ['value 1', 'value 2', 'value 3', 'value 4'];
const numOfValues = values.push('value 5', 'value 6');

// output: 5
console.log(numOfValues);

// output: ['value 1', 'value 2', 'value 3', 'value 4', 'value 5', 'value 6']
console.log(values);

If we wanted to merge two arrays, we can use the spread operator as shown below.

const values = ['value 1', 'value 2', 'value 3', 'value 4'];
const moreValues = ['value 5', 'value 6'];

values.push(...moreValues);

// output: ['value 1', 'value 2', 'value 3', 'value 4', 'value 5', 'value 6']
console.log(values);

Linked List

The push method we are going to implement for the linked list is quite similar to the array push method as it will insert a new node at the end of the linked list. But it will return the linked list data unlike the array push method returns the new length of the array.

Let’s first visualise how it would work.

Walkthrough

We have 4 existing nodes in the list here as an example.

1. Create new node with the value passed to the function. In this case, its value is value 5.

2. Set the next property of the tail pointing to the new node.

3. Set the new node as the tail.

4. Increment the length by one.

5. Return the list.

Edge cases

If there is no head property in the list, we will set the head and tail to the new node.

Implementation

Here is the complete code. We have included the constructor here to show the entire class but from the next method, I will only add the method itself.

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(value) {
    const newNode = new Node(value);

    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.length++;
    return this;
  }
}

First we will create new node (line 9). And we will check if there isn’t any head in the list (line 11). If there is no head, we will set both head and tail to the new node (line 12, 13).

If there is head (meaning there are already nodes existing in the list), we will first set the next of the tail to the new node and then update the tail to the new node (line 15, 16).

Side note: you might ask how adding the newNode to the this.tail.next ends up added to the head value as you can see from the output screenshot below. That’s because in line 12 and 13, we are assigning the same node to both head and tail so they are pointing to the same place in the memory (note: this.tail value on line 13 also can be newNode too). If we are assigning a different node with a different Node instance or Class, this won’t work so we will have to traverse the entire list and add the new node value to the next property of the last node. It will be the same story if we didn’t have the tail property defined too and it will give us O(n) time complexity as we need to traverse the entire list to the end. Please see the the Big O notation for our approach in the following section below.

Finally we will increment the length by one and return the linked list (line 19, 20).

Output

If we run:

const list = new SinglyLinkedList();
list.push('value 1');
list.push('value 2');
list.push('value 3');
list.push('value 4');
list.push('value 5');

it will return:

Big O

Time complexity

The push method for both array and linked list gives us O(1).

For the array, because JS is a dynamic array which allocates more memory spaces at the end so adding new values to the end of the array will be constant. For other programming language with a static array will be O(n) time complexity.

For the linked list, as we discussed above briefly, if we didn’t have the reference to the tail, it will be O(n) time complexity, but with the tail property, we can directly assign the new value to the this.tail.next which gives us O(1) time complexity.

Space complexity

For the space complexity, both array and linked list do not required any increase in size, just adding 1 element for array and 1 node for the linked list, both will be O(1) space complexity.

	Array	Linked List
Time complexity	O(1)	O(1)
Space complexity	O(1)	O(1)

pop()

Array

The array pop() method removes an element from the end of the array and returns the removed one. It will decrement the length of the array by 1.

Here is an example.

const values = ['value 1', 'value 2', 'value 3', 'value 4', 'value 5'];

// output: 'value 5'
console.log(values.pop());

// output: ['value 1', 'value 2', 'value 3', 'value 4']
console.log(values);

// output: 4
console.log(values.length);

Linked List

The pop method for the linked list will work exactly the same as array. It will remove the last node in the list and return the node removed. The length of the linked list will be decremented by 1.

For the pop() method, we need to track two variables, previous node and current node. The previous node will be always one node behind the current node because later when the current node has no next node, we will set the previous node as the new tail. Let’s visualise how it works. We will start with 3 existing nodes.

1. Set the previous node and current node. The current node is always one node ahead than the previous node.

2. Loop through the node and move the previous node and current node to the next node.

3. Get out of the loop when the next node of the current node is null.

4. Set the tail to the previous node.

5. Set the next of the new tail null.

6. Decrement the length by one.

7. Return the current node.

Edge cases

If there is no node, we will do nothing and just return undefined (note: the array also returns undefined).
If there is one existing node, we will set both head and tail to null and return the previous node. Because we need to return it early and still need to decrement the length, step #6 above actually is happening before the loop (see the code below).

Implementation

Let’s take a look at the complete code first and go through line by line.

pop() {
  if (!this.head) return undefined;

  let previousNode = this.head;
  let currentNode = this.head.next;

  this.length--;
  
  if (!this.head.next) {
    this.head = null;
    this.tail = null;

    return previousNode;
  }

  while(currentNode.next) {
    previousNode = currentNode;
    currentNode = currentNode.next;
  }

  this.tail = previousNode;
  this.tail.next = null;

  return currentNode;
}

First we will cover the two edge cases. When there is no node in the list, we will return undefined (line 1). If there is at least one node, we will set the previousNode and currentNode (line 4, 5) and decrement the length by one first (line 7) because we need to cover the second edge case right away.

For the second edge case, when there is only one node (line 9), we will set the head and tail to null and then return the previousNode which will be this.head.

If there are more than 1 node, we will loop through the list until the end of the list which has no next (line 16), we will move the pointers of the previousNode and currentNode. At the end of the iteration, the value of the previousNode will be one node before the last node, and the currentNode will be the last node. (line 17, 18).

We will set the tail to previousNode and set the next of the new tail to null (line 21, 22). Again, you might ask how the value of head gets also updated when we change the tail to previousNode. That’s because when we add new node, we will use the push() method we wrote above, and as explained, the head and tail are sharing the same last node.

Finally we will return the currentNode which has technically removed from the list by now.

Output

const list = new SinglyLinkedList();
list.push('value 1');
list.push('value 2');
list.push('value 3');

list.pop();

It will return:

and the list will show as:

Big O

Time complexity

The time complexity of the array pop() method is constant because we just need to remove the last element of the array and free up the last memory slot.

The linked list however will be a linear time operation because we need to traverse the entire list to get both last node and one before the last node.

Space complexity

As we are just remove one element or one node, it will be a constant space complexity.

	Array	Linked List
Time complexity	O(1)	O(n)
Space complexity	O(1)	O(1)

shift()

Array

The shift method in array removes the first element and returns the removed one as opposed to the pop method. The length of the array will get decremented by 1.

Here is an example.

const values = ['value 1', 'value 2', 'value 3', 'value 4', 'value 5'];

// output: 'value 1'
console.log(values.shift());

// output: ['value 2', 'value 3', 'value 4', 'value 5']
console.log(values);

// output: 4
console.log(values.length);

Linked List

The shift method in linked list will work same as the array shift method. It will remove the first node which is the head node and return the removed node. The length of the list will be decremented by 1.

Unlike the pop method in the linked list which had to track two variables to update the tail node, the shift implementation will just need to find the head node, and assign it to a variable to return later and change it to the next node of the head. Let’s visualise it. We will begin with 3 nodes.

1. Set the current head to currentHead variable.

2. Set the head to the second node which is the next node of the head.

3. Decrement the length by 1.

4. Return the currentHead.

Edge cases

If there is no node, we will do nothing and just return undefined (note: the array also returns undefined).
After shifting, if no node is left in the list, we will set the tail to null.

Implementation

Let’s look at the complete code.

shift(value) {
  if (!this.head) return undefined;

  const currentHead = this.head;
  this.head = this.head.next;

  this.length--;
  
  if (this.length === 0) {
    this.tail = null;
  }

  return currentHead;
}

First, we will cover the first edge case by returning undefined if there is no node in the list (line 2).

If there is any node, we will assign the current head to the variable, currentHead (line 4) so that we can store this value before we override the head value to another and return it. Once we store the current head to the variable, we will set the head to the second node which is the next node of the head (line 5).

And we will decrement the length by 1 (line 7).

There is another edge case that if there is no node left in the list, we will make the tail to null (line 10) otherwise the tail will still have the last node.

And finally we will return the currentHead (line 13).

Output

const list = new SinglyLinkedList();
list.push('value 1');
list.push('value 2');
list.push('value 3');

list.shift();

It will return:

and the list will show as:

Big O

Time complexity

The shift method in array requires to shift the entire array by reindexing each element in the memory after removing the first element so it runs in linear time.

The linked list requires only changing the pointer of the head (and tail for the edge case) so it doesn’t have to traverse the entire list and it gives us the constant runtime.

Space complexity

As we are just remove one element or one node, it will be a constant space complexity.

	Array	Linked List
Time complexity	O(n)	O(1)
Space complexity	O(1)	O(1)

unshift()

Array

Personally I think the method name, unshift, doesn’t really represent what it does but anyway the unshift() method adds one or more elements to the beginning of the array. It returns the new length of the array.

const values = ['value 1', 'value 2', 'value 3', 'value 4'];
const numOfValues = values.unshift('value 5', 'value 6');

// output: 5
console.log(numOfValues);

// output: ['value 5', 'value 6', 'value 1', 'value 2', 'value 3', 'value 4']
console.log(values);

Linked List

The unshift method in the linked list will be quite similar to the array unshift. The new node will be added to the beginning of the list. But unlike the array, it will return the linked list.

Let’s visualise it. We have 4 nodes here.

1. Create new node with the value passed in; value5 as an example.

2. Set the next value of the new node to the current head.

3. Set the head to the new node.

4. Increment the length by one.

5. Return the list.

Edge cases

If there is no head property in the list, we will set the head and tail to the new node.

Implementation

Here is the complete code for the method.

unshift(value) {
  const newNode = new Node(value);

  if (!this.head) {
    this.head = newNode;
    this.tail = this.head;
  } else {
    newNode.next = this.head;
    this.head = newNode;
  }

  this.length++;
  
  return this;
}

First we will create new node (line 2). And we will check if there isn’t any head in the list (line 4). If there is no head, we will set both head and tail to the new node (line 5, 6).

If there is head (meaning there are already nodes existing in the list), we will first set the next of the new node to the head and then update the head to the new node (line 8, 9).

Finally we will increment the length by one and return the linked list (line 12, 14).

Output

If we run:

const list = new SinglyLinkedList();
list.unshift('value 1');
list.unshift('value 2');
list.unshift('value 3');
list.unshift('value 4');
list.unshift('value 5');

it will return:

Big O

Time complexity

As mentioned in the push method, we will get into more details of the memory allocation for array and linked list in the future article, but the dynamic array in JS won’t really help here because the entire array needs to shift to the available next memory slot in order to add new element at the first index so the time complexity of unshift for array will be O(n) because we need to shift every element by a memory space.

The time complexity for the linked list will be constant as we can directly assign the new value and link it with head.

Space complexity

Same as pop, for the space complexity, both array and linked list do not required any increase in size, both will be O(1) space complexity.

	Array	Linked List
Time complexity	O(n)	O(1)
Space complexity	O(1)	O(1)

length or length()

Array

In array, to check the length of the array, we use the length property (note it’s not a method).

const values = ['value 1', 'value 2', 'value 3', 'value 4'];

// output: 4
values.length;

Linked List

In the linked list, we are already exposing the length property.

const list = new SinglyLinkedList();
list.push('value 1');
list.push('value 2');
list.push('value 3');
list.push('value 4');

// output: 4
list.length;

But let’s say we don’t have the length property in our linked list instance so we need to add new method, length(), to our linked list.

Implementation

We will go through the entire list and return the counter at the end. Let’s see the complete code first.

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    // this.length = 0;
  }

  // other methods go here

  length() {
    let counter = 0;
    let node = this.head;

    while(node) {
      counter++;
      node = node.next;
    }

    return counter;
  }
}

First, we will initialise the counter value to zero (line 13) and assign the node to the first node (this.head) (line 14). We will iterate the node until its value becomes null (line 16) and during the iteration, we will increment the counter value and update the node to the next node which will finally be null when it reaches to the last node. Then we will return the counter.

Let’s add some nodes and get the length of the list and the output will be 4.

const list = new SinglyLinkedList();
list.push('value 1');
list.push('value 2');
list.push('value 3');
list.push('value 4');

// output: 4
list.length();

If we wanted to call length() method more like a property, let’s make the length() method as a getter.

class SinglyLinkedList {
  constructor() {
    ...
  }

  push(value) {
    ...
  }

  get length() {
    ...
  }
}

And now we can call the getter like:

list.length;

Big O

Time complexity

The length property of both array and linked list is constant time complexity as looking up the property is (almost) instant in JS. For the length method in linked list will be a linear time because it has to traverse the entire list to finally get the total number of nodes.

Space complexity

For the space complexity, none of them increases in size so they are all O(1).

	Array	Linked List (length property)	Linked List (length method)
Time complexity	O(1)	O(1)	O(n)
Space complexity	O(1)	O(1)	O(1)

get()

Array

In array, the at() method is used to find a value in the index of given value and it takes an integer value, either positive or negative. The negative given value will count back from the last element.

The at() method works the same as the bracket notation like below:

const arr = ['value 1', 'value 2', 'value 3', 'value 4', 'value 5'];

// output: 'value 1'
arr[0];

// output: 'value 1'
arr.at(0);

But the bracket notation doesn’t work with the negative value whereas the at() method will return the value counting back from the last array element.

const arr = ['value 1', 'value 2', 'value 3', 'value 4', 'value 5'];

// output: undefined
arr[-1];

// output: 'value 5'
arr.at(-1);

Linked List

We are going to call it, get() instead of at() because we will be implementing the set() method in the following section and get instead of at matches better with set.

The get() method in the linked list will do the same as the array at() method. It will accept both positive and negative integer and return the value at the position of the given integer. Like array, the negative integer will count back from the last node in the list.

Edge cases

In the following cases, we will return undefined:

the given value is not the type of number
the positive formatted value of the given number is still smaller than zero. For example, if the length of the list is 3, but the given number is -5, we will return undefined
the given number is bigger than or equal to the length of the list

Implementation

Let’s see the complete code.

get(index) {
  if (index < 0) index = this.length + index;

  if (typeof index !== 'number' || index < 0 || index >= this.length) return undefined;

  let counter = 0;
  let currentNode = this.head;

  while(currentNode) {
    if (counter === index) {
      return currentNode;
    }

    counter++;
    currentNode = currentNode.next;
  }

  return undefined;
}

First we need to take care of the case when the given number is negative. If it’s negative, we will convert the index value to the positive. For example, if the length of the list is 5 and the given number is -2, we want to convert it to 3 (note the index starts from 0 as array) so it’s 5 + (-2) = 3 (line 2).

And we need to check the edge cases and if it falls in the edge cases, we will return undefined (line 4).

Now we are ready to find the value at the position of the given number. Let’s define and assign 0 to counter (line 6). We are going to use the counter value to find the node at the position in the loop (line 10, 11). Also let’s assign the head node to the currentNode (line 7). We are going to use currentNode to make the iteration (line 9).

Let’s iterate (line 9) until the currentNode has null by reassigning the next value to it (line 15). At the end when it reaches to the last node, the currentNode will be null and we will get out of the loop (line 9).

Each iteration, we will increment the counter (line 14) and check if the counter matches with the index given (line 10). When they match, we will return the currentNode (line 11).

The last return statement (line 18) won’t really necessary but just for the safe-guard, we will return undefined at the end of the function call.

Output

If we run:

const list = new SinglyLinkedList();
list.push('value 1');
list.push('value 2');
list.push('value 3');
list.push('value 4');
list.push('value 5');

list.at(3);
list.at(-2);

Both list.at(3) and list.at(-2) will return:

Big O

Time complexity

Accessing the array at an index is instant, O(1), because it knows where the index in array located in the memory.

Unlike array, the get() method in linked list has to traverse the entire list to get the number, in our case, counter, so the time complexity is O(i) where i is index.

Space complexity

Both array and linked list get() method don’t use any extra space so it’s constant space complexity.

	Array	Linked List
Time complexity	O(1)	O(i)
Space complexity	O(1)	O(1)

set()

Array

The array doesn’t have a method to change/set the value of an element at the given index. To change the value, we specify the index with the bracket notation and assign new value. Please note it won’t work with the array at() method.

const arr = ['value 1', 'value 2', 'value 3', 'value 4', 'value 5'];

// output of array: ['value 23', 'value 2', 'value 3', 'value 4', 'value 5'];
arr[0] = 'value 23';

// Uncaught ReferenceError: Invalid left-hand side in assignment
arr.at(0) = 'value 23';

Linked List

The set() method in the linked list will take in two arguments, index and value and change the value of the node positioned at index.

To find the node positioned at index, we will make a use of the get() method we implemented above.

For the edge cases, they will be taken care in the get() method so there won’t be any edge cases specific to set() method.

Implementation

Let’s see the complete code.

set(index, value) {
  const node = this.get(index);

  if (node) {
    node.value = value;

    return node;
  }

  return undefined;
}

We will receive index and value (line 1) and find the node using the get() method (line 2).

If we can find the node, we will set the value of the node to the given value (line 5) and return the node with the new value (line 7).

If the node doesn’t exist, we will return undefined (line 10).

Output

Let’s run:

const list = new SinglyLinkedList();
list.push('value 1');
list.push('value 2');
list.push('value 3');
list.push('value 4');
list.push('value 5');

list.set(3, 'new value');
list.set(-2, 'new value');

Both list.set(3) and list.set(-2) will update the value of the 4th node, value 4.

Big O

Time complexity

Same as get() method, accessing the array at an index and update the value will be a constant runtime for array. For the linked list, it needs to traverse the entire list, it will be O(i).

Space complexity

Both array and linked list are not increasing in size, both will be O(1) for the space complexity.

	Array	Linked List
Time complexity	O(1)	O(i)
Space complexity	O(1)	O(1)

insertAt()

Array

If we wanted to insert new value at a specific index in array, we need to use splice() method. The splice method takes in 3 arguments:

start: the index at which we wanted to change. It accepts both positive and negative number and if if’s negative number, it will start from the end of the array
deleteCount (optional): the number of elements we wanted to remove from the start
item(s) (optional): the element(s) we wanted to add from start

The splice method returns an array with the deleted elements. If no elements are removed, an empty array is returned.

Let’s see the examples.

const arr = ['value 1', 'value 2', 'value 3'];
  
  // result: ['value 1', 'value 23', 'value 2', 'value 3']
  // output: []
  arr.splice(1, 0, 'value 23');
  
  // result: ['value 100', 'value 101', 'value 1', 'value 23', 'value 2', 'value 3']
  // output: []
  arr.splice(0, 0, 'value 100', 'value 101');

For the first example, we start from 1 index, delete 0 element and add value 23.

For the second example, we start from 0 index, delete 0 element and add two values, value 100 and value 101.

Both return an empty array because we are not deleting any elements in the array.

Linked List

For the linked list, unlike array, we are going to split it into two methods, insertAt() and removeAt(). We are going to implement the insertAt method in this section and the removeAt method in the following section.

The insertAt method in the linked list will take in two arguments, index and value and will insert the new node with the given value at the given index. For the index value, it accepts both positive and negative value. If it’s a negative value, we will count back from the end of the list.

Once inserted, it will return the linked list.

Let’s visualise it. We are going to start with 3 nodes in the list and trying to add new node with the value, value 4 at the 2nd index (note: the index starts from 0).

1. Create newNode with the value, value 4.

2. Define previousNode and assign the node at the one index before the given index which will be 1st. Also we will define tempNode and assign the next node of the previousNode to it.

3. Assign the newNode to the next node of previousNode.

4. Assign tempNode to the next node of the newNode.

So we have inserted the new node and it’s now located at 2nd position in the list.

5. Increment the length by 1.

6. Return the linked list.

Edge cases

the edge cases of get() method will return undefined
if the given index is 0, we will make a use of unshift() method
if the given index is same as length, we will make a use of push() method

Implementation

Here is the complete code.

insertAt(index, value) {
  if (index < 0) index = this.length + index;
  if (typeof index !== 'number' || index < 0 || index > this.length) return undefined;
  if (index === 0) return this.unshift(value);
  if (index === this.length) return this.push(value);

  const newNode = new Node(value);

  const previousNode = this.get(index - 1);
  const tempNode = previousNode.next;
  previousNode.next = newNode;
  newNode.next = tempNode;

  this.length++;

  return this;
}

First we will convert the negative index to positive index (line 2) and check the edge cases to see if it should return undefined (line 3).

If the index is 0, we will use the unshift() method to insert the new node and return it (line 4).
If the index is same as the size of the list, we will use the push() method and return it (line 5).
If none of edge cases are met, we will follow the remaining implementation.

First, we will create new node (line 7).

And to update the next node in order to make it point to the right node, we first need to define and assign the previousNode and tempNode (line 9, 10). Once we stored those nodes, we can now change the next node, the next node of previousNode to newNode and the next node of newNode to tempNoe.

Once all done, we increment the length by one (line 14) and return the linked list (line 16).

Output

const list = new SinglyLinkedList();
list.insertAt(0, 'value 0');
list.insertAt(0, 'value 1');
list.insertAt(0, 'value 2');
list.insertAt(3, 'value 3');
list.insertAt(2, 'new value 1');
list.insertAt(-3, 'new value 2');

The output will be:

Big O

Time complexity

The time complexity of the splice array method is O(n) because in the worst case scenario, when we splice at the beginning of the array, it has to traverse the entire array to update all the following indices.

For the linked list, adding new node to the beginning or end will be a constant runtime because we have a reference to both head and tail so we could just directly add the node. For the scenario of adding new node in the middle will be O(i) because it has to traverse the list to find the index/position of the node.

Space complexity

As there is no values increasing in size, the space complexity for both array and linked list will be O(1).

	Array	Linked List (insert at the beginning)	Linked List (insert in the middle)	Linked List (insert at the end)
Time complexity	O(n)	O(1)	O(i)	O(1)
Space complexity	O(1)	O(1)	O(1)	O(1)

removeAt()

Array

To remove an element(s), we use splice method too, but this time, we specify the deleteCount value and don’t provide any elements.

Let’s see some examples.

const arr = ['value 1', 'value 2', 'value 3', 'value 4', 'value 5'];

// result: ['value 1', 'value 3', 'value 4', 'value 5']
// output: ['value 2']
arr.splice(1, 1);

// result: ['value 1', 'value 2', 'value 6', 'value 5']
// output: ['value 3', 'value 4']
arr.splice(2, 2, 'value 6');

// result: ['value 1', 'value 2', 'value 3', 'value 5']
// output: ['value 4']
arr.splice(-2, 1);

// result: ['value 1', 'value 2']
// output: ['value 3', 'value 4', 'value 5']
arr.aplice(2);

For the first example, we start at index 1 and remove 1 item. As we didn’t provide the third argument, no new items will be added.

The second example start at index 2 and remove 2 items, and add value 6 where the items are removed at.

The third example starts from the second last -2 which is index 3 and remove 1 item.

And the last example shows removing all the following items from index 2.

Linked List

Unlike the array splice method, we will only receive the index value and delete only one item at a time so won’t receive the deleteCount. It will return the removed node.

The implementation is quite similar to insertAt() method but a bit different.

Let’s visualise it. We are going to start with 4 nodes in the list and trying to remove the 2nd index node.

1. Define the previousNode at the one index before the given index which will be the 1st node in the list.

2. Define the removedNode to the next node of the previousNode which will be 2nd node we are going to remove.

3. Now to remove the 2nd index node, set the next node of the previous node to the next node of the removed node which will be the tail node.

Decrement the length by 1.
Return the removedNode.

Edge cases

the edge cases of get() method will return undefined
if the given index is 0, we will make use of shift() method
if the given index is same as length, we will make use of pop() method

Implementation

Here is the complete code for the removeAt() method.

removeAt(index) {
  if (index < 0) index = this.length + index;
  if (typeof index !== 'number' || index < 0 || index > this.length) return undefined;
  if (index === 0) return this.shift();
  if (index === this.length - 1) return this.pop();

  const previousNode = this.get(index - 1);
  const removedNode = previousNode.next;
  previousNode.next = removedNode.next;

  this.length--;

  return removedNode;
}

Same as insertAt() method, we will convert the negative index value to the positive value (line 2). And then we will check if the given index is valid. If it’s not valid, we will return undefined (line 3).

If the given index is to remove the first item, we will make a use of shift() method we implemented previously (line 4). Likewise, if the given index is the last item, we will use the pop() method we implemented already (line 5).

To remove an item in the middle somewhere, we will first store the previous node of the given index (line 7) and the node which is going to be removed (line 8). And then we will point the next node of the previous node to the next node of the removed node (line 9) and this will remove the removedNode from the list.

We will decrement the length by 1 (line 11) and then return the removedNode (line 13).

Output

const list = new SinglyLinkedList();
list.insertAt(0, 'value 0');
list.insertAt(1, 'value 1');
list.insertAt(2, 'value 2');
list.insertAt(3, 'value 3');

list.removeAt(2);

And the output of console.log(list) will be:

Big O

Time complexity

Please check the time complexity of the splice array method in the insertAt() section above.

For the linked list, removing the first item will be constant runtime because we have reference to head so we can directly access to it. For both removing items in the middle or at the end will be O(i) because it has to traverse the list to find the index/position of the node.

Space complexity

The space complexity for both array and linked list is constant because there is no value increasing in size.

	Array	Linked List (remove at the beginning)	Linked List (remove in the middle)	Linked List (remove at the end)
Time complexity	O(n)	O(1)	O(i)	O(i)
Space complexity	O(1)	O(1)	O(1)	O(1)

clear()

Array

To empty an array, there are several ways we can do, but making the length of the array 0 would be the simplest and most performant way.

const arr = ['value 1', 'value 2', 'value 3', 'value 4', 'value 5'];

arr.length = 0;

Linked List

In the linked list, emptying the list will be quite similar to how the array does. Let’s see the code.

Implementation

Here is the clear() method.

clear() {
  this.head = null;
  this.tail = null;
  this.length = 0;
}

So basically we set the head and tail to null and length to 0. As the previously existed list items are not getting removed but rather we are setting the reference pointers to null for head and tail, the previous list items might still exist somewhere in the memory until they are garbage-collected. However, in the linked list point of view, they are gone and the list is empty.

const list = new SinglyLinkedList();
list.insertAt(0, 'value 0');
list.insertAt(1, 'value 1');
list.insertAt(2, 'value 2');
list.insertAt(3, 'value 3');

list.clear();

And the output of console.log(list) will be:

Big O

Time complexity

Both array and linked list will be the constant runtime to empty the items because we are instantly updating the properties.

Space complexity

No value is increasing in size so it will be O(1) for the space complexity.

	Array	Linked List
Time complexity	O(1)	O(1)
Space complexity	O(1)	O(1)

reverse()

⭐️ This is a quite popular interview question so it’s a great chance to closer look at how we can implement it.

Array

To reverse the array, we use reverse() method and it returns the reference to the original array but in the reversed order.

Let’s see an example.

const arr = ['value 1', 'value 2', 'value 3', 'value 4'];

const reversed = arr.reverse();

// output: ['value 4', 'value 3', 'value 2', 'value 1']
console.log(reversed);

// output: ['value 4', 'value 3', 'value 2', 'value 1']
console.log(arr);

Please note the reverse() method will change the original array as you can see from console.log(arr).

Linked List

The reverse() method will do exactly the same as the array method; reversing the list.

It will return the linked list.

Let’s visualise it. We are going to start with 4 nodes in the linked list.

1. Define (the order is important, otherwise we will lose the track of the head):

1-1. previousNode as nul
1-2. currentNode as head

1-3. head to tail
1-4. tail to currentNode

2. We are going to loop through until the currentNode is null.

1st iteration

Define nextNode as the next node of the currentNode. And then set the next node of the currentNode to previousNode which is null at the moment.

And then set the previousNode to currentNode and currentNode to nextNode.

It might be a bit confusing but it’s important to understand this 1st iteration so take your time to fully grasp what’s going on here 😀

2nd iteration

Same as first iteration. After updating nextNode and the next node of the currentNode, it will look like below.

And then update the previousNode and currentNode.

I think you know now where we are getting at.

3rd iteration

At the end of the 3rd iteration, it will look like below.

4th iteration

At the end of the 4th iteration, it will look like below.

Now currentNode is null, we will end the loop.

3. Finally return the list.

Implementation

Here is the complete code for the reverse() method.

reverse() {
  let previousNode = null;
  let currentNode = this.head;

  this.head = this.tail;
  this.tail = currentNode;

  while (currentNode !== null) {
    const nextNode = currentNode.next;

    currentNode.next = previousNode;
    previousNode = currentNode;
    currentNode = nextNode;
  }

  return this;
}

Let’s take a closer look at each line.

Initially we set the previousNode to null and currentNode to this.head as we saw from the walkthrough. (line 2, 3)

Next we are swapping the references of this.head and this.tail (line 5, 6). This operation is crucial because, in the reversed list, the original head becomes the new tail, and the original tail becomes the new head.

The algorithm enters a while loop, which continues as long as currentNode is not null (line 8). This loop traverses the list starting from the original head (now the new tail). Inside the loop, nextNode is temporarily stored as currentNode.next (line 9). This variable is essential for moving through the list without losing the reference to the subsequent nodes after reassigning currentNode.next.

Within each iteration of the loop, the next pointer of currentNode is redirected to previousNode (line 11). This step is where the actual reversal happens. Instead of currentNode pointing to its original next node, it now points backward to what was its previous node.

The previousNode and currentNode are then updated for the next iteration (line 12, 13). previousNode becomes currentNode, effectively moving one step forward in the list, and currentNode moves to nextNode, advancing to the next node in the original sequence. This process repeats until currentNode becomes null, indicating the end of the list has been reached. By this time, all the next pointers have been reversed.

Finally the method returns this, the modified list, now fully reversed. The original head is the new tail (with next pointing to null), and the original tail is the new head (now pointing towards what was originally its predecessor).

Output

Let’s first add some nodes using push().

const list = new SinglyLinkedList();
list.push('value 1');
list.push('value 2');
list.push('value 3');
list.push('value 4');
list.push('value 5');

So it will look like:

Let’s reverse it.

list.reverse()

And the LinkedList is now reversed.

In conclusion

This article took you through everything about Singly Linked Lists, from creating a node to exploring methods corresponding to array methods. We also dove into the time and space complexity for each method. It’s important to understand how these methods work, especially the reverse() method, since it often comes up in the technical interviews. Make sure to practice a lot and get familiar with their efficiency.

I hope this article helped you grasp Singly Linked Lists. Coming up, I’ll be discussing Doubly Linked Lists, which are essential for cracking some typical data structure problems like the LRU cache. So, keep an eye out for that, and also let’s connect on LinkedIn.