Cách triển khai Danh sách được liên kết trong JavaScript

Nếu bạn đang học cấu trúc dữ liệu, danh sách liên kết là một cấu trúc dữ liệu bạn nên biết. Nếu bạn không thực sự hiểu nó hoặc cách nó được triển khai trong JavaScript, thì bài viết này ở đây để giúp bạn.

Trong bài viết này, chúng ta sẽ thảo luận về danh sách liên kết là gì, nó khác với mảng như thế nào và cách triển khai nó trong JavaScript. Bắt đầu nào.

Danh sách liên kết là gì?

Danh sách liên kết là một cấu trúc dữ liệu tuyến tính tương tự như một mảng. Tuy nhiên, không giống như mảng, các phần tử không được lưu trữ trong một vị trí hoặc chỉ mục bộ nhớ cụ thể. Thay vào đó, mỗi phần tử là một đối tượng riêng biệt có chứa một con trỏ hoặc một liên kết đến đối tượng tiếp theo trong danh sách đó.

Mỗi phần tử (thường được gọi là nút) chứa hai mục: dữ liệu được lưu trữ và liên kết đến nút tiếp theo. Dữ liệu có thể là bất kỳ loại dữ liệu hợp lệ nào. Bạn có thể thấy điều này được minh họa trong sơ đồ bên dưới.

Điểm vào danh sách liên kết được gọi là phần đầu. Đầu là tham chiếu đến nút đầu tiên trong danh sách liên kết. Nút cuối cùng trong danh sách trỏ đến null. Nếu một danh sách trống, phần đầu là một tham chiếu null.

Trong JavaScript, một danh sách được liên kết trông như thế này:

const list = {
    head: {
        value: 6
        next: {
            value: 10                                             
            next: {
                value: 12
                next: {
                    value: 3
                    next: null	
                    }
                }
            }
        }
    }
};

Ưu điểm của Danh sách liên kết

• Có thể dễ dàng xóa hoặc thêm các nút khỏi danh sách liên kết mà không cần tổ chức lại toàn bộ cấu trúc dữ liệu. Đây là một lợi thế mà nó có trên mảng.

Nhược điểm của danh sách liên kết

• Hoạt động tìm kiếm chậm trong danh sách được liên kết. Không giống như mảng, không được phép truy cập ngẫu nhiên các phần tử dữ liệu. Các nút được truy cập tuần tự bắt đầu từ nút đầu tiên.
• Nó sử dụng nhiều bộ nhớ hơn mảng vì lưu trữ các con trỏ.

Các loại danh sách liên kết

Có ba loại danh sách liên kết:

• Danh sách liên kết đơn: Mỗi nút chỉ chứa một con trỏ tới nút tiếp theo. Đây là những gì chúng ta đã nói về cho đến nay.
• Danh sách liên kết kép: Mỗi nút chứa hai con trỏ, một con trỏ tới nút tiếp theo và một con trỏ tới nút trước đó.
• Danh sách liên kết vòng: Danh sách liên kết vòng là một biến thể của danh sách liên kết trong đó nút cuối cùng trỏ đến nút đầu tiên hoặc bất kỳ nút nào khác trước nó, do đó tạo thành một vòng lặp.

Triển khai Nút danh sách trong JavaScript

Như đã nêu trước đó, một nút danh sách chứa hai mục: dữ liệu và con trỏ tới nút tiếp theo. Chúng ta có thể triển khai nút danh sách trong JavaScript như sau:

class ListNode {
    constructor(data) {
        this.data = data
        this.next = null                
    }
}

Triển khai Danh sách được liên kết trong JavaScript

Đoạn mã dưới đây cho thấy việc thực hiện một lớp danh sách được liên kết với một hàm tạo. Lưu ý rằng nếu nút đầu không được thông qua, đầu được khởi tạo thành null.

class LinkedList {
    constructor(head = null) {
        this.head = head
    }
}

Để tất cả chúng cùng nhau

Hãy tạo một danh sách liên kết với lớp mà chúng ta vừa tạo. Đầu tiên, chúng tôi tạo hai nút danh sách, node1 và node2 và một con trỏ từ nút 1 đến nút 2.

let node1 = new ListNode(2)
let node2 = new ListNode(5)
node1.next = node2

Tiếp theo, chúng ta sẽ tạo một Linked list với node1.

let list = new LinkedList(node1)

Hãy thử truy cập vào các nút trong danh sách mà chúng ta vừa tạo.

console.log(list.head.next.data) //returns 5

Một số phương thức LinkedList

Tiếp theo, chúng tôi sẽ triển khai bốn phương thức trợ giúp cho danh sách được liên kết. Họ đang:

1. kích thước()
2. xa lạ()
3. getLast()
4. getFirst()

1. kích thước()

Phương thức này trả về số nút có trong danh sách liên kết.

size() {
    let count = 0; 
    let node = this.head;
    while (node) {
        count++;
        node = node.next
    }
    return count;
}

2. xóa()

Phương pháp này làm trống danh sách.

clear() {
    this.head = null;
}

3. getLast()

Phương thức này trả về nút cuối cùng của danh sách liên kết.

getLast() {
    let lastNode = this.head;
    if (lastNode) {
        while (lastNode.next) {
            lastNode = lastNode.next
        }
    }
    return lastNode
}

4. getFirst()

Phương thức này trả về nút đầu tiên của danh sách liên kết.

getFirst() {
    return this.head;
}

Tóm lược

Trong bài viết này, chúng ta đã thảo luận danh sách liên kết là gì và cách triển khai danh sách này trong JavaScript. Chúng ta cũng đã thảo luận về các loại danh sách liên kết khác nhau cũng như những ưu điểm và nhược điểm tổng thể của chúng.

Tôi hy vọng bạn thích đọc nó.

Bạn muốn được thông báo khi tôi xuất bản một bài viết mới? Bấm vào đây.