Doubly Linked List with forward and reverse iterators (javascript)

Question

A doubly linked list contains elements that include pointers to the previous and next element along with a value. Being able to search and iterate through the list in both directions is an important feature.

This is my improvement over the previous version. I implemented it with classes, added a forward and reverse iterator, added a reverse search, and made reading at an index faster by starting at the end if the index is after the middle of the list.

I am looking for any advice on how this can be improved, both from a style and from a data structure perspective. If there are mistakes, or any redundant code, please tell me about it.

class ListElement {
  constructor(value, prev, next) {
    this.value = value;
    this.prev = prev;
    this.next = next;
  }
}

class DoublyLinkedList {
  #size;
  #head;
  #tail;

  constructor() {
    this.#size = 0;
    this.#head = undefined;
    this.#tail = undefined;
  }

  #getListElement(index) {
    if (index < 0 || index >= this.#size) return undefined;

    let currentElement;

    if (index < Math.floor(this.#size / 2)) {
      currentElement = this.#head;
      for (let step = 0; step < index; ++step) {
        currentElement = currentElement.next;
      }
    } else {
      currentElement = this.#tail;
      for (let step = this.#size - 1; step > index; --step) {
        currentElement = currentElement.prev;
      }
    }

    return currentElement;
  }

  #insertBefore(element, value) {
    const newListElement = new ListElement(value, element.prev, element);

    if (element.prev) element.prev.next = newListElement;
    else this.#head = newListElement;

    element.prev = newListElement;

    ++this.#size;
  }

  #insertAfter(element, value) {
    const newListElement = new ListElement(value, element, element.next);

    if (element.next) element.next.prev = newListElement;
    else this.#tail = newListElement;

    element.next = newListElement;

    ++this.#size;
  }

  size() {
    return this.#size;
  }

  empty() {
    let currentElement = this.#head;

    for (let step = 0; step < this.#size; ++step) {
      if (currentElement.prev) currentElement.prev.next = undefined;
      currentElement.value = currentElement.prev = undefined;
      currentElement = currentElement.next;
    }

    this.#head = this.#tail = undefined;
    this.#size = 0;
  }

  append(value) {
    if (this.#size === 0) {
      this.#head = this.#tail = new ListElement(value, undefined, undefined);
      this.#size = 1;
      return;
    }

    this.#insertAfter(this.#tail, value);
  }

  prepend(value) {
    if (this.#size === 0) return this.append(value);

    this.#insertBefore(this.#head, value);
  }

  headFind(value) {
    let currentElement = this.#head;

    for (let step = 0; step < this.#size; ++step) {
      if (currentElement.value === value) return step;
      currentElement = currentElement.next;
    }

    return -1;
  }

  tailFind(value) {
    let currentElement = this.#tail;

    for (let step = this.#size - 1; step >= 0; --step) {
      if (currentElement.value === value) return step;
      currentElement = currentElement.prev;
    }

    return -1;
  }

  read(index) {
    return this.#getListElement(index)?.value;
  }

  insert(index, value) {
    if (index < 0 || index > this.#size) return false;

    if (index === this.#size) {
      this.append(value);
      return true;
    }

    this.#insertBefore(this.#getListElement(index), value);

    return true;
  }

  remove(index) {
    const element = this.#getListElement(index);
    if (!element) return undefined;

    if (element.prev) element.prev.next = element.next;
    else {
      this.#head = element.next;
      this.#head.prev = undefined;
    }

    if (element.next) element.next.prev = element.prev;
    else {
      this.#tail = element.prev;
      this.#tail.next = undefined;
    }

    --this.#size;

    return element.v;
  }

  [Symbol.iterator]() {
    let currentElement = this.#head;

    return {
      next: () => {
        if (currentElement) {
          const currentValue = currentElement.value;
          currentElement = currentElement.next;

          return { value: currentValue, done: false };
        } else {
          return { done: true };
        }
      },
    };
  }

  reverse() {
    return {
      [Symbol.iterator]: () => {
        let currentElement = this.#tail;

        return {
          next: () => {
            if (currentElement) {
              const currentValue = currentElement.value;
              currentElement = currentElement.prev;

              return { value: currentValue, done: false };
            } else {
              return { done: true };
            }
          },
        };
      },
    };
  }
}

Some test code to see it in action:

const list = new DoublyLinkedList();

list.append(20);
list.append(30);
list.append(40);
list.append(50);
list.insert(1, 5);
list.insert(3, 6);
list.insert(6, 7);
list.prepend(10);

for (let element of list) {
  console.log(element);
}

console.log();

list.remove(list.size() - 1);
list.remove(list.size() - 2);
list.remove(0);

for (let element of list) {
  console.log(element);
}

console.log();

console.log(list.tailFind(7));
console.log(list.headFind(5));
console.log(list.read(1));
console.log(list.read(list.size() - 2));

Answer 1

Very nice! A couple things:

Linked lists don't only optimize removing a single element, they are equally efficient at removing spans of elements by only detaching them at the ends. Thus, empty() can be greatly simplified to:

empty() {
    this.#head = this.#tail = undefined;
    this.#size = 0;
}

Though I wonder if your current implementation might be easier on the garbage collector... Not worth thinking about.

Since you have iterators now, you can use them to minorly simplify your other code:

headFind(value) {
    let step = 0;
    for (const e of this) {
        if (e === value) return step;
        ++step;
    }

    return -1;
}

tailFind(value) {
    let step = this.#size - 1;

    for (const e of this.reverse()) {
        if (e === value) return step;
        --step;
    }

    return -1;
}

Writing iterators manually is a pain. That's one reason why the schmucks at JavaScript HQ gave us generator functions! They let you write iterators like normal code; When .next() is called, the generator code will run until it reaches a yield statement, at which point .next() will return whatever you gave to the statement. But when .next() is called again, the generator code will continue right where it left off!

// The asterisk * before the function makes it a generator function:
*[Symbol.iterator]() {
    for (let current = this.#head; current; current = current.next) {
        yield current.value; // Generator will pause until the next call to next()
    }
}

*reverse() {
    for (let current = this.#tail; current; current = current.prev) {
        yield current.value;
    }
}

Your iterators are relatively simple, but manual iterators get gross quickly if you need to do something advanced.

Besides that, here're a couple neutral notes:

• My original suggestion for remove() worked properly, but your version's redundant assignments to undefined might in fact make the code more readable. Wicked!
• I want to confirm that you understand the difference between size() and get size(). Ultimately, it's up to you if you want to use a method instead of a getter for your API.
• Your test code at the end doesn't cover all your functions, nor does it test edge cases. This isn't really important since you're just mucking around, but this is a good place to practice unit tests. Things like "does prepend()/append() work when the list is empty?", "can I insert() into an empty list properly?" and so on.