Posted on

Problem

A doubly linked list contains elements that include pointers to the previous and next element along with a value. This data structure is implemented with methods similar to what you would find in an array: insert or remove elements, read the value at an index or find an index that contains a value.

Just looking to see if my implementation is good. Did I make any mistakes? Did I do anything unusual?

``````function Node(v, p, n) {
this.v = v;
this.p = p;
this.n = n;
}

this.size = 0;
this.tail = null;

this.append = (v) => {
if (this.size === 0) {
this.head = this.tail = new Node(v, null, null);
} else {
this.tail.n = new Node(v, this.tail, null);
this.tail = this.tail.n;
}
this.size++;
};

this.prepend = (v) => {
if (this.size === 0) {
this.head = this.tail = new Node(v, null, null);
} else {
}
this.size++;
};

this.find = (v) => {
let index = -1;

while (current) {
index++;
if (current.v === v) {
return index;
} else {
current = current.n;
}
}
return -1;
};

if (v >= this.size) return null;
let step = 0;

while (step < v) {
step++;
current = current.n;
}
return current.v;
};

this.insert = (v, i) => {
let step = 0;

if (i === 0) {
this.prepend(v);
} else if (i === this.size) {
this.append(v);
} else {
while (step < i) {
step++;
current = current.n;
}
current.p.n = current.p = new Node(v, current.p, current);
this.size++;
}
};

this.remove = (i) => {
let step = 0;

if (i === 0 && this.size === 1) {
} else if (i === 0) {
} else if (i === this.size - 1) {
this.tail = this.tail.p;
this.tail.n = null;
} else {
while (step < i) {
step++;
current = current.n;
}
current.p.n = current.n;
current.n.p = current.p;
current.v = current.p = current.n = null;
}
this.size--;
};
}
```
``````

Solution

First, a bug: `read()` doesn’t properly check negative indices; `list.read(-42)` currently returns the first value (or throws an exception on an empty list).

As slepic pointed out, unless you want to support dinosaur browsers, you should be using class syntax instead of constructor functions; The way you have it right now, every `DoublyLinkedList` you create has a copy of every method stored on each individual object. The performance implications are not good. The class syntax automatically puts methods on the prototype instead, which also allows inheritance. (You don’t need to understand prototypes unless you’re doing something fancy, just stick to class syntax.)

I’m not sure I like using single letters for your member and parameter names. You definitely shouldn’t be using “i” as a parameter name, since `i` is typically used as the index variable in a loop, making it very confusing.

`insert(value, index)` is confusing, the idiom would be `insert(index, value)`.

The name “Node” already exists in JavaScript. This isn’t a problem if your code is in a module, but otherwise might accidentally shadow the original.

Your code should probably return `undefined` for missing elements instead of `null`, here’re some reasons:

1. Users might want to store `null` in the list.
2. It’s consistent with `Array` and `Map`.
3. It plays nice with the optional chaining operator `?.` (which returns `undefined`).
4. `typeof null === "object"` (all sorts of horrifying).

I also prefer using `undefined` internally so that I can pretend `null` doesn’t exist.

`size` should be externally readonly; This means that the list can change its own `size`, but the user can’t accidentally set `size` to some incorrect number. You can do this by using a private field and a public getter.

There are a couple bits of code that can be factored out: Getting a `Node` from an index and inserting before/after a given `Node`. This simplifies code and prevents mistakes/unmaintainability due to repetition.

``````class DoublyLinkedList {
// The hashtag at the start of member names makes them private
// (you might also come across code that uses underscores _ instead).
// Predeclaring field names like this is optional for public fields.
#tail;
// size is private to avoid user messing with it;
// We'll give them access with a getter instead:
#size;

// This is a getter; It acts like a normal field, but the user
// can only read it (i.e. they cannot set the size themselves).
get size() { return this.#size; }

// This is assuming you don't want to expose these functions publicly.
#getNode(index) {
if (index < 0 || index >= this.#size) return undefined;

for (let step = 0; step < index; ++step) {
current = current.n;
}

return current;
}

#insertBefore(node, value) {
const newNode = new Node(value, node.p, node);

if (node.p) node.p.n = newNode;

node.p = newNode;

++this.#size;
}

// Doesn't really refactor anything, but it'd be weird not to have:
#insertAfter(node, value) {
const newNode = new Node(value, node, node.n);

if (node.n) node.n.p = newNode;
else this.#tail = newNode;

node.n = newNode;

++this.#size;
}

// With this, you can refactor your class as:

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

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

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

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

}

find(value) {

// Using a for-loop is cleaner:
for (let i = 0; current; ++i) {
if (current.v === value) return i;
current = current.n;
}

return -1;
}

const node = this.#getNode(index);
if (node) return node.v;

return undefined;

// Shorter using optional chaining: return this.#getNode(index)?.v;
}

// This function should return true/false to indicate success.
// I'd personally throw an Error on failure instead,
// since something's gone wrong if you have the wrong index.
// Your code does unintentionally throw an Error as-is,
// but the error message isn't appropriate.
// Also note the swapped parameter order.
insert(index, value) {
if (index < 0 || index > this.#size) return false;

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

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

return true;
}

// Following Array's conventions, this should return the removed value
// or undefined if it didn't exist (could also throw Error).
remove(index) {
const node = this.#getNode(index);
if (!node) return undefined;

// Instead of having many special cases based on the index and list's size,
// just check if node the has neighbours and act accordingly.
// This is cleaner than having cases for every possible combination
// of the p and n nodes existing.

if (node.p) node.p.n = node.n;

if (node.n) node.n.p = node.p;
else this.#tail = node.p;

--this.#size;

return node.v;
}
}
``````

A few suggestions:

• Currently, none of your code really needs the list to be doubly linked; You could switch to a singly linked list instead and save memory/performance/complexity, or you could add things like a reverse iterator which lets the user take advantage of it.
• You could modify your functions to check if the index is more than halfway through the list and iterate backward if so. This would half the average number of nodes you need to traverse (though it might perform worse on small lists).

Don’t let my rant discourage you though, good work!