# Linked List

by [ kirupa](https://www.kirupa.com/me/index.htm) | filed under [Data Structures and Algorithms](https://www.kirupa.com/data_structures_algorithms/index.htm)

Linked lists are pretty sweet. They provide an elegant solution for dealing with large amounts of data that is constantly changing, and they have some tricks up their sleeve for doing all of this dealing quickly and efficiently. In this article, we'll explore the ins and outs of linked lists such as their basic structure, performance characteristics, code implementation, and more! It's going to be a hoot.

Onwards!

## Meet the Linked List

Linked lists, just like arrays, are all about helping us store a collection of data. Below we have an example of a linked list we are using to store the letters A through E:

![](https://www.kirupa.com/data_structures_algorithms/images/linked_list_intro_200.png)

sThe way linked lists work is by relying on individual nodes that are connected to each other. Each node is responsible for two things:

1. Whatever data that it is storing, such as a letter
1. A next pointer (aka reference) that points to the next node in the list

It goes without saying that the node is sort of a big deal. We can zoom in on a node and visualize it as follows:

![](https://www.kirupa.com/data_structures_algorithms/images/node_linked_list_200.png)

The abbreviated biography of a linked list is this: when we take a bunch of data, match them with nodes, and connect the nodes together via the next pointer, we have a linked list. How does a linked list become a linked list? How does it help us work with data? Let’s walk through some more details and answer these questions!

### Finding a Value

We have a linked list with a bunch of data, and we want to find something. This will be one of the most common operations we’ll perform. The way we do this is by starting with the *first* node (aka the ***head*** node) and traversing through each node as referenced by the next pointer:

![](https://www.kirupa.com/data_structures_algorithms/images/first_last_node_200.png)

We keep jumping from node to node until we either:

1. Find the node whose value we are looking for
1. Reach the last node (aka ***tail*** node) that marks the end of our list and we have no where to go

If this sounds a whole lot like a [linear search](https://www.kirupa.com/data_structures_algorithms/linear_search.htm), you would be correct. It totally is...and all the good and bad performance characteristics that it implies.

### Adding Nodes

Now, let’s look at how to add nodes to our linked list. The whole idea of adding nodes is less about ***adding*** and more about ***creating*** a new node and ***updating*** a few next pointers. We’ll see this play out as we look at a handful of examples. Let’s say that we want to add a node F at the end:

![](https://www.kirupa.com/data_structures_algorithms/images/adding_node_example_200.png)

What we need to do is update the next pointer for our *tail* or *last* E node to the new node F we are adding:

![](https://www.kirupa.com/data_structures_algorithms/images/node_f_added_200.png)

It doesn’t matter where in our linked list we are adding our new node. The behavior is mostly the same. Let’s say that we want to add a new node Q **between** our existing nodes of C and D:

![](https://www.kirupa.com/data_structures_algorithms/images/adding_node_middle_200.png)

To make this work, the steps we need to take are:

1. Replace the next pointer on C to point to Q
1. Replace the next pointer on Q to point to D

This will result in the following arrangement, which is exactly what we wanted:

![](https://www.kirupa.com/data_structures_algorithms/images/middle_node_added_200.png)

An important detail to keep in mind is that it doesn’t matter where in our linked list we are adding our node. Our linked list’s primary job is to ensure the next pointers are updated to account for the newly added node. While this sounds complicated, this is a small amount of work. If we are adding a node to the beginning or end of our linked list, we make only one pointer-related update. If we are adding a node anywhere else but the beginning or end of our linked list, we make two pointer-related updates. That’s pretty efficient!

### Deleting a Node

When we want to delete a node, the steps we take are similar-ish to what we did when adding nodes. Let’s say that we want to delete node D in our linked list:

![](https://www.kirupa.com/data_structures_algorithms/images/delete_node_d_200.png)

What we do is update the next pointer on node C to reference node E directly, bypassing node D:

![](https://www.kirupa.com/data_structures_algorithms/images/deletion_step_node_200.png)

We also clear the next pointer on the D node. All of this makes node D unreachable via a traversal and removes any connection this node has with the rest of the nodes in our linked list. *Unreachable* does not mean *deleted*, though. When does node D actually get deleted? The exact moment varies, but this will happen automatically as part of something known as **garbage collection** when our computer reclaims memory by getting rid of unwanted things.

## Linked List: Time and Space Complexity

It’s time for some more fun! We started off our look at linked lists by talking about how fast and efficient they are. For the most common operations, the following table summarizes how our linked list performs:

An important detail to keep in mind is that the exact implementation of a linked list plays an important role in how fast or slow certain operations are. One implementation choice we will make is that our linked list will have a direct reference to both the ***first*** (aka ***head***) node and the ***last*** (aka ***tail***) node.

### Deeper Look at the Running Time

The table glosses over some subtle (but very important) details, so let's call out the relevant points below:

***Search:***

- Searching for an element in a singly linked list takes O(n) time. This is because we have to traverse the list from the beginning to find the element
- If what we are looking for happens to be the first item, then we return the found node in O(1) time

***Adding / Insertion:***

- Inserting an element at the beginning or end of a singly linked list takes O(1) time, as we only need to update the reference of the new node to point to the current head or tail of the list.
- Inserting an element at a specific position in the list takes O(n) time in the average and worst cases, for we have to traverse through the list to find the position

***Deletion:***

- Similar to the adding case, deleting an element from the beginning or end of a singly linked list takes O(1) time, as we only need to update the reference of the first or last node.
- Deleting an element from a specific position in the list takes O(n) time in the average and worst cases, for we have to traverse the list to find the element and then delete it

### Space Complexity

From a memory/space point of view, linked lists require O(n) space. For each piece of data we want our linked list to store, we wrap that data into a node . The node itself is a very lightweight structure where all it contains is a thin wrapper to store our data and a reference to the next node.

## JavaScript Implementation

We have covered a lot of theoretical ground so far. It's time to make our linked list real by looking at the JavaScript implementation. The full code for using a linked list looks as follows:

```js
class Node {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  addFirst(data) {
    const newNode = new Node(data, this.head);

    this.head = newNode;

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

    this.size++;
  }

  addLast(data) {
    const newNode = new Node(data);

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

    this.size++;
  }

  addBefore(data, beforeData) {
    const newNode = new Node(data);

    if (this.size === 0) {
      this.head = newNode;
      this.size++;
      return;
    }

    if (this.head.data === beforeData) {
      newNode.next = this.head;
      this.head = newNode;
      this.size++;
      return;
    }

    let current = this.head.next;
    let prev = this.head;

    while (current) {
      if (current.data === beforeData) {
        newNode.next = current;
        prev.next = newNode;
        this.size++;
        return;
      }

      prev = current;
      current = current.next;
    }

    throw new Error(`Node with data '${beforeData}' not found in list`);
  }

  addAfter(data, afterData) {
    const newNode = new Node(data);

    if (this.size === 0) {
      this.head = newNode;
      this.size++;
      return;
    }

    let current = this.head;

    while (current) {
      if (current.data === afterData) {
        newNode.next = current.next;
        current.next = newNode;
        this.size++;
        return;
      }

      current = current.next;
    }

    throw new Error(`Node with data '${afterData}' not found in list!`);
  }

  removeFirst() {
    if (!this.head) {
      throw new Error('List is empty');
    }

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

  removeLast() {
    if (!this.tail) {
      throw new Error('List is empty');
    }

    if (this.head === this.tail) {
      this.head = null;
      this.tail = null;
      this.size--;
      return;
    }

    let current = this.head;
    let prev = null;

    while (current.next) {
      prev = current;
      current = current.next;
    }

    prev.next = null;
    this.tail = prev;
    this.size--;
  }

  remove(data) {
    if (this.size === 0) {
      throw new Error("List is empty");
    }

    if (this.head.data === data) {
      this.head = this.head.next;
      this.size--;
      return;
    }

    let current = this.head;

    while (current.next) {
      if (current.next.data === data) {
        current.next = current.next.next;
        this.size--;
        return;
      }

      current = current.next;
    }

    throw new Error(`Node with data '${data}' not found in list!`);
  }

  toArray() {
    const arr = [];

    let current = this.head;

    while (current) {
      arr.push(current.data);
      current = current.next;
    }

    return arr;
  }
}
```

Take a few moments to go through the code, especially the name of the methods that correspond to the operations we can perform on our linked list:

- addLast
- addFirst
- addAfter
- addBefore
- removeFirst
- removeLast
- remove
- toArray

What these operations do should be straightforward. The addAfter and addBefore methods take two arguments. The first argument stands for the data we wish to add. The second argument stands for the existing data in the linked list we wish to add our data either next to or before. With the remove method, we specify an argument for the data we wish to remove from our linked list.

Below is an example of us creating a linked list, using the letters A through E that we saw in the examples earlier, and some common operations:

```js
let letters = new LinkedList();
letters.addLast("A");
letters.addLast("B");
letters.addLast("C");
letters.addLast("D");
letters.addLast("E");

console.log(letters.toArray()); // ['A', 'B', 'C', 'D', 'E']

letters.addFirst("AA");
letters.addLast("Z");

console.log(letters.toArray()); // ['AA', 'A', 'B', 'C', 'D', 'E', 'Z']

letters.remove("C");
letters.removeFirst();
letters.removeLast();

console.log(letters.toArray()); // ['A', 'B', 'D', 'E']

letters.addAfter("Q", "D");

console.log(letters.toArray()); // ['A', 'B', 'D', 'Q', 'E']
```

You may be wondering

## Conclusion

In the many past sections, through lots of words and countless diagrams, we learned about binary trees! The 411 is that a binary tree is a data structure that consists of nodes with an important constraint: ***each node can have at most two child nodes***. The unique constraint of the binary tree allows us to use them to efficiently search, sort, and store data. Now, we didn't cover any of that here. The reason is that a binary tree by itself is too generic. The more useful variant of the binary tree is the **binary search tree**, and we are going to look at it next.