# LinkedList in JavaScript

**URL:** <https://forum.kirupa.com/t/linkedlist-in-javascript/637119>\
**Category:** web dev\
**Created:** [September 2, 2017, 9:25pm UTC](https://forum.kirupa.com/t/linkedlist-in-javascript/637119 "2017-09-02T21:25:05Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![kirupa](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/kirupa/32/11616_2.png) [@kirupa](https://forum.kirupa.com/u/kirupa)\
**Post date:** [September 2, 2017, 9:25pm UTC](https://forum.kirupa.com/t/linkedlist-in-javascript/637119/1 "2017-09-02T21:25:05Z")

</div>

Another day, another data structure in JS that every other language takes for granted 🙂

```auto
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;
  }
}

```

The usage for it is simple:

```auto
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']

```

I haven’t done any extensive testing on it yet, so let me know if you find any issues with it 😛

Cheers,  
Kirupa

---

<div class="post-metadata">

**Author:** ![senocular](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/senocular/32/7217_2.png) [@senocular](https://forum.kirupa.com/u/senocular)\
**Post date:** [September 3, 2017, 2:58am UTC](https://forum.kirupa.com/t/linkedlist-in-javascript/637119/2 "2017-09-03T02:58:05Z")

</div>

There are a couple of problems with single node lists. For example, removeLast() will do nothing because it starts comparing the second item (n1.next) to tail rather than head itself.

```auto
var foo = new LinkedList();

foo.add("1");
foo.removeLast();
foo.count //-> 1

```

remove() also fails slightly in this case in that it doesn’t clear tail.

```auto
var foo = new LinkedList();

foo.add("1");
foo.remove("1");
foo.head //-> undefined
foo.tail //-> Node

```

Of course you don’t really need the tail in this implementation anyway, since you can check next for null to determine if you’re at the last node in the list, That is unless you like having it as a convenient reference to the last item without iteration 😉

---

<div class="post-metadata">

**Author:** ![krilnon](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/krilnon/32/34_2.png) [@krilnon](https://forum.kirupa.com/u/krilnon)\
**Post date:** [September 3, 2017, 5:07am UTC](https://forum.kirupa.com/t/linkedlist-in-javascript/637119/3 "2017-09-03T05:07:56Z")

</div>

> [@kirupa](#):
>
> let me know if you find any issues with it

There’s an identity vs equality issue. For example, if you use `new String("someString")` instead of `"someString"`, you get 3 different results depending on whether you’re using `==` or `===` in the two relevant cases in `remove`:

```javascript
foo.add(new String("1"));
foo.add(new String("1"));
foo.add(new String("1"));
foo.add(new String("1"));
foo.add(new String("1"));
foo.add(new String("1"));
foo.add(new String("1"));

foo.remove("1");
foo.remove("1");
foo.remove("1");
foo.remove("1");
foo.remove("1");
foo.remove("1");
foo.remove("1");
foo.remove("1");
foo.remove("1");
foo.remove("1");
foo.remove("1");

```

```auto
// using 2x ==
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
There are no items!
There are no items!
There are no items!
There are no items!
0 "!"

// using 1x ==, 1x ===
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
1 "!"

using 2x ===
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
Setting data: 1
7 "!"

```

---

<div class="post-metadata">

**Author:** ![senocular](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/senocular/32/7217_2.png) [@senocular](https://forum.kirupa.com/u/senocular)\
**Post date:** [September 3, 2017, 2:21pm UTC](https://forum.kirupa.com/t/linkedlist-in-javascript/637119/4 "2017-09-03T14:21:43Z")

</div>

Along these lines, given the current `==` usage, there’s also this kind of behavior:

```javascript
var foo = new LinkedList();

foo.add({bar: 'hello'});
foo.add({baz: 'world'});
foo.add({qux: '!'});
foo // {"bar":"hello"}, {"baz":"world"}, {"qux":"!"}

foo.remove('[object Object]')
foo // {"baz":"world"}, {"qux":"!"}

foo.remove('[object Object]')
foo // {"qux":"!"}

// etc.

```

---

<div class="post-metadata">

**Author:** ![kirupa](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/kirupa/32/11616_2.png) [@kirupa](https://forum.kirupa.com/u/kirupa)\
**Post date:** [September 3, 2017, 5:40pm UTC](https://forum.kirupa.com/t/linkedlist-in-javascript/637119/5 "2017-09-03T17:40:18Z")

</div>

Thanks for pointing these issues out sen, kril! I’ve updated the code to take into account single item lists. I’ve also replaced the == with ===. I think that solves most of the equality issues, but that is a tricky one.

---

<div class="post-metadata">

**Author:** ![kirupa](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/kirupa/32/11616_2.png) [@kirupa](https://forum.kirupa.com/u/kirupa)\
**Post date:** [April 2, 2023, 8:19pm UTC](https://forum.kirupa.com/t/linkedlist-in-javascript/637119/6 "2023-04-02T20:19:04Z")

</div>

I’m writing my next chapter on `LinkedList` for my upcoming book, and I have updated my method names and behavior to match the excellent .NET variation 🙂

> **[LinkedList.Remove Method (System.Collections.Generic)](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.linkedlist-1.remove?view=net-8.0)**
>
> Removes the first occurrence of a node or value from the LinkedList.