-// Copyright Jerome Benoit. 2023. All Rights Reserved.
+// Copyright Jerome Benoit. 2023-2024. All Rights Reserved.
-export class Node<T> {
- public value: T
- public next?: Node<T>
- public prev?: Node<T>
-
- public constructor (value: T) {
- this.value = value
- }
+/**
+ * Linked list node interface.
+ *
+ * @typeParam T - Type of linked list node data.
+ * @internal
+ */
+export interface ILinkedListNode<T> {
+ data: T
+ next?: ILinkedListNode<T>
+ prev?: ILinkedListNode<T>
}
/**
* Deque.
* Implemented with a doubly linked list.
*
- * @typeParam T - Type of deque values.
+ * @typeParam T - Type of deque data.
+ * @internal
*/
export class Deque<T> {
- private head?: Node<T>
- private tail?: Node<T>
+ private head?: ILinkedListNode<T>
+ private tail?: ILinkedListNode<T>
/** The size of the deque. */
public size!: number
/** The maximum size of the deque. */
}
/**
- * Appends a value to the deque.
+ * Appends data to the deque.
*
- * @param value - Value to append.
- * @returns The new size of the queue.
+ * @param data - Data to append.
+ * @returns The new size of the deque.
*/
- public push (value: T): number {
- const node = new Node(value)
+ public push (data: T): number {
+ const node: ILinkedListNode<T> = { data }
if (this.tail == null) {
this.head = this.tail = node
} else {
}
/**
- * Prepends a value to the deque.
+ * Prepends data to the deque.
*
- * @param value - Value to prepend.
- * @returns The new size of the queue.
+ * @param data - Data to prepend.
+ * @returns The new size of the deque.
*/
- public unshift (value: T): number {
- const node = new Node(value)
+ public unshift (data: T): number {
+ const node: ILinkedListNode<T> = { data }
if (this.head == null) {
this.head = this.tail = node
} else {
}
/**
- * Pops a value from the deque.
+ * Pops data from the deque.
*
- * @returns The popped value or `undefined` if the deque is empty.
+ * @returns The popped data or `undefined` if the deque is empty.
*/
public pop (): T | undefined {
if (this.head == null) {
- return undefined
+ return
}
const tail = this.tail
- this.tail = (this.tail as Node<T>).prev
+ this.tail = this.tail?.prev
if (this.tail == null) {
- this.head = undefined
+ delete this.head
} else {
- this.tail.next = undefined
+ delete this.tail.next
}
--this.size
- return tail?.value
+ return tail?.data
}
/**
- * Shifts a value from the deque.
+ * Shifts data from the deque.
*
- * @returns The shifted value or `undefined` if the deque is empty.
+ * @returns The shifted data or `undefined` if the deque is empty.
*/
public shift (): T | undefined {
if (this.head == null) {
- return undefined
+ return
}
const head = this.head
this.head = this.head.next
if (this.head == null) {
- this.tail = undefined
+ delete this.tail
} else {
- this.head.prev = undefined
+ delete this.head.prev
}
--this.size
- return head?.value
+ return head.data
}
/**
- * Peeks at the first value.
- * @returns The first value or `undefined` if the deque is empty.
+ * Peeks at the first data.
+ * @returns The first data or `undefined` if the deque is empty.
*/
public peekFirst (): T | undefined {
- return this.head?.value
+ return this.head?.data
}
/**
- * Peeks at the last value.
- * @returns The last value or `undefined` if the deque is empty.
+ * Peeks at the last data.
+ * @returns The last data or `undefined` if the deque is empty.
*/
public peekLast (): T | undefined {
- return this.tail?.value
+ return this.tail?.data
}
/**
* Clears the deque.
*/
public clear (): void {
- this.head = undefined
- this.tail = undefined
+ delete this.head
+ delete this.tail
this.size = 0
this.maxSize = 0
}
}
}
const ret = {
- value: node.value,
+ value: node.data,
done: false
}
- node = node.next as Node<T>
+ node = node.next
return ret
}
}
}
}
const ret = {
- value: node.value,
+ value: node.data,
done: false
}
- node = node.prev as Node<T>
+ node = node.prev
return ret
}
}