So sánh ArrayList và LinkedList trong Java

Table of Contents

1. Giống nhau giữa ArrayList và LinkedList
2. Khác nhau giữa ArrayList và LinkedList

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).