Helpex - Trao đổi & giúp đỡ Đăng nhập

ArrayList hay LinkedList?

Bài viết này cung cấp hướng dẫn cho các nhà phát triển Java trong việc chọn cấu trúc dữ liệu tuần tự thích hợp.

ArrayList LinkedList là hai lớp của Java Collection Framework được sử dụng để lưu trữ danh sách các tham chiếu đối tượng. ArrayList và   LinkedList cả hai đều triển khai giao diện Danh sách . Đầu tiên chúng ta hãy cố gắng hiểu Danh sách (cái) giao diện mẹ quan trọng nhất của chúng.

Giao diện danh sách

Danh sách chỉ đơn giản là một tập hợp các phần tử có thứ tự (còn được gọi là một dãy). Nó bổ sung các thao tác định hướng theo vị trí hữu ích để nhanh chóng truy cập, thêm và xóa các phần tử tại một vị trí chỉ mục cụ thể trên danh sách. Giao diện danh sách có Bộ sưu tập và Có thể lặp lại là các siêu giao diện. Nó có thể cho phép lưu trữ các bản sao và giá trị null. Nó cung cấp quyền truy cập được lập chỉ mục vào phần tử của nó.

Sử dụng

Dưới đây là đoạn mã khai báo ArrayList LinkedListsử dụng giao diện Danh sách.

import java.util.*;

public class MyClass {

  // Unsynchronized or Not thread safe
  List<object> arrayList = new ArrayList<>(); // declares an array list
  List<object> linkedList = new LinkedList(); // declares a linked list   

    // ensures thread safety 
  List<object> tsArrayList = Collections.synchronizedList(new LinkedList<>());
  List<object> tsLinkedList = Collections.synchronizedList(new LinkedList<>());   
}</object></object></object></object>


Vector tương tự như ArrayList ngoại trừ chúng được cung cấp đồng bộ hóa tự động, điều này làm cho chúng an toàn theo luồng nhưng gây ra một số chi phí hiệu suất.

Thực hiện nội bộ 

Danh sách liên kết

Các LinkedListcấu trúc dữ liệu chứa một tập có thứ tự của các yếu tố dữ liệu (được biết như là nút ) sao cho mỗi phần tử chứa một liên kết hoặc tham chiếu đến người kế nhiệm (của nó tới phần tử). Phần tử cuối cùng (hoặc phần đuôi ) của dãy trỏ đến phần tử rỗng . Bản thân danh sách được liên kết chứa một tham chiếu đến phần tử đầu tiên của danh sách, phần tử này được gọi là phần tử đầu. LinkedList trong Java là một triển khai danh sách được liên kết kép của giao diện Danh sách. Trong danh sách được liên kết kép, mọi nút đều trỏ đến nút trước đó và nút tiếp theo của nó. Giao diện khác nó cụ là Serializable , Cloneable , và deque (với siêu giao diện như Queue).

Lập danh sách

ArrayList là một triển khai mảng có thể thay đổi kích thước của giao diện Danh sách. Nó được triển khai nội bộ dưới dạng một mảng đối tượng, có thể tăng kích thước khi cần thiết để hỗ trợ nhiều phần tử hơn trong bộ sưu tập. Có thể chỉ định dung lượng ban đầu của một ArrayList thông qua phương thức khởi tạo ArrayList(int initialCapacity)  và sau đó tăng dung lượng bằng cách sử dụng   void ensureCapacity(int minCapacity), nếu cần, để đảm bảo rằng nó có thể chứa ít nhất số phần tử được chỉ định bởi đối số dung lượng tối thiểu.

Nó cũng bao gồm một phương pháp để giảm kích thước dựa trên các yếu tố hiện có. void trimToSize()

import java.util.*;

Theo mặc định, an tạo một danh sách có dung lượng ban đầu 10, trong khi LinkedListchỉ tạo một danh sách trống mà không có bất kỳ dung lượng ban đầu nào.  LinkedList không triển khai giao diện RandomAccess , ngược lại thực thi giao diện (thay vì giao diện Deque).

Sự phức tạp về không gian và thời gian của các hoạt động khác nhau

Đặc tính

Lập danh sách

LinkedList

Thêm (hoặc xóa) một phần tử

Điều này liên quan đến việc di chuyển tất cả các phần tử hiện có trở lại (hoặc chuyển tiếp) đến một nơi yêu cầu sao chép các mục được thực hiện thông qua lệnh gọi đến   System.arraycopy (). - độ phức tạp thời gian của trường hợp tốt nhất  là O (1).

độ phức tạp thời gian theo trường hợp trung bình O (n) là System.arraycopy () sẽ là thời gian tuyến tính.

Điều này liên quan đến việc phân bổ (hoặc phân bổ) một bản ghi nội bộ cho phần tử và sau đó sắp xếp lại một vài liên kết và có chi phí cố định . - độ phức tạp thời gian là O (1). Việc thêm (hoặc bớt) một phần tử ở giữa danh sách sẽ có độ phức tạp về thời gian là O (n) vì nó sẽ liên quan đến việc lặp qua danh sách.

Thêm một phần tử

Thông thường, điều này liên quan đến việc đặt vị trí mảng bên trong thành tham chiếu phần tử với độ phức tạp thời gian là O (1)., Nhưng đôi khi đối với trường hợp tràn, điều này dẫn đến việc mảng được phân bổ lại và có chi phí trung bình cố định một lần nữa liên quan đến việc kích hoạt lệnh gọi thành System.arraycopy (),  với độ phức tạp thời gian trong trường hợp xấu nhất là O (n).

Điều này chỉ liên quan đến việc phân bổ một đối tượng bên trong và chi phí là đồng nhất.

Dung lượng bộ nhớ Overhead

Nó có một không gian bộ nhớ trên đầu vì danh sách các đối tượng phải được phân bổ trước, có nghĩa là các phần tử trống ở cuối danh sách.

Nó có một khoảng trống bộ nhớ trên không để lưu trữ các tham chiếu đến phần tử trước đó và tiếp theo trong danh sách cho mọi phần tử.

Truy cập ngẫu nhiên vào các phần tử của nó

Truy cập ngẫu nhiên có thời gian cố định - độ phức tạp về thời gian là O (1).

Thời gian để thực hiện truy cập ngẫu nhiên tỷ lệ thuận với kích thước của danh sách (trừ khi đây là phần tử đầu tiên hoặc phần tử cuối cùng mà chi phí được cố định) - độ phức tạp thời gian trường hợp trung bình là O (n).

Giá trị rỗngCó, nó có thể được lưu trữCó, nó có thể được lưu trữ
Trùng lặpCó, nó có thể được lưu trữ

Có, nó có thể được lưu trữ


Lời khuyên

Hãy xem xét các ví dụ mã sau đây để duyệt LinkedListmã Đoạn mã dưới đây sẽ rất chậm vì LinkedListkhông hỗ trợ truy cập ngẫu nhiên và có một chi phí lớn khi duyệt cho mỗi lần lặp.


Thay vào đó, một cách tiếp cận tốt hơn để cải thiện hiệu suất là sử dụng đoạn mã sau.

public class MyClass {

Phần kết luận

An ArrayList nhanh hơn và tốt hơn vì nó hỗ trợ truy cập ngẫu nhiên vào các phần tử của nó. Việc duyệt qua một danh sách được liên kết hoặc chèn một mục vào giữa là rất tốn kém vì bạn phải lặp đi lặp lại từng mục và rất có thể bị bỏ sót bộ nhớ cache. Nếu bạn cần phải thực hiện chế biến trên nhiều mặt hàng của danh sách trong một sự lặp lại đơn thì chi phí của sự lặp lại có thể ít hơn trong LinkedListhơn một ArrayListtrong đó bao gồm sao chép phần tử mảng nhiều lần .

Để chia sẻ kinh nghiệm của bạn và hiểu biết thêm về chủ đề này, vui lòng để lại suy nghĩ của bạn trong phần bình luận bên dưới.

13 hữu ích 0 bình luận 31k xem chia sẻ

Có thể bạn quan tâm

loading