1 // Copyright Jerome Benoit. 2023-2024. All Rights Reserved.
4 * Linked list node interface.
6 * @typeParam T - Type of linked list node data.
9 export interface ILinkedListNode
<T
> {
11 next
?: ILinkedListNode
<T
>
12 prev
?: ILinkedListNode
<T
>
17 * Implemented with a doubly linked list.
19 * @typeParam T - Type of deque data.
22 export class Deque
<T
> {
23 private head
?: ILinkedListNode
<T
>
24 private tail
?: ILinkedListNode
<T
>
25 /** The size of the deque. */
27 /** The maximum size of the deque. */
28 public maxSize
!: number
30 public constructor () {
35 * Appends data to the deque.
37 * @param data - Data to append.
38 * @returns The new size of the deque.
40 public push (data
: T
): number {
41 const node
: ILinkedListNode
<T
> = { data
}
42 if (this.tail
== null) {
43 this.head
= this.tail
= node
46 this.tail
= this.tail
.next
= node
48 return this.incrementSize()
52 * Prepends data to the deque.
54 * @param data - Data to prepend.
55 * @returns The new size of the deque.
57 public unshift (data
: T
): number {
58 const node
: ILinkedListNode
<T
> = { data
}
59 if (this.head
== null) {
60 this.head
= this.tail
= node
63 this.head
= this.head
.prev
= node
65 return this.incrementSize()
69 * Pops data from the deque.
71 * @returns The popped data or `undefined` if the deque is empty.
73 public pop (): T
| undefined {
74 if (this.head
== null) {
77 const tail
= this.tail
78 this.tail
= this.tail
?.prev
79 if (this.tail
== null) {
89 * Shifts data from the deque.
91 * @returns The shifted data or `undefined` if the deque is empty.
93 public shift (): T
| undefined {
94 if (this.head
== null) {
97 const head
= this.head
98 this.head
= this.head
.next
99 if (this.head
== null) {
102 delete this.head
.prev
109 * Peeks at the first data.
110 * @returns The first data or `undefined` if the deque is empty.
112 public peekFirst (): T
| undefined {
113 return this.head
?.data
117 * Peeks at the last data.
118 * @returns The last data or `undefined` if the deque is empty.
120 public peekLast (): T
| undefined {
121 return this.tail
?.data
127 public clear (): void {
135 * Returns an iterator for the deque.
137 * @returns An iterator for the deque.
138 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
140 [Symbol
.iterator
] (): Iterator
<T
> {
161 * Returns an backward iterator for the deque.
163 * @returns An backward iterator for the deque.
164 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
166 backward (): Iterable
<T
> {
168 [Symbol
.iterator
]: (): Iterator
<T
> => {
190 private incrementSize (): number {
192 if (this.size
> this.maxSize
) {
193 this.maxSize
= this.size