Việc triển khai Danh sách nào để sử dụng?

Question

Trong chương trình của tôi, tôi thường sử dụng các bộ sưu tập để lưu trữ danh sách các đối tượng. Hiện tại tôi sử dụng ArrayList để lưu trữ các đối tượng. Câu hỏi của tôi là: đây có phải là lựa chọn tốt nhất không? Có thể tốt hơn nếu sử dụng LinkedList? Hay cái gì khác?

Tiêu chuẩn để xem xét là:

• Sử dụng bộ nhớ
• Performance

Operations mà tôi cần là:

• Thêm yếu tố để thu
• Duyệt qua các yếu tố

Bất kỳ suy nghĩ nào?

Cập nhật: sự lựa chọn của tôi là: ArrayList :) Căn cứ vào cuộc thảo luận này cũng như những người sau đây:

• When to use LinkedList over ArrayList?
• List implementations: does LinkedList really perform so poorly vs. ArrayList and TreeList?

Answer 1

tôi luôn mặc định ArrayList, và sẽ ở trường hợp của bạn là tốt, trừ khi

• tôi cần an toàn thread (trong trường hợp này tôi bắt đầu nhìn vào hiện thực List trong java.util.concurrent)
• Tôi biết tôi sẽ làm rất nhiều việc chèn và thao tác vào Danh sách hoặc lược tả cho thấy việc sử dụng ArrayList của tôi là một vấn đề (rất hiếm)

Như những gì cần chọn trong trường hợp thứ hai, Chuỗi SO.com có ​​một số thông tin chi tiết hữu ích: List implementations: does LinkedList really perform so poorly vs. ArrayList and TreeList?

Answer 2

danh sách liên kết là nhanh hơn để thêm/xóa các phần tử bên trong (ví dụ: không phải đầu hoặc đuôi)

Danh sách nhanh hơn để lặp lại

Answer 3

Đó là sự cân bằng cổ điển giữa chèn tối ưu hóa so với truy xuất. Sự lựa chọn chung cho nhiệm vụ khi bạn mô tả nó là ArrayList.

Answer 4

ArrayList là tốt cho mục đích (và hầu hết các mục đích khác) của bạn. Nó có chi phí bộ nhớ rất nhỏ và có hiệu suất khấu hao tốt cho hầu hết các hoạt động. Các trường hợp nó không phải là lý tưởng là tương đối hiếm:

• Danh sách ist rất lớn
• Bạn thường xuyên cần phải làm một trong những hoạt động:
  • Add/gỡ bỏ các mục trong lặp
  • Hủy bỏ mục từ đầu danh sách

Answer 5

Nếu bạn chỉ thêm ở cuối danh sách, ArrayList phải ổn. Từ các tài liệu của ArrayList:

Các chi tiết của chính sách tăng trưởng không được chỉ định ngoài thực tế rằng việc thêm một yếu tố có thời gian khấu hao liên tục tốn

và ArrayList cũng nên sử dụng ít bộ nhớ hơn so với một danh sách liên kết vì bạn không cần sử dụng không gian cho các liên kết.

Answer 6

Tùy thuộc vào hồ sơ sử dụng của bạn.

Bạn có thêm vào cuối danh sách không? Cả hai đều tốt cho việc này. Bạn có thêm vào đầu danh sách không? LinkedList là tốt hơn cho việc này. Bạn có cần quyền truy cập ngẫu nhiên (bạn có bao giờ gọi số get(n) trên đó) không? ArrayList là tốt hơn cho việc này.

Cả hai đều lặp lại tốt, cả hai lần triển khai Iterator là O (1) cho next().

Nếu nghi ngờ, hãy thử nghiệm ứng dụng của riêng bạn với từng triển khai và thực hiện lựa chọn của riêng bạn.

Answer 7

Tôi biết tôi đến trễ nhưng, có lẽ, this page có thể giúp bạn, không chỉ bây giờ, nhưng trong tương lai ...

Answer 8

Tôi đoán đây sẽ là một khởi đầu tốt đẹp: http://www.odi.ch/prog/design/newbies.php#26 Nó cho thấy sự khác biệt về hiệu suất các triển khai khác nhau của Danh sách.

Answer 9

Với tiêu chí của bạn, bạn nên sử dụng LinkedList.

LinkedList thực hiện giao diện Deque có nghĩa là nó có thể thêm vào đầu hoặc cuối danh sách trong thời gian không đổi (1). Ngoài ra, cả ArrayList và LinkedList sẽ lặp lại trong (N) thời gian.

Bạn KHÔNG nên sử dụng ArrayList đơn giản chỉ vì chi phí thêm phần tử khi danh sách đầy. Trong trường hợp này, việc thêm phần tử sẽ là (N) vì mảng mới được tạo và sao chép tất cả các phần tử từ mảng này sang mảng khác.

Ngoài ra, ArrayList sẽ chiếm nhiều bộ nhớ hơn vì kích thước mảng sao lưu của bạn có thể không được lấp đầy hoàn toàn.