Sự khác biệt giữa Danh sách mảng và Danh sách liên kết

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à các 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. Chúng ta hãy xem cách họ lưu trữ dữ liệu trong bộ nhớ của họ. Danh sách Mảng sử dụng bộ lưu trữ tuần tự và các phần dữ liệu được lưu trữ lần lượt. Đây có lẽ là một hình thức lưu trữ đơn giản hơn - nó tránh sự nhầm lẫn. Có, chúng ta có thể truy xuất mục hoặc dữ liệu tiếp theo từ vị trí bộ nhớ tiếp theo 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ỏ giải quyết 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 trữ dữ liệu 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à các yếu tố chính trong việc định vị các vị trí dữ liệu trong bộ nhớ.

Dynamic Array và Danh sách liên kết

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 danh sách Mảng. Nó chỉ đặt các mẩu dữ liệu lần lượt theo tên khác - 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. Do đó, nó sử dụng danh sách liên kết nội bộ, như danh sách liên kết đơn hoặc đôi để hiển thị cho chúng tôi dữ liệu tiếp theo.

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 không gian cho dữ liệu 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 đó, cần có hai vị trí bộ nhớ và chúng ta có thể nói rằng danh sách được liên kết sẽ tiêu thụ nhiều bộ nhớ hơn danh sách Array. Một lợi thế 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 ngược 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 các khe cắm bộ nhớ nhỏ hơn không liên tục. Khi nói đến việc sử dụng bộ nhớ, con trỏ đóng vai trò chính trong danh sách Liên kết và hiệu quả của chúng cũng vậy..

Kích thước của danh sách mảng ban đầu và danh sách liên kết

Với danh sách Mảng, ngay cả một danh sách trống cũng yêu cầu kích thước 10, nhưng với 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 này, chúng tôi có thể tăng kích thước khi cần.

Phục hồi dữ liệu

Truy xuất dữ liệu đơn giản hơn trong danh sách Array vì nó lưu trữ tuần tự. Tất cả những gì nó làm 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 toán như vị trí dữ liệu đầu tiên + 'n', trong đó 'n' là thứ tự của dữ liệu trong danh sách Mảng. Danh sách được liên kết đề cập đến con trỏ ban đầu để tìm vị trí dữ liệu đầu tiên và từ đó nó chỉ ra con trỏ được liên kết với mỗi 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 một cách hiệu quả.

Hết dữ liệu

Danh sách Array sử dụng giá trị null để đánh dấu kết thúc dữ liệu, trong khi danh sách Liên kết sử dụng con trỏ null cho mục đích này. Ngay khi hệ thống nhận ra dữ liệu null, danh sách Array dừng truy xuất dữ liệu tiếp theo. Theo cách tương tự, con trỏ null ngăn hệ thống tiến hành truy xuất dữ liệu tiếp theo.

Đảo ngược

Danh sách được liên kết cho phép chúng ta đi qua các hướng ngược lại với sự trợ giúp của bộ giảm dần (). Tuy nhiên, chúng tôi không có một cơ sở như vậy trong danh sách Mảng - truyền tải ngược trở thành vấn đề ở đây.

Cú pháp

Chúng ta hãy xem Cú pháp Java của cả hai cơ chế lưu trữ.

Tạo danh sách mảng:

Liệt kê danh sách mảng = new ArrayList ();

Thêm đối tượng vào Danh sách mảng:

Arraylistsample.add (Tên tên11);

Arraylistsample.add (Tên tên22);

Đây là cách danh sách Mảng kết quả sẽ trông như thế nào - [name1, name2].

Tạo danh sách liên kết:

Danh sách linkslistsample = new LinkedList ();

Thêm đối tượng vào Danh sách liên kết:

Linkedlistsample.add (Tên name3 trực tiếp);

Linkedlistsample.add (Tiếng tên44);

Đây là cách danh sách Liên kết kết quả sẽ trông như thế nào - [name3, name4].

 Cái nào tốt hơn cho hoạt động Nhận hoặc Tìm kiếm?

Danh sách Mảng mất thời gian O (1) để chạy bất kỳ tìm kiếm dữ liệu nào, trong khi danh sách Liên kết mất u O (n) cho n^{thứ tự} tìm kiếm dữ liệu. Do đó, danh sách Mảng luôn sử dụng thời gian không đổi cho bất kỳ tìm kiếm dữ liệu nào, nhưng trong danh sách Liên kết, thời gian thực hiện tùy thuộc vào vị trí của dữ liệu. Do đó, danh sách mảng luôn là lựa chọn tốt hơn cho các hoạt động Nhận hoặc Tìm kiếm.

Cái nào tốt hơn cho thao tác chèn hoặc bổ sung?

Cả danh sách Mảng và Danh sách liên kết đều mất thời gian O (1) để thêm dữ liệu. Nhưng nếu mảng đầy, thì danh sách Array cần một khoảng thời gian đáng kể để thay đổi kích thước của nó và sao chép các mục sang cái mới hơn. Trong trường hợp như vậy, danh sách Liên kết là sự lựa chọn tốt hơn.

Cái nào tốt hơn cho thao tác xóa?

Thao tác xóa mất gần như cùng một lượng thời gian trong cả danh sách Mảng và danh sách Liên kết. Trong danh sách Mảng, thao tác này xóa dữ liệu và sau đó dịch chuyển vị trí của dữ liệu để tạo thành mảng mới hơn - phải mất thời gian O (n). Trong danh sách Liên kết, thao tác này đi qua dữ liệu cụ thể và thay đổi vị trí con trỏ để tạo thành danh sách mới hơn. Thời gian để truyền tải và loại bỏ là O (n) ở đây.

Cái nào nhanh hơn?

Chúng tôi biết rằng một danh sách Array sử dụng một mảng nội bộ để lưu trữ dữ liệu thực tế. Do đó, nếu bất kỳ dữ liệu nào bị xóa, thì tất cả các dữ liệu sắp tới cần một sự thay đổi bộ nhớ. Rõ ràng, điều này đòi hỏi một lượng thời gian đáng kể và làm mọi thứ chậm lại. Sự thay đổi bộ nhớ như vậy là không bắt buộc trong danh sách Liên kết, vì tất cả những gì nó làm là thay đổi vị trí con trỏ. Do đó, danh sách Liên kết nhanh hơn danh sách Mảng 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, tức là đối với 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 danh sách Mảng. 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 được liên kết nhanh hơn.

Khi nào nên sử dụng Danh sách mảng và Danh sách liên kết?

Một danh sách Array phù hợp nhất cho các yêu cầu dữ liệu nhỏ hơn, nơi có bộ nhớ liên tục. Nhưng khi chúng ta xử lý lượng dữ liệu khổng lồ, sự sẵn có của bộ nhớ liên tục sẽ thực hiện các cơ chế lưu trữ dữ liệu, cho dù nó nhỏ hay lớn. Tiếp theo, quyết định chọn cái nào - danh sách Mảng 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 mức độ thường xuyên phải thao tác dữ liệu, điều quan trọng là phải kiểm tra loại truy xuất dữ liệu bạn thường thực hiện. Khi nó chỉ là Nhận hoặc Tìm kiếm, thì Danh sách Mảng là lựa chọn tốt hơn; đối với các hoạt động khác như Chèn hoặc Xóa, hãy tiếp tục với danh sách Liên kết.

Chúng ta hãy nhìn vào sự khác biệt trong hình thức bảng.

S.Không	Các khái niệm	Sự khác biệt
		Lập danh sách	Danh sách liên kết
1	Thời trang 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	Đề án lưu trữ nội bộ	Duy trì một mảng động bên trong	Duy trì danh sách liên kết
3	Sử dụng bộ nhớ	Yêu cầu không gian bộ nhớ chỉ dành cho dữ liệu	Yêu cầu không gian bộ nhớ cho dữ liệu cũng như cho con trỏ
4	Kích thước của danh sách ban đầu	Cần không gian cho ít nhất 10 mục	Không cần dung lượng và chúng tôi thậm chí có thể tạo danh sách Liên kết có kích thước 0 trống.
5	Phục hồi dữ liệu	Tính toán như vị trí dữ liệu đầu tiên + 'n', trong đó 'n' là thứ tự của dữ liệu trong danh sách Mảng	Truyền qua từ đầu tiên hoặc cuối cùng cho đến khi dữ liệu được yêu cầu là bắt buộc
6	Hết dữ liệu	Các giá trị Null đánh dấu sự kết thúc	Con trỏ Null đánh dấu sự kết thúc
7	Đảo ngược	Không cho phép	Cho phép nó với sự trợ giúp của bộ giảm dần ()
số 8	Cú pháp tạo danh sách	Liệt kê danh sách mảng = new ArrayList ();	Danh sách linkslistsample = new LinkedList ();
9	Thêm đối tượng	Arraylistsample.add (Tên tên11);	Linkedlistsample.add (Tên name3 trực tiếp);
10	Nhận hoặc tìm kiếm	Mất O (1) thời gian và hiệu suất tốt hơn	Mất thời gian và hiệu suất của O (n) phụ thuộc vào vị trí của dữ liệu
11	Chèn hoặc bổ sung	Tiêu tốn thời gian O (1) trừ khi mảng đầy	Tiêu thụ O (1) thời gian trong mọi trường hợp
12	Xóa hoặc xóa	Mất thời gian O (n)	Mất thời gian O (n)
13	Khi nào sử dụng?	Khi có nhiều hoạt động Nhận hoặc Tìm kiếm liên quan; bộ nhớ khả dụng sẽ cao hơn ngay cả khi bắt đầu	Khi có nhiều thao tác Chèn hoặc Xóa và bộ nhớ khả dụng không cần phải liên tục