Table of Contents
Trong các bài viết trước, tôi đã giới thiệu với các bạn ArrayList và LinkedList. Trong bài này, tôi sẽ so sánh sự giống nhau, khác nhau của 2 collection này.
1. Giống nhau giữa ArrayList và LinkedList
Cả hai lớp ArrayList và LinkedList đều được implements từ List Interface và duy trì thứ tự của phần tử được thêm vào. Cả hai lớp này đều là lớp không đồng bộ (non-synchronized).
2. Khác nhau giữa ArrayList và LinkedList
ArrayList | LinkedList | |
Cấu trúc dữ liệu (Structure) | ArrayList sử dụng mảng động để lưu trữ các phần tử. ArrayList là một cấu trúc dữ liệu dựa trên chỉ mục (index), trong đó mỗi phần tử (element) được liên kết với một chỉ mục. | LinkedList sử dụng danh sách liên kết (Doubly Linked List) để lưu trữ các phần tử. Các phần tử trong LinkedList được gọi là node, mỗi node cần lưu trữ 3 thông tin: tham chiếu phần tử trước nó, giá trị của phần tử và một tham chiếu tới phần tử kế tiếp. |
Thao tác thêm và xóa (Insertion And Removal) | Thao tác thêm và xóa phần tử với ArrayList là chậm bởi vì nó sử dụng nội bộ mảng. Bởi vì sau khi thêm hoặc xóa các phần tử cần sắp xếp lại. Độ phức tạp: O(n). | Thao tác thêm và xóa phần tử với LinkedList nhanh hơn ArrayList. Bởi vì nó không cần sắp xếp lại các phần tử sau khi thêm hoặc xóa. Nó chỉ cần cập nhật lại tham chiếu tới phần tử phía trước và sau nó. Độ phức tạp: O(1). |
Thao tác tìm kiếm hoặc truy xuất phần tử (Retrieval) | Truy xuất phần tử trong ArrayList nhanh hơn LinkedList. Bởi vì các phần tử trong ArrayList được lưu trữ dựa trên chỉ mục (index). Độ phức tạp: O(1). | Thao tác truy xuất phần tử trong LinkedList chậm hơn nhiều so với ArrayList. Bởi vì, nó phải duyệt qua lần lượt các phần tử từ đầu tiên cho đến cuối cùng. Độ phức tạp: O(n). |
Truy xuất ngẫu nhiên (Random Access) | ArrayList có thể truy xuất ngẫu nhiên phần tử. | LinkedList không thể truy xuất ngẫu nhiên. Nó phải duyệt qua tất cả các phần tử từ đầu tiên đến phần tử cuối cùng để tìm phần tử. |
Trường hợp sử dụng (Usage) | ArrayList chỉ có thể hoạt động như một list vì nó chỉ implements giao tiếp List. | LinkedList có thể hoạt động như một ArrayList, stack (hàng đợi), queue (hàng đợi), Singly Linked List and Doubly Linked List vì nó implements các giao tiếp List và Deque. |
Sử dụng bộ nhớ | ArrayList yêu cầu ít bộ nhớ hơn so với LinkedList. Bởi vì ArrayList chỉ lưu trữ dữ liệu (data) của nó và chỉ mục (index). | LinkedList yêu cầu nhiều bộ nhớ hơn so với ArrayList. Bởi vì LinkedList lưu giữ thông tin của nó và tham chiếu tới phần tử trước và sau nó. |
Khi nào sử dụng? | ArrayList tốt hơn trong việc lưu trữ và truy xuất dữ liệu (get). | LinkedList tốt hơn trong việc thao tác dữ liệu (thêm/ xóa). |
Related posts:
Java Program to Implement Binomial Heap
Getting Started with Stream Processing with Spring Cloud Data Flow
New Features in Java 14
Spring RequestMapping
Java Program to Implement Hash Tables with Double Hashing
Java Program for Douglas-Peucker Algorithm Implementation
Java Copy Constructor
Creating Docker Images with Spring Boot
Apache Commons Collections BidiMap
Java Program to Implement Traveling Salesman Problem using Nearest neighbour Algorithm
Registration with Spring Security – Password Encoding
Java Program to Implement AVL Tree
Java Program to Find Median of Elements where Elements are Stored in 2 Different Arrays
Java Program to Implement Gale Shapley Algorithm
HttpClient 4 – Follow Redirects for POST
Spring Cloud AWS – Messaging Support
Java Program to Implement Fermat Primality Test Algorithm
Java Program to Find a Good Feedback Vertex Set
Sắp xếp trong Java 8
Spring Security – security none, filters none, access permitAll
Spring Boot Actuator
Java Web Services – JAX-WS – SOAP
Calling Stored Procedures from Spring Data JPA Repositories
A Guide to HashSet in Java
Java Program to Implement Adjacency List
Concurrent Test Execution in Spring 5
Spring Boot - Bootstrapping
Spring Boot - Service Components
Giới thiệu về Stream API trong Java 8
Spring Cloud AWS – S3
Java Program to Implement the RSA Algorithm
Getting a File’s Mime Type in Java