programming javascript

Danh sách 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, 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à các nút] chứa hai mục. dữ liệu được lưu trữ và một 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à đầ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ế của nó so với 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 đôi. 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 chúng ta vừa tạo. Đầu tiên, chúng tôi tạo hai nút danh sách,

class ListNode {
    constructor[data] {
        this.data = data
        this.next = null                
    }
}

0 và

class ListNode {
    constructor[data] {
        this.data = data
        this.next = null                
    }
}

1 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

class ListNode {
    constructor[data] {
        this.data = data
        this.next = null                
    }
}

let list = new LinkedList[node1]

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

________số 8

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

kích thước[]
xa lạ[]
getLast[]
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. xa lạ[]

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

class ListNode {
    constructor[data] {
        this.data = data
        this.next = 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

class ListNode {
    constructor[data] {
        this.data = data
        this.next = null                
    }
}

4. getFirst[]

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

class ListNode {
    constructor[data] {
        this.data = data
        this.next = null                
    }
}

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 tôi cũng đã thảo luận về các loại danh sách được liên kết khác nhau cũng như những ưu điểm và nhược điểm chung 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?

QUẢNG CÁO

Sarah Chima Atuonwu

Tôi là một kỹ sư phần mềm quan tâm đến việc làm cho tất cả mọi người có thể truy cập web. Tôi thích chia sẻ kiến thức nên tôi viết về những điều tôi học được và những điều tôi cần học

Nếu bạn đọc đến đây, hãy tweet cho tác giả để cho họ thấy bạn quan tâm. Tweet một lời cảm ơn

Học cách viết mã miễn phí. Chương trình giảng dạy mã nguồn mở của freeCodeCamp đã giúp hơn 40.000 người có được việc làm với tư cách là nhà phát triển. Bắt đầu