Danh sách liên kết đơn js

Danh sách được liên kết là một trong những cấu trúc dữ liệu quan trọng nhất mà bạn có thể học.

Trong danh sách được liên kết, mỗi mục chứa một tham chiếu đến mục theo sau nó.

Chúng ta có thể bắt đầu từ đầu danh sách,headvà lặp lại qua tất cả các mục của danh sách, cho đến khi chúng ta đi đến phần cuối [tail].

So với một mảng, các mục không nằm cạnh nhau trong bộ nhớ thực [trong ngôn ngữ lập trình cấp thấp] hoặc không có chỉ mục mà chúng ta có thể sử dụng để truy cập ngẫu nhiên một mục của mảng.

Chúng tôi không thể tham chiếu một mục ở giữa danh sách mà không bắt đầu từ đầu, vì chúng tôi không biết cách tham chiếu nó.

JavaScript không có triển khai danh sách được liên kết, vì vậy chúng tôi sẽ tạo một danh sách ngay bây giờ.

Đầu tiên, chúng tôi tạoItemlớp sẽ được chứa cho mỗi mục trong danh sách:

class Item { next = null value = null constructor[value] { this.value = value } }

Chúng tôi có một con trỏ đến mục tiếp theo trong danh sách và giá trị.

Sau đó, chúng tôi xác định mộtLinkedListlớp sẽ lưu trữ 2 giá trị riêng tư:headvàtail.

Chúng tôi xác định mộtappend[]phương pháp để thêm một mục vào danh sách. Nếu đó là mục đầu tiên chúng tôi thêm vào, thì mục đó vừa là phần đầu vừa là phần cuối của danh sách. Nếu không, chúng tôi tạo mục và chúng tôi gán nó chonextthuộc tính của mục đuôi:

class LinkedList { #head = null #tail = null append = [value] => { const item = new Item[value] if [!this.#head] { this.#head = item this.#tail = item return } this.#tail.next = item this.#tail = item } size = [] => { let count = 1 let item = this.#head if [!item] return 0 while [[item = item.next]] { count++ } return count } }

Đây là cách chúng ta có thể sử dụng nó:

const list = new LinkedList[] list.append[1] list.append[2] list.append[3]

Chúng ta có thể thêm mộtsize[]phương thức để trả về kích thước của danh sách:

class LinkedList { //... size = [] => { let count = 1 let item = this.#head if [!item] return 0 while [[item = item.next]] { count++ } return count } }

const list = new LinkedList[] list.size[] //0 list.append[1] list.size[] //1 list.append[2] list.append[3] list.size[] //3

Làm thế nào chúng ta có thể tìm thấy một mục trong danh sách, theo giá trị? Hãy triển khai một phương pháp để làm như vậy:

class LinkedList { //... find = [value] => { let count = 1 let item = this.#head if [!item] return null while [[item = item.next]] { if [item.value === value] { return item } } return null } }

const list = new LinkedList[] list.append[1] list.append[2] list.append[3] const item = list.find[2] //item.value === 2

Điều gì sẽ xảy ra nếu chúng ta muốn chèn một mục vào danh sách liên kết? Chúng tôi đã cóappend[]để chèn mục vào cuối danh sách. Hãy triển khai một cách để chèn mục tại một vị trí cụ thể:

class LinkedList { //... insert = [index, value] => { //check for out-of-bounds values if [index < 0 || index > this.size[]] return const node = new Item[value] let current = this.#head let previous if [index === 0] { //first position node.next = current this.#head = node } else { let i = 0 while [i++ < index] { previous = current current = current.next } node.next = current previous.next = node } } }

const list = new LinkedList[] list.append[1] list.append[2] list.append[3] list.insert[2, a] list.size[] //4

Một loại danh sách liên kết khác là danh sách liên kết kép, trong đó mỗi mục cũng chứa một liên kết đến phần tử trước đó.

Các hướng dẫn js khác:

Video liên quan

Bài Viết Liên Quan

Toplist mới

Bài mới nhất

Chủ Đề