Giới thiệu

Là một kiểu dữ liệu gồm đầu (head), đuôi (tail) và độ dài (length)

Linked list gồm nhiều node, 1 node có 1 giá trị và 1 con trỏ trỏ tới node khác hoặc null

Có 2 loại linked list:

• Singly linked list (danh sách liên kết đơn)
• Doubly linked list (danh sách liên kết đôi)

Singly Linked lists (danh sách liên kết đơn)

Khởi tạo

Tạo 1 class cho node của Singly linked list

class NodeSinglyLinkedList { val: string; next: NodeSinglyLinkedList | null; constructor(val: string) { this.val = val; this.next = null; }
}

Tạo 1 class chứa các method của Singly Linked list

class SinglyLinkedList { head: NodeSinglyLinkedList | null; tail: NodeSinglyLinkedList | null; length: number; constructor() { this.head = null; this.tail = null; this.length = 0; } push(val){} pop(){} unshift(val){} shift(){} get(val){} insert(val, position){} remove(position){} }

Khởi tạo các method

push

 push(val) { const newNode = new NodeSinglyLinkedList(val); if (!this.head) { this.head = newNode; this.tail = this.head; } else { this.tail.next = newNode; this.tail = newNode; } this.length++; return this; }

pop

 pop() { if (!this.head) { return undefined; } let current = this.head; let newTail = current; while (current.next) { newTail = current; current = current.next; } this.tail = newTail; this.tail.next = null; this.length--; return this; }

unshift

 unshift(val) { const newNode = new NodeSinglyLinkedList(val); if (!this.tail) { this.head = newNode; this.tail = this.head; } else { newNode.next = this.head; this.head = newNode; } this.length++; return this; }

shift

 shift() { if (!this.head) { return undefined; } else { const currentHead = this.head; this.head = currentHead.next; } this.length--; return this; }

get

 get(position) { if (position < 0 || position > this.length) return null; let counter = 0; let head = this.head; while (counter < this.length) { if (counter === position) { return head; } head = head.next; counter++; } }

insert

 insert(val, position) { if (position < 0 || position > this.length) return null; const newNode = new NodeSinglyLinkedList(val); if (position === 0) { return this.unshift(val); } if (position === this.length) { return this.push(val); } const prevNode = this.get(position - 1); const prevNodeNext = prevNode.next; prevNode.next = newNode; newNode.next = prevNodeNext; }

remove

 remove(position) { if (position < 0 || position > this?.length) return null; if (position === 0) { return this.shift(); } if (position === this.length - 1) { return this.pop(); } const currentNode = this.get(position); const prevNode = this.get(position - 1); prevNode.next = currentNode.next; return this; }

Doubly Linked lists (danh sách liên kết đôi)

Khởi tạo

Tạo 1 class cho node của Singly linked list

class NodeDoublyLinkedList { val: string; next: NodeDoublyLinkedList | null; prev: NodeDoublyLinkedList | null; constructor(val: string) { this.val = val; this.next = null; this.prev = null; }
}

Tạo 1 class chứa các method của Singly Linked list

class DoublyLinkedList { head: NodeDoublyLinkedList | null; tail: NodeDoublyLinkedList | null; length: number; constructor() { this.head = null; this.tail = null; this.length = 0; } push(val){} pop(){} unshift(val){} shift(){} get(val){} insert(val, position){} remove(position){} }

Khởi tạo các method

push

 push(val) { const newNode = new NodeDoublyLinkedList(val); if (!this.head) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; newNode.prev = this.tail; this.tail = newNode; } this.length++; return this; }

pop

 pop() { if (!this.head) { return undefined; } const newTail = this.tail.prev; this.tail.next = null; this.tail = newTail; this.length--; return this; }

unshift

 unshift(val) { const newNode = new NodeDoublyLinkedList(val); if (!this.tail) { this.head = newNode; this.tail = this.head; } else { newNode.next = this.head; this.head.prev = newNode; this.head = newNode; } this.length++; return this; }

shift

 shift() { if (!this.head) { return undefined; } else { const currentHead = this.head; this.head = currentHead.next; this.head.prev = null; } this.length--; return this; }

get

 get(position) { if (position < 0 || position > this.length) return null; let counter = 0; let head = this.head; while (counter < this.length) { if (counter === position) { return head; } head = head.next; counter++; } }

insert

 insert(val, position) { if (position < 0 || position > this.length) return null; const newNode = new NodeDoublyLinkedList(val); if (position === 0) { return this.unshift(val); } if (position === this.length) { return this.push(val); } const currentNode = this.get(position); const prevNode = this.get(position - 1); prevNode.next = newNode; newNode.prev = prevNode; newNode.next = currentNode; currentNode.prev = newNode; this.length++; return this; }

remove

 remove(position) { if (position < 0 || position > this?.length) return null; if (position === 0) { return this.shift(); } if (position === this.length - 1) { return this.pop(); } const prevNode = this.get(position - 1); const nextNode = this.get(position + 1); prevNode.next = nextNode; nextNode.prev = prevNode; this.length--; return this; }

Kết luận

Từ việc triền khai các method ở trên ta có được bảng so sánh độ phức tạp của 2 loại linked list như sau: