Skip to content

Instantly share code, notes, and snippets.

@another-guy
Last active October 20, 2024 05:10
Show Gist options
  • Save another-guy/ebaaa8bea039aef32b7f0227ba1676ca to your computer and use it in GitHub Desktop.
Save another-guy/ebaaa8bea039aef32b7f0227ba1676ca to your computer and use it in GitHub Desktop.
LeetCode: linked-list-based queue, more performant than default JS's array-based one
function createQueue() {
let head = undefined;
let tail = head;
function isEmpty() { return head === undefined; }
function push(value) {
const newElement = { next: undefined, value };
if (!tail) {
head = newElement;
tail = newElement;
} else {
tail.next = newElement;
tail = newElement;
}
}
function pop() {
const { value } = head;
head = head.next;
if (!head) tail = undefined;
return value;
}
function peek() { return head.value; }
function some(predicate) {
let current = head;
while (current) {
if (predicate(current.value)) return true;
current = current.next;
}
return false;
}
function every(predicate) {
return !some(v => !predicate(v));
}
return { isEmpty, push, pop, peek, some, every };
};
// ts
function createQueue<T>() {
let head: Elem<T> | undefined = undefined;
let tail: Elem<T> | undefined = head;
function isEmpty(): boolean { return head === undefined; }
function push(value: T) {
const newElement = { next: undefined, value };
if (!tail) {
head = newElement;
tail = newElement;
} else {
tail.next = newElement;
tail = newElement;
}
}
function pop(): T {
if (!head) throw new Error('No head');
const { value } = head;
head = head.next;
if (!head) tail = undefined;
return value;
}
function peek(): T | undefined { return head?.value; }
function some(predicate: (value: T) => boolean): boolean {
let current = head;
while (current) {
if (predicate(current.value)) return true;
current = current.next;
}
return false;
}
function every(predicate: (value: T) => boolean): boolean {
return !some(v => !predicate(v));
}
return { isEmpty, push, pop, peek, some, every };
};
interface Elem<T> {
next?: Elem<T>;
value: T;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment