Giới thiệu về danh sách được liên kết qua JavaScript - Phần 1: Tổng quan
Khi ứng dụng và dữ liệu ngày càng trở nên phức tạp, việc bị hạn chế trong các mảng cơ bản sẽ trở thành một nút thắt lớn trong hiệu suất và những gì bạn có thể hoàn thành. Ta cần phát triển một thứ gì đó lớn hơn kiểu dữ liệu cơ bản nhất mà JavaScript cung cấp cho ta . Với danh sách được liên kết, ta có thể xây dựng nền tảng để học các cấu trúc dữ liệu và thuật toán nâng cao hơn.
Ý tưởng
Danh sách được liên kết là một cách đặc biệt sử dụng các lớp để tạo chuỗi các đối tượng được kết nối. Mỗi đối tượng này 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 đó.
Mặc dù các mảng cho phép bạn truy cập trực tiếp vào một mục bằng index của nó, luôn là O(1) , các node của ta không có index , vì vậy ta cần bắt đầu từ phần đầu hoặc phần cuối của danh sách và sử dụng các con trỏ để tìm kiếm qua từng mục mà ta muốn thay đổi, do đó O(n) .
Tại sao ta lại muốn có một danh sách được liên kết trên một mảng? Mảng vượt trội hơn khi tìm kiếm và phân loại, vì dễ dàng truy cập trực tiếp và di chuyển các mục hơn. Danh sách được liên kết hiệu quả hơn nhiều để chèn và xóa các mục, đặc biệt là ở phần cuối. Khi bạn chèn hoặc xóa một mục vào một mảng, máy tính của bạn cũng cần lập index lại phần còn lại của dữ liệu, cung cấp cho ta O(n) , với danh sách được liên kết có thể thực hiện điều đó trong O(1) cộng với thời gian tìm kiếm, ta có một số cách để tối ưu hóa.
Nhiều trình duyệt sử dụng danh sách được liên kết để ghi lại lịch sử tìm kiếm của bạn, vì nó thực tế hơn nhiều cho việc di chuyển lên và xuống một chuỗi khi user hiếm khi cần tìm kiếm bất kỳ thứ gì hoặc xem toàn bộ.
Mặc dù một mảng sẽ cho phép bạn truy cập lại trực tiếp vào Google, nhưng một danh sách được liên kết buộc bạn phải đặt nó làm phần đuôi mới hoặc chuyển ngược lại theo cách thủ công đến những gì bạn muốn, ta không thể chuyển qua bất kỳ thứ gì ở giữa.
Danh sách liên kết đơn so với kép
Có hai cách chính để ta có thể cài đặt danh sách được liên kết của bạn , hoặc bằng một con trỏ, buộc nó vào một hướng hoặc hai, làm cho nó thành hai hướng.
Tìm kiếm thông qua một danh sách được liên kết đơn lẻ yêu cầu ta xem từng mục để tìm thứ ta muốn, trong khi danh sách được liên kết kép có thể bắt đầu tìm kiếm từ đầu hoặc đuôi tùy thuộc vào một nửa mục đó, cho ta O(n / 2) .
Danh sách được liên kết kép cũng yêu cầu nhiều bộ nhớ hơn vì mỗi mục phải lưu trữ con trỏ cho các mục tiếp theo và trước đó, điều này có thể nghĩa là sự khác biệt lớn nếu bạn đang lưu trữ nhiều dữ liệu.
Sau này, khi ta triển khai danh sách liên kết trong các cấu trúc khác, ta sẽ chủ yếu sử dụng danh sách liên kết đơn lẻ. Ví dụ, trong ngăn xếp và hàng đợi, ta chỉ tương tác với các phần cuối và có rất ít nhu cầu duyệt qua toàn bộ danh sách, vì vậy hai con trỏ sẽ không thực tế.
Quan tâm làm gì?
- Danh sách được liên kết đóng role là nền tảng cho các cấu trúc dữ liệu phức tạp hơn như ngăn xếp, hàng đợi, cây, biểu đồ và đống. Tất cả đều có những cách để xây dựng dựa trên lợi ích của danh sách được liên kết trong khi loại bỏ một số nhược điểm của chúng, tùy thuộc vào mục đích sử dụng của bạn.
- Chúng có hiệu suất tốt hơn nhiều so với mảng khi bạn cần thực hiện nhiều bổ sung và xóa và thời gian tìm kiếm tốt hơn khi kết hợp với các kỹ thuật khác như sử dụng danh sách bỏ qua .
- Dễ dàng tạo danh sách lặp lại bằng cách đặt con trỏ tiếp theo ở phần đuôi đến phần đầu, chẳng hạn như trong thành phần băng chuyền.
Kết luận
Hy vọng rằng sau phần giới thiệu ngắn này, bạn đã sẵn sàng để bắt đầu khám phá một số lựa chọn thay thế tốt hơn cho các mảng tiêu chuẩn của bạn . Hãy xem Phần 2 để tìm hiểu cách bắt đầu triển khai danh sách liên kết kép được phân tách đầy đủ trong JavaScript.
Các tin liên quan
Câu hỏi phỏng vấn JavaScript: Gotchas phổ biến2020-02-21
Hiểu Radix Sắp xếp Thông qua JavaScript
2020-02-18
Cách xây dựng PWA trong Vanilla JavaScript
2020-02-17
Hiểu về Sắp xếp nhanh qua JavaScript
2020-02-14
Hiểu bản đồ và thiết lập đối tượng trong JavaScript
2020-02-12
Hiểu Hợp nhất Sắp xếp Thông qua JavaScript
2020-02-08
Tạo biểu mẫu tùy chỉnh bằng API dữ liệu biểu mẫu JavaScript
2020-02-06
Thuật toán sắp xếp cho người mới bắt đầu trong JavaScript: Bubble, Selection & Insertion Sort
2020-02-03
Tìm kiếm nhị phân tuyến tính Vs qua JavaScript
2020-01-29
Hiểu Đệ quy & Ghi nhớ qua JavaScript
2020-01-26
