A sortable link list

README.md

Sortable Linked List

Usage

class ComparableNumber implements Comparable<number> {
	constructor(private _value: number) {}

	get value() {
		return this._value;
	}

	compare(b: number): number {
		return this._value - b;
	}
}

const l = new LLNode(new ComparableNumber(5));
l.insert(new ComparableNumber(4));
l.insert(new ComparableNumber(3));
l.insert(new ComparableNumber(10));
l.insert(new ComparableNumber(8));
l.insert(new ComparableNumber(2));

function* map<T, V>(iterable: Iterable<T>, fn: (item: T) => V): Iterable<V> {
	for (const value of iterable) {
		yield fn(value);
	}
}

console.log([...map(LLNode.mergeSort(l) || [], (v) => v.value)]);

sortable-link-list.ts

interface Comparable<T> {
	readonly value: T;
	compare(b: T): number;
}

export class LLNode<T> implements Iterable<Comparable<T>> {
	private _next: LLNode<T> | null = null;
	constructor(private _data: Comparable<T>) {}

	insert(data: Comparable<T>): void {
		if (this._next) return this._next.insert(data);
		this._next = new LLNode(data);
	}

	*[Symbol.iterator](): Iterator<Comparable<T>> {
		yield this._data;
		if (this._next) {
			yield* this._next;
		}
	}

	get next() {
		return this._next;
	}

	get data(): Comparable<T> {
		return this._data;
	}

	static mergeSort<T>(node: LLNode<T> | null): LLNode<T> | null {
		if (node === null) return null;
		if (node.next === null) return node;

		const mid = LLNode.getMid(node);

		let left: LLNode<T> | null = node;
		let right = mid.next;
		mid._next = null;

		left = LLNode.mergeSort(left);
		right = LLNode.mergeSort(right);

		return LLNode.merge(left, right);
	}

	static getMid<T>(node: LLNode<T>): LLNode<T> {
		let slow = node;
		let fast = node;

		while (fast.next && fast.next.next) {
			slow = slow.next!;
			fast = fast.next.next;
		}

		return slow;
	}

	static merge<T>(
		left: LLNode<T> | null,
		right: LLNode<T> | null
	): LLNode<T> | null {
		if (left === null) return right;
		if (right === null) return left;

		if (left.data.compare(right.data.value) <= 0) {
			left._next = LLNode.merge(left.next, right);
			return left;
		} else {
			right._next = LLNode.merge(left, right.next);
			return right;
		}
	}
}