Sự khác nhau giữa Danh sách mảng và Danh sách liên kết Khác biệt giữa
Dữ liệu được lưu trữ như thế nào?
Danh sách mảng và Danh sách liên kết là thuật ngữ phổ biến khi nói đến lưu trữ và truy xuất dữ liệu. Mặc dù có rất nhiều thiết bị lưu trữ, cuối cùng, chúng phụ thuộc vào cơ chế lưu trữ. Hai cơ chế lưu trữ này đặt dữ liệu của bạn vào các thiết bị lưu trữ và truy xuất chúng khi cần thiết. Chúng ta hãy cùng xem cách chúng lưu trữ dữ liệu trong bộ nhớ của chúng. Danh sách Array sử dụng một lưu trữ tuần tự, và các mẩu dữ liệu được lưu giữ một lần nữa. Đây có lẽ là một hình thức lưu trữ đơn giản - nó tránh nhầm lẫn. Có, chúng ta có thể lấy mục tiếp theo hoặc dữ liệu từ vị trí bộ nhớ kế tiếp của danh sách mảng; tuy nhiên, nó được lưu trữ với sự trợ giúp của các con trỏ trong danh sách liên kết. Ở đây chúng ta cần hai vị trí bộ nhớ để lưu trữ - một cho dữ liệu, một cho con trỏ. Một con trỏ địa chỉ vị trí bộ nhớ của dữ liệu tiếp theo. Chúng ta có thể dễ dàng hiểu rằng Danh sách liên kết không bao giờ lưu dữ liệu theo tuần tự; thay vào đó, nó sử dụng một cơ chế lưu trữ ngẫu nhiên. Các con trỏ là những yếu tố chính trong việc định vị các vị trí dữ liệu trong bộ nhớ.
Chúng tôi đã thảo luận về cách cả hai cơ chế lưu trữ đưa vào dữ liệu và chúng tôi có thể đưa ra một thuật ngữ 'mảng động' cho sơ đồ lưu trữ nội bộ của mảng Array. Nó chỉ đặt các phần dữ liệu một lần nữa - do đó tên - trong khi danh sách liên kết sử dụng danh sách nội bộ với sự trợ giúp của các con trỏ để theo dõi mục tiếp theo. Vì vậy, nó sử dụng một danh sách kết nối nội bộ, giống như một danh sách liên kết đơn hoặc gấp đôi để hiển thị cho chúng tôi dữ liệu tiếp theo.Cách sử dụng bộ nhớ
Vì danh sách Array chỉ lưu trữ dữ liệu thực tế, chúng tôi chỉ cần lưu trữ dữ liệu mà chúng tôi lưu trữ. Ngược lại, trong danh sách Liên kết, chúng tôi cũng sử dụng con trỏ. Do đó, yêu cầu hai vị trí bộ nhớ, và chúng tôi có thể nói rằng danh sách liên kết này tiêu tốn nhiều bộ nhớ hơn so với danh sách Array. Một mặt thuận lợi của Danh sách liên kết là nó không bao giờ yêu cầu các vị trí bộ nhớ liên tục để lưu trữ dữ liệu của chúng tôi, trái với danh sách Array. Các con trỏ có khả năng giữ vị trí của vị trí dữ liệu tiếp theo, và chúng ta thậm chí có thể sử dụng khe bộ nhớ nhỏ hơn không liên tục. Khi sử dụng bộ nhớ, các con trỏ đóng vai trò chính trong danh sách Liên kết, và hiệu quả của chúng như thế nào.Với danh sách Array, thậm chí một danh sách trống có yêu cầu kích thước 10, nhưng với một danh sách Liên kết, chúng ta không cần một không gian rộng lớn như vậy. Chúng tôi có thể tạo một danh sách Liên kết trống với kích thước 0. Sau đó, chúng tôi có thể tăng kích thước nếu cần.
Truy hồi dữ liệu
Thu hồi dữ liệu đơn giản hơn trong danh sách Array khi lưu trữ theo tuần tự. Tất cả nó là xác định vị trí dữ liệu đầu tiên; từ đó, vị trí tiếp theo được truy cập tuần tự để lấy phần còn lại.Nó tính như vị trí dữ liệu đầu tiên + 'n', trong đó 'n' là thứ tự của dữ liệu trong danh sách Array. Danh sách Liên kết đề cập đến con trỏ ban đầu để tìm vị trí dữ liệu đầu tiên và từ đó nó đề cập đến con trỏ kết hợp với từng dữ liệu để tìm vị trí dữ liệu tiếp theo. Quá trình truy xuất chủ yếu phụ thuộc vào các con trỏ ở đây và chúng cho chúng ta thấy vị trí dữ liệu tiếp theo.End of Data
Danh sách Array sử dụng một giá trị null để đánh dấu sự kết thúc của dữ liệu, trong khi danh sách liên kết sử dụng một con trỏ null cho mục đích này. Ngay khi hệ thống nhận ra dữ liệu null, danh sách Mảng sẽ dừng việc truy xuất dữ liệu tiếp theo. Theo cách tương tự, con trỏ null sẽ không cho hệ thống tiếp tục tiến hành truy vấn dữ liệu tiếp theo.
Reverse Traversal
Danh sách liên kết cho phép chúng ta đi qua các hướng đảo ngược với sự trợ giúp của trình giảm điểm (). Tuy nhiên, chúng tôi không có một thiết bị như vậy trong một danh sách Array - ngược trở lại trở thành một vấn đề ở đây.
Cú pháp
Chúng ta hãy nhìn vào Cú pháp Java của cả hai cơ chế lưu trữ.
Tạo danh sách mảng:
Danh sách arraylistsample = new ArrayList ();
Thêm các đối tượng vào Danh sách mảng:
Arraylistsample. thêm ("name1");
Arraylistsample. thêm ("name2");
Đây là danh sách kết quả Array sẽ như thế nào - [name1, name2].
Tạo danh sách liên kết:
Danh sách các liên kết được liệt kêtìm kiếm = new linkedList ();
Thêm đối tượng vào danh sách liên kết:
Các liên kết có liên quan. thêm ("name3"); Các liên kết có liên quan. thêm ("name4");
Đây là cách kết quả kết hợp danh sách sẽ như thế nào - [name3, name4].
Mà nào tốt hơn cho hoạt động Tìm kiếm hoặc Tìm kiếm? Danh sách Array mất O (1) thời gian để chạy bất kỳ tìm kiếm dữ liệu, trong khi danh sách liên kết mất u O (n) để tìm kiếm dữ liệu n 999. Vì vậy, một danh sách Array luôn luôn sử dụng một thời gian liên tục cho bất kỳ tìm kiếm dữ liệu, nhưng trong Danh sách liên kết, thời gian thực hiện phụ thuộc vào vị trí của dữ liệu. Do đó, các danh sách Array luôn là sự lựa chọn tốt hơn cho các hoạt động Tìm kiếm hoặc Tìm kiếm.
Mà là tốt hơn cho các hoạt động REPLACEion hoặc bổ sung?
Cả hai danh sách Mảng và Danh sách Liên kết mất O (1) thời gian để bổ sung dữ liệu. Nhưng nếu mảng đầy, sau đó danh sách Mảng mất một khoảng thời gian đáng kể để thay đổi kích thước nó và sao chép các mục vào một trong những mới hơn. Trong trường hợp đó, danh sách Liên kết là sự lựa chọn tốt hơn.
Mà là tốt hơn cho các hoạt động Hủy bỏ?
Thao tác loại bỏ mất gần như cùng một khoảng thời gian trong cả danh sách Array và danh sách Liên kết. Trong danh sách Array, thao tác này sẽ xóa dữ liệu và sau đó thay đổi vị trí của dữ liệu để tạo mảng mới hơn - cần thời gian O (n). Trong danh sách Liên kết, thao tác này đi qua các dữ liệu cụ thể và thay đổi các vị trí con trỏ để tạo thành danh sách mới hơn. Thời gian để traversal và loại bỏ là O (n) ở đây là tốt. Nhanh hơn? Chúng ta biết rằng một mảng Array sử dụng một mảng nội bộ để lưu dữ liệu thực. Do đó, nếu bất kỳ dữ liệu nào bị xóa, thì tất cả dữ liệu sắp tới cần có sự thay đổi bộ nhớ.Rõ ràng, điều này đòi hỏi một số lượng đáng kể thời gian và làm chậm mọi thứ xuống. Sự chuyển đổi bộ nhớ như vậy không bắt buộc trong danh sách Liên kết, vì tất cả điều đó là thay đổi vị trí con trỏ. Do đó, một danh sách Liên kết nhanh hơn một danh sách Array trong bất kỳ loại lưu trữ dữ liệu nào. Tuy nhiên, điều này hoàn toàn phụ thuộc vào loại hoạt động, i. e. cho các hoạt động Nhận hoặc Tìm kiếm, Danh sách liên kết mất nhiều thời gian hơn so với một danh sách Array. Khi chúng ta nhìn vào hiệu suất tổng thể, chúng ta có thể nói rằng danh sách Liên kết nhanh hơn.
Khi nào để sử dụng một mảng và một danh sách liên kết?
Một danh sách Array là tốt nhất cho các yêu cầu dữ liệu nhỏ hơn, nơi bộ nhớ liên tục có sẵn. Nhưng khi chúng ta đối phó với số lượng lớn dữ liệu, sự sẵn có của bộ nhớ liên tục thực hiện các cơ chế lưu trữ dữ liệu, cho dù đó là nhỏ hay lớn. Tiếp theo, quyết định lựa chọn nào - danh sách Array hoặc danh sách Liên kết. Bạn có thể tiếp tục với một danh sách mảng khi bạn chỉ cần lưu trữ và truy xuất dữ liệu. Nhưng một danh sách có thể giúp bạn vượt qua điều đó bằng cách thao tác dữ liệu. Khi bạn quyết định tần suất thao tác dữ liệu cần thiết, điều quan trọng là bạn phải kiểm tra kiểu truy xuất dữ liệu mà bạn thường thực hiện. Khi nó chỉ là Get hay Search, thì Array List là sự lựa chọn tốt hơn; cho các hoạt động khác như REPLACEion hoặc Deletion, tiếp tục với danh sách Linked.
Chúng ta hãy nhìn vào sự khác biệt trong hình dạng bảng.
S. Lưu trữ dữ liệu
Sử dụng lưu trữ dữ liệu tuần tự
Sử dụng lưu trữ dữ liệu không tuần tự 2 < Duy trì một dãy động nội bộ
Duy trì một danh sách liên kết
3
