Skip to content

Instantly share code, notes, and snippets.

@Phryxia
Created August 18, 2025 16:34
Show Gist options
  • Save Phryxia/bd53bd8e8e1735ba494f07ac9108692d to your computer and use it in GitHub Desktop.
Save Phryxia/bd53bd8e8e1735ba494f07ac9108692d to your computer and use it in GitHub Desktop.
TypeScript implementation of LinkedList with iterator protocol
export interface LinkedListNode<T> {
value: T;
next: LinkedListNode<T>;
prev: LinkedListNode<T>;
}
export class LinkedList<T> implements Iterable<T> {
// @ts-ignore
head: LinkedListNode<T> = {};
// @ts-ignore
tail: LinkedListNode<T> = {};
constructor() {
this.head.prev = this.head;
this.head.next = this.tail;
this.tail.prev = this.head;
this.tail.next = this.tail;
}
checkIsBegin(it: LinkedListIterator<T>): boolean {
return it.node === this.head;
}
checkIsEnd(it: LinkedListIterator<T>): boolean {
return it.node === this.tail;
}
/**
* Insert given `value` after the node pointed by given iterator `it`.
*
* @param value
* @param it The point where value is inserted after. If it's ommited, last node will be used for base.
* @returns New iterator pointing added value
*/
insertAfter(value: T, it?: LinkedListIterator<T>): LinkedListIterator<T> {
const base = it?.node ?? this.tail.prev;
const newNode: LinkedListNode<T> = {
value,
next: base.next,
prev: base,
};
base.next.prev = newNode;
base.next = newNode;
return new LinkedListIterator(this, newNode);
}
/**
* Remove value pointed by given iterator `it`
*
* @param it iterator pointing at the removing target
* @return New iterator pointing at the next element of `value`
*/
remove(it: LinkedListIterator<T>): LinkedListIterator<T> {
const node = it.node;
const next = node.next;
node.prev.next = next;
node.next.prev = node.prev;
return new LinkedListIterator(this, next);
}
[Symbol.iterator](): LinkedListIterator<T> {
return new LinkedListIterator(this, this.head);
}
}
class LinkedListIterator<T> implements IterableIterator<T> {
constructor(public list: LinkedList<T>, public node: LinkedListNode<T>) {}
next(): IteratorResult<T> {
this.node = this.node.next;
if (this.list.checkIsEnd(this)) {
return {
done: true,
value: undefined,
};
}
return {
value: this.node.value,
};
}
[Symbol.iterator](): IterableIterator<T> {
return this;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment