Created
August 18, 2025 16:34
-
-
Save Phryxia/bd53bd8e8e1735ba494f07ac9108692d to your computer and use it in GitHub Desktop.
TypeScript implementation of LinkedList with iterator protocol
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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