alt

Xây dựng từ các thuật toán đơn giản & cấu trúc dữ liệu trong JS
, ở đây chúng ta sẽ xem xét các cấu trúc dữ liệu ngoài các mảng và các đối tượng key-value, ngoài các "labelled & deposit” boxes. Giống như một con đường dọc theo một lối đi, linked lists, stacks & queues là những cách trực tiếp để di chuyển từ đơn vị dữ liệu này sang đơn vị dữ liệu tiếp theo.

Linked Lists

Một Linked Lists giống như một tập hợp các hộp được xâu chuỗi lại với nhau và được lưu trữ trong một căn phòng tối. Để đến bất kỳ một hộp nào, yêu cầu bắt đầu từ một đầu (đầu hoặc đuôi) và đi theo các liên kết, từ hộp này sang hộp tiếp theo. Khi đến bất kỳ ô nào, bạn sẽ được chỉ hướng của ô tiếp theo. Không có chỉ mục nào đóng vai trò là hướng dẫn để chuyển đến bất kỳ ô nào.

Bạn có thể dễ dàng bỏ dịch chuyển hoặc đẩy “hộp” vào đầu hoặc đuôi của danh sách được liên kết. Bạn cũng có thể dễ dàng chuyển hoặc bật “hộp” ra khỏi đầu hoặc đuôi. Đầu hoặc đuôi có thể dễ dàng truy cập. Tuy nhiên, để chèn thêm hoặc loại bỏ các “hộp” dọc theo phần thân của Linked Lists này, để đặt các mục vào một “hộp” nằm ngoài phần đầu hoặc phần đuôi, thì khó hơn. Nó yêu cầu bắt đầu từ đầu (hoặc đuôi) và di chuyển từ “hộp” hiện tại sang hộp tiếp theo, trước khi bạn có thể đến “hộp” mong muốn của mình.

Linked Lists đơn là danh sách liên kết một chiều. Điều này có nghĩa là bạn chỉ có thể tiến từ đầu đến đuôi. Độ phức tạp để hủy dịch chuyển & dịch chuyển là một hằng số ( O(1) ). Điều này là do việc thêm một “hộp” vào hoặc xóa nó ngay từ đầu chỉ yêu cầu truy cập vào phần đầu của danh sách. Độ phức tạp để đẩy một “chiếc hộp” đến cùng cũng là O(1) vì lý do tương tự, phần đuôi có thể truy cập ngay lập tức.

Tuy nhiên, để lấy ra phần đuôi cần phải chỉ định lại một phần đuôi mới, phần đuôi này chỉ có thể truy cập được bằng cách di chuyển về phía trước bắt đầu từ phần đầu, do đó có độ phức tạp tuyến tính ( O(n) ). Nếu n số “hộp” thì yêu cầu n số bước (thao tác) để đi đến “hộp” thứ hai và chỉ định lại nó làm đuôi mới. Tương tự, để chèn/xóa một “hộp” hoặc để lấy/đặt các mục trong bất kỳ “hộp” nào dọc theo phần thân của danh sách, yêu cầu phải di chuyển từ phần đầu và do đó, độ phức tạp của chúng nói chung là O(n) .

Linked Lists kép là danh sách liên kết hai chiều. Điều này có nghĩa là bạn có thể di chuyển về phía trước từ đầu hoặc đuôi. Một lợi thế là cả phần đầu và phần đuôi đều có thể dễ dàng truy cập để thêm “hộp” vào hoặc xóa “hộp” khỏi. Độ phức tạp của unshift , shift , Push hoặc pop là O(1) . Có thể truy cập đuôi mới cần thiết để bật đuôi từ đuôi hiện tại.

Một ưu điểm khác của việc có thể di chuyển từ hai điểm cuối khác nhau (đầu hoặc đuôi) là việc chèn/xóa bất kỳ “hộp” nào hoặc lấy/đặt “các mục” trong một “hộp” dọc theo phần thân của danh sách chỉ mất một nửa thời gian. của Linked Lists đơn. Đó là, độ phức tạp của chúng là một nửa của O(n) . Nếu “hộp” hoặc “mục” nằm ở nửa sau của danh sách, thì việc di chuyển từ phần đuôi sẽ không cần phải di chuyển qua nửa đầu của danh sách. Điều ngược lại cũng đúng. Mặc dù, một O(1/2 n) có xu hướng được đơn giản hóa thành O(n) .

Stacks

Stack là một đống vật phẩm được sắp xếp gọn gàng lên nhau. Một mục mới sẽ được đẩy lên trên cùng của Stacks, mỗi lần một mục, xây dựng theo chiều cao của Stacks. Ngược lại, mỗi mục có thể được lấy ra, từng mục một, từ đầu ngăn xếp. Mục cuối cùng sẽ luôn là mục đầu tiên xuất hiện ( LIFO-Last in first out).

alt

Vì Stacks hoạt động theo quy trình LIFO nên độ phức tạp để đẩy một mục lên trên cùng của ngăn xếp hoặc bật nó ra khỏi ngăn xếp là một hằng số của O(1) . Đỉnh của ngăn xếp có thể dễ dàng truy cập.

Queues

Queues là một dòng các mặt hàng, được sắp xếp gọn gàng cạnh nhau. Một mục mới có thể được xếp vào cuối dòng, mỗi lần thêm một mục, kéo dài dòng. Ngược lại, mỗi mục có thể được lấy ra từ đầu hàng, từng mục một. Mục đầu tiên trong Queues luôn là mục đầu tiên xuất hiện ( FIFO-first in first out ).

alt

Vì cả đầu và cuối của dòng đều có thể truy cập dễ dàng, nên thêm và lấy ra phần tử của queues có độ phức tạp là O(1) .

Cảm ơn vì đã đọc!