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:
- Users might want to store
null in the list.
- It's consistent with
Array and Map.
- It plays nice with the optional chaining operator
?. (which returns undefined).
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.
#head;
#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;
let current = this.#head;
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;
else this.#head = 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.#head = undefined;
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
this.#insertBefore(this.#head, value);
}
find(value) {
let current = this.#head;
// Using a for-loop is cleaner:
for (let i = 0; current; ++i) {
if (current.v === value) return i;
current = current.n;
}
return -1;
}
read(index) { // Original's parameter had a typo: read(v) -> read(index)
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;
else this.#head = 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!
remove(-1)orDoublyLinkedList().insert({}, 1)\$\endgroup\$