Linked List
June 24, 2025
04:33 AM
No headings found
Loading content...
Related Posts
Theory Data Structure And Algorithms
No headings found
Related Posts
Theory Data Structure And Algorithms
Approach
Node để biểu diễn từng node, mỗi node chứa value và next.LinkedList sẽ có hai thuộc tính chính: head (node đầu) và tail (node cuối), cùng một biến đếm size.nextSolution
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}