Vừa mới tốt nghiệp khóa đào tạo mã hóa, tôi đã đi sâu vào nghiên cứu cấu trúc dữ liệu và thuật toán để nâng cao kiến ​​thức nền tảng của mình. Danh sách được liên kết là một cấu trúc dữ liệu tương đối đơn giản, nhưng là cơ sở cho các cấu trúc dữ liệu phức tạp hơn trong tương lai. Bài viết này sẽ thảo luận về các danh sách được liên kết - điểm mạnh, điểm yếu và cách triển khai chúng.

Cấu trúc dữ liệu, nói một cách đơn giản, là cách tổ chức và lưu giữ dữ liệu một cách hiệu quả

Cấu trúc dữ liệu là gì?

Cấu trúc dữ liệu, nói một cách đơn giản, là cách để tổ chức và lưu giữ dữ liệu một cách hiệu quả. Những thứ này cho phép chúng tôi lưu giữ thông tin để chúng tôi có thể truy cập chúng sau này - tìm kiếm một mặt hàng cụ thể hoặc sắp xếp chúng theo một thứ tự nhất định hoặc thậm chí quản lý các tập dữ liệu lớn. JavaScript có cấu trúc dữ liệu mà bạn có thể rất quen thuộc - mảng và đối tượng. Đây là những cấu trúc dữ liệu nguyên thủy có nguồn gốc từ ngôn ngữ. Cấu trúc dữ liệu không nguyên thủy là cấu trúc dữ liệu được định nghĩa bởi người lập trình. Ví dụ bao gồm ngăn xếp, hàng đợi, cây, đồ thị và bảng băm.

Danh sách được 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 chứa các phần tử theo thứ tự tuần tự. Nghe có vẻ quen? Chúng tương tự như mảng nhưng không hoàn toàn giống nhau. Mảng được lập chỉ mục bằng 0 , có nghĩa là mỗi chỉ mục được ánh xạ tới một giá trị và phần tử đầu tiên của mảng bắt đầu từ chỉ số 0. Bạn có thể dễ dàng kéo các phần tử từ mảng, miễn là bạn biết chỉ mục.

Mặt khác, một danh sách liên kết bao gồm các nút trỏ đến các nút khác. Mỗi nút chỉ biết chính nó và nút tiếp theo. Là một cấu trúc dữ liệu tuyến tính, các mục được sắp xếp theo thứ tự. Bạn có thể nghĩ về nó như một đoàn tàu - mỗi toa xe lửa được kết nối với toa xe lửa tiếp theo, v.v. Danh sách được liên kết không được lập chỉ mục , vì vậy bạn không thể truy cập trực tiếp vào phần tử thứ 5. Bạn phải bắt đầu từ đầu, chuyển sang phần tiếp theo và chuyển sang phần tiếp theo cho đến khi bạn tìm thấy phần tử thứ 5. Nút đầu tiên được gọi là đầu, và nút cuối cùng được gọi là đuôi. Có nhiều loại danh sách liên kết - danh sách liên kết đơn, danh sách liên kết kép và danh sách liên kết vòng. Vì lợi ích của bài viết này, tôi sẽ tập trung vào danh sách được liên kết đơn lẻ.

Việc truy cập các phần tử trong toàn mảng dễ dàng hơn, nhưng điều đó phải trả giá.

Tại sao lại sử dụng danh sách được liên kết qua mảng?

Bạn có thể tự hỏi - nhưng tại sao lại sử dụng điều này nếu tôi có thể truy cập trực tiếp vào các phần tử bằng mảng? Đây là sự thật! Việc truy cập các phần tử trong toàn mảng dễ dàng hơn, nhưng điều đó phải trả giá.

Mảng được lập chỉ mục - vì vậy bất cứ khi nào bạn cần xóa một phần tử từ đầu hoặc giữa, tất cả các chỉ số sau đây đều cần được dịch chuyển. Điều này cũng đúng nếu bạn cần chèn một phần tử - tất cả các phần tử sau cần được lập chỉ mục lại. Khi chèn hoặc xóa các phần tử khỏi danh sách liên kết, bạn không cần lập chỉ mục lại - tất cả những gì nó quan tâm là nút mà nó trỏ đến .

Triển khai một danh sách được liên kết đơn lẻ

Có nhiều loại danh sách được liên kết - đơn lẻ, kép và vòng tròn. Danh sách liên kết đơn là một loại danh sách được liên kết trong đó mỗi nút có một giá trị và một con trỏ đến nút tiếp theo (null nếu đó là nút đuôi). Mặt khác, danh sách được liên kết kép có một con trỏ bổ sung đến nút trước đó. Danh sách liên kết hình tròn là nơi nút đuôi trỏ trở lại nút đầu.

Lưu ý: Nếu bạn là người học trực quan, VisuAlgo là một nơi tuyệt vời để chơi xung quanh và xem cấu trúc dữ liệu trải qua những thay đổi.

Nếu bạn muốn bỏ qua phần tiếp theo để có mã hoàn chỉnh: hãy xem ý chính của GitHub này .

Tạo nút

Hãy bắt đầu bằng cách xây dựng một nút để sử dụng. Nó sẽ có một giá trị và một con trỏ tiếp theo, sẽ chỉ ra hàng xóm tiếp theo của nó.

class Node {    
    constructor(val) {        
        this.val = val;        
        this.next = null;    
    }
}

Chúng ta sẽ bắt đầu bằng cách xây dựng một lớp có tên là SinglyLinkedList và tạo cơ sở cho nó về phần đầu, phần đuôi và độ dài của danh sách.

class SinglyLinkedList {    
      constructor() {        
          this.head = null;
          this.tail = null;
          this.length = 0;
      }
}

Để thêm một nút vào cuối, chúng tôi sẽ kiểm tra xem có phần đầu đã được khai báo trong danh sách hay không. Nếu không, hãy đặt đầu và đuôi là nút mới tạo. Nếu đã có thuộc tính head, hãy đặt thuộc tính tiếp theo ở phần đuôi thành nút mới và thuộc tính đuôi là nút mới. Chúng tôi sẽ tăng chiều dài lên 1.

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

Để loại bỏ một nút ở cuối, trước tiên chúng ta phải kiểm tra xem có các nút trong danh sách hay không. Nếu có các nút, thì chúng ta phải lặp qua danh sách cho đến khi chúng ta đến đuôi. Chúng tôi sẽ đặt thuộc tính tiếp theo của nút thứ hai đến nút cuối cùng là null, đặt thuộc tính đuôi cho nút đó, giảm độ dài đi 1 và trả về giá trị của nút đã loại bỏ.

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

Để loại bỏ nút ngay từ đầu, chúng tôi kiểm tra xem có các nút trong danh sách hay không. Chúng tôi sẽ lưu trữ thuộc tính head hiện tại trong một biến và đặt head là nút tiếp theo của head hiện tại. Giảm độ dài đi 1 và trả về giá trị của nút bị xóa.

shift() {
        if (!this.head) return undefined
        var oldHead = this.head;
        this.head = oldHead.next;
        this.length--
        if (this.length===0) {
            this.head = null;
            this.tail = null;
        }
        return oldHead
}

Để thêm một nút vào đầu, trước tiên chúng ta tạo nút và kiểm tra xem có thuộc tính head trong danh sách hay không. Nếu vậy, hãy đặt thuộc tính tiếp theo của nút mới tạo thành phần đầu hiện tại, đặt phần đầu thành nút mới và tăng độ dài.

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

Để truy cập một nút dựa trên vị trí của nó trong danh sách, trước tiên chúng ta sẽ kiểm tra xem chỉ mục có phải là chỉ mục hợp lệ hay không. Sau đó, chúng ta sẽ lặp qua danh sách, đồng thời giữ một biến bộ đếm. Khi biến bộ đếm khớp với chỉ mục, chúng tôi sẽ trả về nút tìm thấy

get(idx) {
        if (idx < 0 || idx >= this.length) return null
        var counter = 0;
        var current = this.head
        while (counter !== idx) {
            current = current.next;
            counter++;
        }
        return current;
}

Để thay đổi một nút dựa trên vị trí của nó, trước tiên, chúng ta tìm nút, sử dụng phương thức get và đặt giá trị thành giá trị mới.

set(idx, val) {
        var foundNode = this.get(idx)
        if (foundNode) {
            foundNode.val = val
            return true;
        }
        return false;
}

Để chèn một nút, trước tiên chúng ta kiểm tra chỉ mục. Nếu nó bằng 0, chúng tôi sử dụng phương pháp unshift. Nếu nó bằng chiều dài, chúng tôi đẩy nó vào danh sách. Nếu không, chúng ta sẽ lấy nút before bằng cách sử dụng phương thức get ở mức thấp hơn chỉ mục một. Về cơ bản, chúng ta cần theo dõi nút trước và sau chỉ mục đã chọn để đảm bảo các con trỏ của chúng ta hướng đến đúng nút.

insert(idx, val) {
        if (idx < 0 || idx > this.length) return false;
        if (idx === 0) {
            this.unshift(val)
            return true;
        };
        if (idx === this.length) {
            this.push(val);
            return true;
        };
        var newNode = new Node(val);
        var beforeNode = this.get(idx-1);
        var afterNode = beforeNode.next;
        beforeNode.next = newNode;
        newNode.next = afterNode;
        this.length++;
        return true;
}

Để loại bỏ một nút dựa trên vị trí, chúng tôi sẽ sử dụng lại phương thức get và sử dụng nguyên tắc tương tự mà chúng tôi đã sử dụng để chèn một nút. Bằng cách theo dõi nút trước đó đến chỉ mục đã chọn, chúng ta có thể điều động các con trỏ của mình.

remove(idx) {
        if (idx < 0 || idx > this.length) return undefined;
        if (idx === this.length-1) {
            this.pop()
        }
        if (idx === 0) {
            this.shift()
        }
        var prevNode = this.get(idx-1)
        var removeNode = prevNode.next
        prevNode.next = removeNode.next
        this.length--;
        return removeNode;
}

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

Lợi ích của việc sử dụng danh sách liên kết là khả năng chèn và loại bỏ các phần tử một cách nhanh chóng. Vì danh sách được liên kết không được lập chỉ mục nên việc chèn các phần tử tương đối nhanh chóng và dễ dàng.

Việc thêm vào cuối danh sách được liên kết chỉ cần yêu cầu đuôi cũ trỏ đến nút mới và thuộc tính đuôi phải được đặt thành nút mới. Việc thêm vào đầu danh sách được liên kết là cùng một tiền đề, nhưng nút mới trỏ đến phần đầu cũ và thuộc tính head được đặt thành nút mới. Về cơ bản các hành động giống nhau, do đó nội tiếp là O (1).

Lưu ý: Việc chèn vào giữa danh sách được liên kết, yêu cầu tìm kiếm thông qua để tìm nút của bạn (O (N)) và sau đó chèn nút (O (1)).

Xóa một nút khỏi danh sách liên kết có thể dễ dàng… nhưng cũng không. Điều này phụ thuộc vào nơi. Việc xóa một nút khỏi đầu danh sách rất đơn giản - nút thứ hai trở thành phần đầu mới và chúng tôi đặt con trỏ tiếp theo của phần đầu cũ thành null. Việc xóa khỏi phần cuối phức tạp hơn vì điều này đòi hỏi phải đi qua toàn bộ danh sách và dừng lại ở nút thứ hai đến nút cuối cùng. Trường hợp xấu nhất O (N) và trường hợp tốt nhất O (1).

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

Điểm yếu của danh sách liên kết là do nó thiếu lập chỉ mục. Bởi vì bạn không thể truy cập trực tiếp các phần tử, điều này làm cho việc tìm kiếm và truy cập các phần tử khó hơn.

Tìm kiếm & Truy cập một nút trong danh sách được liên kết yêu cầu bắt đầu từ đầu danh sách và đi theo đường dẫn của đường dẫn xuống danh sách. Nếu chúng ta đang tìm kiếm nút ở cuối danh sách, chúng ta sẽ phải xem qua toàn bộ danh sách được liên kết, làm cho độ phức tạp về thời gian là O (N) một cách hiệu quả. Khi danh sách phát triển, số lượng hoạt động cũng tăng lên. So với mảng có quyền truy cập ngẫu nhiên - cần thời gian liên tục để truy cập một phần tử.

Đó là nó!

Danh sách được liên kết là lựa chọn thay thế tuyệt vời cho mảng khi chèn và xóa ở đầu là những hành động quan trọng. Mảng được lập chỉ mục, trong khi danh sách được liên kết thì không. Danh sách được liên kết cũng là cấu trúc dữ liệu nền tảng mà các ngăn xếp và hàng đợi được xây dựng dựa trên, mà tôi sẽ thảo luận trong một bài viết sau. Nếu bạn đã hoàn thành nó ở đây, xin chúc mừng bạn và tôi hy vọng bạn đã học được một chút tiện ích cùng với hành trình lập trình của mình!

Người giới thiệu