Danh sách được sử dụng rất nhiều trong quá trình chúng ta lập trình và mảng là kiểu mà chúng ta hay sử dụng nhất. Nhưng đôi khi mảng thông thường không thể đáp ứng được hết nhu cầu sử dụng của chúng ta như kích thước không thể thay đổi chẳng hạn. Vì thế có 2 loại vê cấu trúc dữ liệu mà chúng ta thường dùng để thay thế đó chính là ArrayList và LinkedList. Cả 2 đều giúp chúng ta sử dụng dễ dàng hơn. Nhưng đôi khi chúng ta không biết phải sử dụng cái nào cho hiệu quả. Vậy nên bài blog này sẽ phân tích để giúp mọi người hiểu rõ hơn và tối ưu tốc độ của code hơn nhé.
Trước hết, chúng ta cùng phải hiểu ArrayList và LinkedList là gì? Và chúng quản lý các phần tử như thế nào?
- ArrayList là dùng một mảng động (như mảng thường nhưng có thể thay đổi kích thước và các phương thức thêm) để lưu trữ phần tử.
- LinkedList sử dụng danh sách liên kết để lưu trữ phần tử. Mỗi phần thử có thể được gọi là 1 node trong danh sách.
Vậy cả 2 đều dùng để lưu trữ danh sách. Giờ chúng ta cùng xem sự khác nhau của chúng nhé.
Chúng khác nhau ở những đặc điểm sau:
- Cách lưu trữ phần tử: Định nghĩa đã nêu rõ rồi đúng không nào
- ArrayList thêm và xóa phần tử chậm hơn LinkedList: Điều này khá dễ hiểu vì LinkedList chỉ cần thay đổi luồng trỏ của các node trong danh sách nên độ phức tạp là O(1) còn ArrayList phải tăng/lùi tất cả những vị trí sau vị trí muốn thêm/xóa nên độ phức tạp là O(n).
- ArrayList truy xuất phần tử nhanh hơn LinkedList: ArrayList muốn truy xuất đến phân tử thứ mấy trong danh sách thì chỉ cần gọi vị trí đó ra là được nên mất O(1) phức tạp, còn LinkedList thì phải duyệt qua các phần tử trước đó thì mới truy xuất được đến phần tử cần lấy nên độ phức tạp là O(n)
- ArrayList chỉ có thể hoạt động như 1 list thông thường, còn LinkedList có thể hoạt động như ArrayList, stack, queue. (stack và queue mình sẽ nói đến ở bài blog khác nhé)
- ArrayList yêu cầu ít bộ nhớ hơn LinkedList: Vì ngoài lưu trữ giá trị thì các node trong LinkedList còn phải chứa các tham chiếu đến phần tử trước, sau của nó nữa.
Như vậy mọi người có lẽ đã hiểu rõ về 2 loại danh sách thường sử dụng này.
Author: Nguyễn Minh Quân
Đăng ký nhận bộ tài liệu kỹ năng dành cho lập trình viên (video hướng dẫn + slide) tại đây
Xem thêm các bài chia sẻ, hướng dẫn học lập trình khác tại đây.
