LinkedList in JavaScript

programming web dev
1

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

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:

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 :stuck_out_tongue:

Cheers,
Kirupa

2

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.

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.

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 :wink:

1 Like
3

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:

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");

// 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 "!"
1 Like
4

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

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.
1 Like
5

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.

6

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 :slight_smile: