/

JavaScript Data Structures: Linked Lists - Improve Your Technical Blog

JavaScript Data Structures: Linked Lists - Improve Your Technical Blog

Linked lists are a crucial data structure to learn in JavaScript. They allow us to efficiently store and manage data by connecting each item to the next item in the list. Unlike arrays, linked list items do not need to be stored in adjacent memory locations and cannot be randomly accessed using indices.

Since JavaScript does not natively support linked lists, we can create our implementation. To start, let’s create the “Item” class that represents each item in the linked list:

1
2
3
4
5
6
7
8
class Item {
  next = null;
  value = null;
  
  constructor(value) {
    this.value = value;
  }
}

The “Item” class contains two properties: “next” and “value”. “next” is a reference to the next item in the list, and “value” holds the actual value of the item.

Next, we’ll define the “LinkedList” class, which will have two private properties: “head” and “tail”. The “LinkedList” class provides methods for adding items to the list and obtaining the size of the list:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class LinkedList {
  #head = null;
  #tail = null;
  
  append = (value) => {
    const item = new Item(value);
    
    if (!this.#head) {
      this.#head = item;
      this.#tail = item;
    } else {
      this.#tail.next = item;
      this.#tail = item;
    }
  };
  
  size = () => {
    let count = 0;
    let item = this.#head;
    
    while (item) {
      count++;
      item = item.next;
    }
    
    return count;
  };
}

In the above code, the “append” method adds an item to the end of the linked list. If it’s the first item being added, the item becomes both the head and tail of the list. The “size” method iterates through the list and counts the number of items.

Let’s see how we can use the LinkedList class:

1
2
3
4
const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);

We can also find an item in the list by its value using the “find” method:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class LinkedList {
  //...
  
  find = (value) => {
    let item = this.#head;
    
    while (item) {
      if (item.value === value) {
        return item;
      }
      
      item = item.next;
    }
    
    return null;
  };
}

const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
const item = list.find(2); // item.value === 2

To insert an item at a specific position in the linked list, we can use the “insert” method:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class LinkedList {
  //...
  
  insert = (index, value) => {
    if (index < 0 || index > this.size()) {
      return;
    }
    
    const node = new Item(value);
    let current = this.#head;
    let previous = null;
    
    if (index === 0) {
      node.next = current;
      this.#head = node;
    } else {
      let i = 0;
      
      while (i++ < index) {
        previous = current;
        current = current.next;
      }
      
      node.next = current;
      previous.next = node;
    }
  };
}

const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.insert(2, 'a');
list.size(); // 4

Lastly, there is the double-linked list, where each item has a reference to both the next and previous elements.