Trang chủ » Blog » Phân biệt ArrayList và LinkedList

Phân biệt ArrayList và LinkedList

bởi CodeGym | 06/12/2023 17:30 | Blog

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:

  1. Cách lưu trữ phần tử: Định nghĩa đã nêu rõ rồi đúng không nào
  2. 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).
  3. 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 thi 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)
  4. 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é)
  5. 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

Tìm hiểu thêm về mô hình Coding Bootcamp tại đây

Tags:

0 Lời bình

Gửi Lời bình

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

BÀI VIẾT LIÊN QUAN

BẠN MUỐN HỌC LẬP TRÌNH?

GỌI NGAY

098 953 44 58

Đăng ký tư vấn lộ trình học lập trình

Đăng ký tư vấn, định hướng lộ trình học và giải đáp các thắc mắc về ngành nghề – Miễn phí – Online.

9 + 14 =

TƯ VẤN VỀ LỘ TRÌNH HỌC NGHỀ LẬP TRÌNH TẠI CODEGYM
TƯ VẤN VỀ LỘ TRÌNH HỌC NGHỀ LẬP TRÌNH TẠI CODEGYM