## TypeScript data structure: Singly linked list

My implementation for singly linked list using TypeScript

Wanna see something cool? Check out Angular Spotify ðŸŽ§

In computer science, a **queue** is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. By convention, the end of the sequence at which elements are added is called the back, **tail**, or rear of the queue, and the end at which elements are removed is called the **head** or front of the queue, analogously to the words used when people line up to wait for goods or services.

The operation of adding an element to the rear of the queue is known as enqueue, and the operation of removing an element from the front is known as dequeue. Other operations may also be allowed, often including a peek or front operation that returns the value of the next element to be dequeued without dequeuing it.

The operations of a queue make it a first-in-first-out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed. A queue is an example of a linear data structure, or more abstractly a sequential collection

Representation of a FIFO (first in, first out) queue

Implement using built-in object as a map, with tail pointer. I came up with this approach to make sure the Big O notation for the dequeue operation. You can implement with the same approach using array instead of object. But to take one element out of an array could take `O(n)`

.

Operation | Description | Big O |
---|---|---|

enqueue(value) | adds value at tail | O(1) |

dequeue() | returns value and removes least recently added element (head) | O(1) |

peek() | returns the value of the next element to be dequeued without dequeuing it | O(1) |

clear() | removes all the element in the queue | O(1) |

isEmpty | checks if the queue is empty | O(1) |

size | checks the size of the queue | O(1) |

You can find the source code in my TS data structure repo

trungk18/typescript-data-structures/tree/master/data-structures/queue

```
import { ObjectType } from '../model/objectType';
export class Queue<T> {
private _queue: ObjectType<T>;
private _head: number;
private _tail: number;
constructor() {
this._queue = {};
this._head = 0;
this._tail = 0;
}
get isEmpty() {
return this.size === 0;
}
get size() {
return this._tail - this._head;
}
enqueue(value: T): void {
this._queue[this._tail] = value;
this._tail++;
}
dequeue(): T {
if (this.isEmpty) {
return undefined;
}
const value = this._queue[this._head];
delete this._queue[this._head];
this._head++;
return value;
}
peek(): T {
if (this.isEmpty) {
return undefined;
}
return this._queue[this._head];
}
clear(): void {
this._queue = {};
this._head = 0;
this._tail = 0;
}
print(): string {
if (this.isEmpty) {
return '';
}
let values = [];
for (let i = this._head; i < this._tail; i++) {
values.unshift(this._queue[i].toString());
}
return values.join(' -> ');
}
}
```

- Trivial implementation using Array - Using
`arr.shift()`

for dequeuing, take`O(n)`

time. That will not meet the requirement of`O(1)`

for dequeuing. - Queue