Linked list implementation in Deno, part 2
June 13, 2020
In the previous post, we implemented some core features necessary to build a linked list in Typescript. If you haven’t read it, go check it out.
A (short) detour into Typescript: type assertion functions
Before jumping into the remaining methods of our linked list, let’s examine a helper function we’ll use a bit later that makes working with possibly nullish values a little nicer.
The Typescript dev team introduced type assertion functions in Typescript 3.7. One of my favorite ways to use type assertion functions is the assertIsDefined
helper:
export function assertIsDefined<T>(value: T): asserts value is NonNullable<T> {
if (value === undefined || value === null) {
throw new Error(`AssertionError: expected value ${value} to be NonNullable.`);
}
}
type Example = {
name: string;
address?: {
city: string;
postalCode?: string;
}
};
const nathan: Example = {
name: "nathan",
address: { city: "Washington" },
};
assertIsDefined(nathan.address);
// No Typescript errors that "nathan.address" is possibly undefined
console.log(nathan.address.city)
Type assertion functions eliminate clumsy conditional code, like:
if (nathan.address) {
console.log(nathan.address.city);
}
If you’re interested in reading more about type assertion functions, check out:
- The release notes for 3.7
- The PR implementing type assertion functions
With that, let’s resume our linked list implementation!
Linked list methods, part 2
In part 2 of our linked list implementation, we’ll be adding the following public methods:
- LinkedList.prototype.clear
- Delete all nodes from the list.
- LinkedList.prototype.index
- Retrieve the node at the given index.
- LinkedList.prototype.insert
- Insert a node at the head of the list.
- LinkedList.prototype.insertAt
- Insert a node at the given index.
- LinkedList.prototype.remove
- Delete the given node.
- LinkedList.prototype.removeAt
- Delete a node at the given index.
- LinkedList.prototype.removeFirst
- Delete the first node (a.k.a.
head
) in the list. - LinkedList.prototype.removeLast
- Delete the last node (a.k.a.
tail
) in the list.
LinkedList.prototype.clear
Emptying a link list is easy; just reset all the stateful properties in the class to their original values. The garbage collector will do the rest!
class LinkedList<T> {
...
clear(): void {
this.#head = undefined;
this.#tail = undefined;
this.#count = 0;
}
...
}
// LinkedList.prototype.clear
(() => {
const list = new LinkedList<string>();
list.append("foo");
list.append("bar");
assertEquals(list.count(), 2);
list.clear()
assertEquals(list.count(), 0);
assertEquals(list.head(), undefined);
assertEquals(list.tail(), undefined);
})();
LinkedList.prototype.index
Finding a node at a given index takes a little more work. We’ve made some optimizations to our linked list by keeping track of our head
and tail
nodes. Accessing each of those is an O(1) operation. Since we are also tracking how many nodes our list has in the count
property, we can easily tell if a provided index is out-of-bounds. That means the most expensive lookup, O(n), will be accessing the node just before the tail
because we have to cycle through each node until we reach it.
class LinkedList {
...
index(index: number): Node<T> | undefined {
if (index < 0) {
throw new IndexError(
"IndexError: Index cannot be a negative number."
);
}
if (this.isEmpty()) {
throw new IndexError(
"IndexError: Cannot index an empty list."
);
}
if (index === 0) {
return this.head();
}
const lastIndex = this.count() - 1;
if (index > lastIndex) {
throw new IndexError(
"IndexError: Index exceeds the number of nodes in the list."
);
}
if (index === lastIndex) {
return this.tail();
}
let node = this.head();
for (let i = 0; i !== index; i++) {
node = node!.next;
}
return node;
}
...
}
// LinkedList.prototype.index
(() => {
const list = new LinkedList<string>();
// Throws when a negative number is passed
assertThrows(() => list.index(-1));
// Throws when an index larger than count is passed
assertThrows(() => list.index(1));
list.append("foo");
list.append("bar");
list.append("baz");
assertEquals(list.index(0)!.value, "foo");
assertEquals(list.index(1)!.value, "bar");
assertEquals(list.index(2)!.value, "baz");
})();
LinkedList.prototype.insert
With the insert
method, we can insert a new node at the head of the list. Insert is an O(1) operation because the head of the list is always known. Insertion is as simple as instantiating a new node and updating the pointers on the new node and the previous head
. Not too different, conceptually, from our append method from part one!
class LinkedList {
...
insert(value: T): void {
const node = new Node<T>(value);
const head = this.head();
if (head) {
head.previous = node;
node.next = head;
this.#head = node;
} else {
this.#head = node;
this.#tail = node;
}
this.#count++;
}
...
}
// LinkedList.prototype.insert
(() => {
const list = new LinkedList<string>();
list.insert("foo");
list.insert("bar");
const head = list.head();
const tail = list.tail();
assertEquals(head!.value, "bar");
assertEquals(tail!.value, "foo");
})();
LinkedList.prototype.insertAt
The inserAt
method uses the index method from earlier to grab a reference to the current node occupying the index where we want to insert the new node (notice the use of assertIsDefined
!). Then it’s just a matter of updating pointers and incrementing the count
property.
class LinkedList {
...
insertAt(index: number, value: T) {
const node = new Node<T>(value);
const current = this.index(index);
assertIsDefined(current);
const previous = current.previous;
if (previous) {
previous.next = node;
node.previous = previous;
}
node.next = current;
current.previous = node;
this.#count++;
}
...
}
// LinkedList.prototype.insertAt
(() => {
const list = new LinkedList<string>();
// Cannot use LinkedList.prototype.insertAt on an empty list
assertThrows(() => list.insertAt(0, "foo"));
// [foo]
list.insert("foo");
// Cannot use LinkedList.prototype.insertAt to append to a list
assertThrows(() => { list.insertAt(1, "bar") });
// [baz] => [foo]
list.insert("baz");
// [baz] => [bar] => [foo]
list.insertAt(1, "bar");
assertEquals(list.index(1)!.value, "bar");
assertEquals(list.index(1)!.previous!.value, "baz");
assertEquals(list.index(1)!.next!.value, "foo");
// [baz] => [bar] => [qux] => [foo]
list.insertAt(2, "qux");
assertEquals(list.index(2)!.value, "qux");
assertEquals(list.index(2)!.previous!.value, "bar");
assertEquals(list.index(2)!.next!.value, "foo");
})();
LinkedList.prototype.remove
Now that we have a couple methods for adding nodes to the linked list, we also need a way to remove a node. We’ll start with the remove
method, because it will get reused in the other “remove” convenience methods.
To remove a node, we first need a reference to it. For the sake of clarity, let’s refer to the node being removed as the removed node.
First, we’ll grab the previous
and next
properties of the removed node. If the previous
property points to a node, we update the previous’ node’s next
property to point the removed node’s next
node.
If the remove node’s previous
property does not contain a pointer to node, that means it’s the list’s current head. So we’ll have to update the head
property of the list to point to the removed node’s next
node.
If the remove node’s next
property points to a node, we’ll update it so that the next node’s previous
property points to the removed node’s previous
node.
If the remove node’s next
property does not contain a pointer to a node, that means it’s the list’s current tail
. So we need to update the tail
property of the list to point to the removed node’s previous
node.
Finally, we’ll decrement the count property to reflect the removal of the node.
Phew, that’s a lot of words! The code expresses the same idea much more succinctly!
class LinkedList {
...
remove(node: Node<T>) {
const { previous, next } = node;
if (previous) {
previous.next = next;
} else {
this.#head = next;
}
if (next) {
next.previous = previous;
} else {
this.#tail = previous;
}
this.#count--;
}
...
}
// LinkedList.prototype.remove
(() => {
const list = new LinkedList<string>();
list.append("foo");
list.append("bar");
list.append("baz");
const head = list.head();
const bar = list.index(1);
const tail = list.tail();
assertIsDefined(bar);
assertIsDefined(head);
assertIsDefined(tail);
list.remove(bar);
assertEquals(head.next!.value, "baz");
assertEquals(tail.previous!.value, "foo");
list.remove(tail);
assertEquals(head.next, undefined);
list.remove(head);
assertEquals(list.isEmpty(), true);
})();
LinkedList.prototype.removeAt
Now that we have index
and remove
methods, removing a node at a given index is very easy.
class LinkedList {
...
removeAt(index: number) {
const node = this.index(index);
assertIsDefined(node);
this.remove(node);
}
...
}
// LinkedList.prototype.removeAt
(() => {
const list = new LinkedList<string>();
assertThrows(() => list.removeAt(0));
list.append("foo");
list.append("bar");
list.append("baz");
list.append("qux");
list.removeAt(2);
const bar = list.index(1);
assertIsDefined(bar);
assertEquals(list.count(), 3);
assertEquals(bar.value, "bar");
assertEquals(bar.previous!.value, "foo");
assertEquals(bar.next!.value, "qux");
})();
LinkedList.prototype.removeFirst
Likewise, removeFirst
is an easy implementation.
class LinkedList {
...
removeFirst() {
const node = this.head();
assertIsDefined(node);
this.remove(node);
}
...
}
// LinkedList.prototype.removeFirst
(() => {
const list = new LinkedList<string>();
assertThrows(() => list.removeFirst());
list.insert("foo");
list.insert("bar");
list.removeFirst();
assertEquals(list.count(), 1);
assertEquals(list.head()!.value, "foo");
})();
LinkedList.prototype.removeLast
So is removeLast
.
class LinkedList {
...
removeLast() {
const node = this.tail();
assertIsDefined(node);
this.remove(node);
}
...
}
// LinkedList.prototype.removeLast
(() => {
const list = new LinkedList<string>();
assertThrows(() => list.removeLast());
list.insert("foo");
list.insert("bar");
list.removeLast();
assertEquals(list.count(), 1);
assertEquals(list.head()!.value, "bar");
})();
And with that our doubly linked list is complete!
The complete code for this linked list implementation is available on Github.