Linked List

1class Node<T> {
2	value: T;
3	next: Node<T> | null = null;
4	constructor(value: T) {
5		this.value = value;
6	}
7}
8export default class LinkedList<T> {
9  head: Node<T> | null;
10  tail: Node<T> | null;
11  _size: number;
12  constructor() {
13    this.head = null;
14    this.tail = null;
15    this._size = 0;
16  }
17
18  /**
19   * Adds an item to the head of the linked list.
20   * @param {T} value The item to be added to the head of the list.
21   */
22  insertHead(value: T): void {
23	  const node = new Node(value);
24	  node.next = this.head;
25	  this.head = node;
26	  if(!this.tail) this.tail = node;
27	  this._size++
28  }
29
30  /**
31   * Adds an item to the tail of the linked list.
32   * @param {T} value The item to be added to the tail of the list.
33   */
34  insertTail(value: T): void {
35    const node = new Node(value);
36    if(!this.head) this.head = this.tail = node;
37    else {
38	    if(this.tail) this.tail.next = node;
39	    this.tail = node;
40    }
41    this._size++
42  }
43
44  /**
45   * Remove the item in the given index and return its value or `undefined` if index is out of bounds.
46   * @param {number} i The index of the item to be removed.
47   * @return {T | undefined} The value at index i if it exists, `undefined` otherwise.
48   */
49  remove(i: number): T | undefined {
50    if(i < 0 || i >= this._size || !this.head) return undefined;
51    let removed_value: T;
52    if(i === 0) {
53	    removed_value = this.head.value;
54	    this.head = this.head.next;
55	    if(!this.head) this.tail = null
56    } else {
57	    let prev = this.head;
58	    for(let idx = 0; idx < i - 1; idx++) {
59		    prev = prev.next!;
60	    }
61	    const to_remove = prev.next;
62	    removed_value = to_remove.value;
63	    prev.next = to_remove.next;
64	    if(to_remove === this.tail) this.tail = prev;
65    }
66    this._size--
67    return removed_value
68  }
69
70  /**
71   * Return the value of the item at the given index or `undefined` if index is out of bounds.
72   * @param {number} i The index of the value to retrieve.
73   * @return {T | undefined} The value at index i if it exists, `undefined` otherwise.
74   */
75  get(i: number): T | undefined {
76    if(i < 0 || i >= this._size) return undefined;
77    let curr = this.head;
78    let idx = 0;
79    while(curr && idx < i) {
80	    curr = curr.next;
81	    idx++
82    }
83    return curr?.value
84  }
85
86  /**
87   * Return an array containing all the values in the linked list from head to tail.
88   * @return {Array<T>} The array of all values in the linked list from head to tail.
89   */
90  toArray(): Array<T> {
91    const arr: T[] = [];
92    let curr =this.head;
93    while(curr) {
94	    arr.push(curr.value)
95	    curr= curr.next;
96    }
97    return arr
98  }
99
100  /**
101   * Return the number of elements in the linked list.
102   * @return {number} The length of the list.
103   */
104  length(): number {
105    return this._size;
106  }
107}