Mảng và danh sách được liên kết

Nov 06 2022
Thuật toán và cấu trúc dữ liệu từ 0 đến anh hùng
Đôi khi bạn cần lưu trữ danh sách các phần tử trong bộ nhớ. Giả sử bạn đang viết một ứng dụng để quản lý chi phí của mình.

Đôi khi bạn cần lưu trữ danh sách các phần tử trong bộ nhớ. Giả sử bạn đang viết một ứng dụng để quản lý chi phí của mình. Bạn sẽ muốn lưu trữ các khoản chi phí dưới dạng danh sách trong bộ nhớ.

Bạn nên sử dụng một mảng hay một danh sách được liên kết? Trước tiên, hãy lưu trữ các chi phí trong một mảng, vì nó dễ nắm bắt hơn. Sử dụng một mảng có nghĩa là tất cả các chi phí của bạn được lưu trữ liền kề (ngay cạnh nhau) trong bộ nhớ.

Bây giờ, giả sử bạn muốn thêm khoản chi phí thứ tư. Nhưng ngăn kéo tiếp theo được đưa lên.

Nó giống như việc bạn đi chơi với bạn bè và tìm một chỗ để ngồi nhưng một người bạn khác tham gia cùng bạn và không có chỗ cho họ. Bạn phải chuyển đến một vị trí mới, nơi bạn phù hợp. Trong trường hợp này, bạn cần yêu cầu máy tính của mình cung cấp một phần bộ nhớ khác có thể phù hợp với bốn chi phí. Sau đó, bạn cần phải chuyển tất cả các chi phí của bạn đến đó.

Và điều này sẽ trở thành một vòng lặp ngay khi có nhiều bạn bè tham gia với bạn, nhưng hãy chắc chắn rằng bạn luôn có thể thêm các vị trí bổ sung để đề phòng. Đây là một giải pháp tốt, nhưng bạn nên biết một số nhược điểm:

  • Bạn có thể không cần thêm khe cắm mà bạn đã yêu cầu, và khi đó bộ nhớ đó sẽ bị lãng phí.
  • Bạn có thể thêm hơn 10 mục vào danh sách chi phí của mình và vẫn phải di chuyển.

Danh sách được liên kết

Danh sách được liên kết là một tập hợp tuyến tính của các phần tử dữ liệu mà thứ tự của chúng không được đưa ra bởi vị trí vật lý của chúng trong bộ nhớ. Thay vào đó, mỗi phần tử trỏ đến phần tiếp theo.

Với danh sách được liên kết, các mục của bạn có thể ở bất kỳ đâu trong bộ nhớ.

Truy cập tuần tự so với truy cập ngẫu nhiên

Truy cập tuần tự có nghĩa là chi phí truy cập phần tử thứ 5 gấp 5 lần chi phí truy cập phần tử đầu tiên hoặc ít nhất là có một chi phí ngày càng tăng liên quan đến một vị trí phần tử trong tập hợp. Điều này là do để truy cập phần tử thứ 5 của tập hợp, trước tiên bạn phải thực hiện một thao tác để tìm phần tử thứ 1, thứ 2, thứ 3 và thứ 4, vì vậy để truy cập phần tử thứ 5 cần 5 thao tác.

Truy cập ngẫu nhiên có nghĩa là truy cập bất kỳ phần tử nào trong tập hợp có cùng chi phí với bất kỳ phần tử nào khác trong tập hợp. Việc tìm phần tử thứ 5 của một tập hợp vẫn chỉ là một phép toán duy nhất.

Array vs LinkedList

Trong một mảng, chúng ta biết địa chỉ của từng phần tử của mảng. Như chúng ta có thể thấy trong hình trên, chúng ta có một mảng với 5 đơn vị bộ nhớ và mảng này chứa 3 phần tử, vì các phần tử được lưu trữ ở các vị trí bộ nhớ liền nhau (các phần tử trong một mảng được đánh số và việc đánh số này bắt đầu từ 0) chúng ta biết ở đâu nó bắt đầu và nó kết thúc ở đâu.

Vị trí của một phần tử được gọi là chỉ mục của nó, vì vậy thay vì nói, “8 ở vị trí 1”, thuật ngữ chính xác là “8 ở chỉ mục 1”.

Mảng rất tuyệt nếu bạn muốn đọc các phần tử ngẫu nhiên, vì bạn có thể tra cứu bất kỳ phần tử nào trong mảng của mình ngay lập tức.

Trong một danh sách được liên kết, mỗi mục lưu trữ địa chỉ của mục tiếp theo trong danh sách. Một loạt các địa chỉ bộ nhớ ngẫu nhiên được liên kết với nhau.

Nó giống như một cuộc truy tìm kho báu. Bạn đi đến địa chỉ đầu tiên, và nó nói, "Có thể tìm thấy mặt hàng tiếp theo tại địa chỉ 008". Vì vậy, bạn đi đến địa chỉ 008, và nó nói, "Có thể tìm thấy mặt hàng tiếp theo tại địa chỉ 002", v.v.

Thêm một mục vào danh sách liên kết rất dễ dàng: bạn dán nó vào bất kỳ vị trí nào trong bộ nhớ và lưu trữ địa chỉ với mục tiếp theo trước đó.

Với danh sách được liên kết, bạn không bao giờ phải di chuyển các mục của mình. Bạn cũng tránh được một vấn đề khác.

Giả sử bạn đi xem một bộ phim nổi tiếng với bốn người bạn của mình. Năm bạn đang cố gắng tìm một chỗ để ngồi, nhưng rạp chiếu phim đã chật cứng. Không có năm chỗ ngồi cùng nhau.

Chà, đôi khi điều này xảy ra với mảng. Giả sử bạn đang cố gắng tìm 40.000 vị trí cho một mảng. Bộ nhớ của bạn có 40.000 khe cắm, nhưng nó không có 40.000 khe cắm cùng nhau. Bạn không thể có được không gian cho mảng của mình!

Một danh sách được liên kết giống như nói "Hãy chia nhỏ và xem phim". Nếu có dung lượng trong bộ nhớ, bạn có không gian cho danh sách liên kết của mình.

Nếu danh sách liên kết có khả năng chèn tốt hơn rất nhiều, thì mảng tốt cho điều gì?

Mảng

Mảng tốt hơn danh sách liên kết khi chúng tôi cố gắng truy cập vào các mục của chúng tôi trong danh sách.

Giả sử bạn muốn đọc mục cuối cùng thứ hai trong danh sách được liên kết. Bạn không thể chỉ đọc nó, bởi vì bạn không biết nó ở địa chỉ nào.

Bạn phải đi đến mục số 1 để lấy địa chỉ cho mục số 2, v.v., cho đến khi bạn đến mục cuối cùng thứ hai.

Danh sách được liên kết sẽ rất tuyệt nếu bạn muốn đọc tất cả các mục cùng một lúc. Nhưng nếu bạn tiếp tục nhảy xung quanh, danh sách được liên kết là rất tệ.

Các mảng là khác nhau. Bạn biết địa chỉ của mọi mục trong mảng của mình, vì vậy bạn có thể truy cập vào bất kỳ mục nào ngay lập tức.

Chèn vào giữa danh sách

Giả sử bạn muốn danh sách chi phí của mình hoạt động giống lịch hơn. Trước đó, bạn đã thêm những thứ vào cuối danh sách.

Bây giờ bạn muốn thêm chúng theo thứ tự mà chúng sẽ được thực hiện.

Còn gì tốt hơn nếu bạn muốn chèn các phần tử vào giữa: mảng hoặc danh sách liên kết? Với danh sách được liên kết, thật dễ dàng như thay đổi phần tử trước đó trỏ đến.

Nhưng đối với mảng, bạn phải chuyển tất cả các phần tử còn lại xuống dưới.

Và nếu không có dung lượng, bạn có thể phải sao chép mọi thứ sang một vị trí mới! Danh sách sẽ tốt hơn nếu bạn muốn chèn các phần tử vào giữa.

Xóa

Điều gì xảy ra nếu bạn muốn xóa một phần tử? Một lần nữa, danh sách được liên kết tốt hơn, bởi vì bạn chỉ cần thay đổi phần tử trước đó trỏ đến. Với mảng, mọi thứ cần được di chuyển lên khi bạn xóa một phần tử.

Thời gian chạy cho các hoạt động phổ biến trên mảng và danh sách:

Chèn và xóa là O (1) lần vì bạn thường sẽ theo dõi các mục đầu tiên và cuối cùng trong danh sách được liên kết, vì vậy sẽ chỉ mất O (1) để thêm hoặc xóa.

Cái nào được sử dụng nhiều hơn: mảng hoặc danh sách liên kết? Rõ ràng, nó phụ thuộc, vào trường hợp sử dụng. Nhưng mảng được sử dụng nhiều vì chúng cho phép truy cập ngẫu nhiên.

BÀI TẬP

Giả sử bạn đang xây dựng một ứng dụng cho siêu thị để nhận đơn đặt hàng của khách hàng. Ứng dụng của bạn cần lưu trữ danh sách các đơn đặt hàng. khách hàng tiếp tục thêm đơn đặt hàng vào danh sách này, và nhân viên lấy đơn đặt hàng ra khỏi danh sách và thực hiện chúng. Đó là một hàng đợi đơn hàng: khách hàng thêm đơn hàng vào phía sau hàng đợi, và người sử dụng lao động lấy đơn hàng đầu tiên ra khỏi hàng đợi và chuẩn bị.

Bạn sẽ sử dụng một mảng hoặc một danh sách được liên kết để triển khai hàng đợi này? (Gợi ý: - Danh sách được liên kết tốt cho việc chèn / xóa và mảng tốt cho việc truy cập ngẫu nhiên. Bạn muốn làm gì ở đây?).

Tiếp theo

Mảng và danh sách liên kết cũng được sử dụng để triển khai các cấu trúc dữ liệu khác.

⬅️ Bộ nhớ hoạt động như thế nào | Mục lục | Ngăn xếp ➡️

© Copyright 2021 - 2022 | vngogo.com | All Rights Reserved