Phân biệt LinkedList và ArrayList trong Java (phần 2)

Chào mừng các bạn đã quay trở lại với thachleblog. Ở bài trước, mình đã phân tích cấu trúc dữ liệu của LinkedList, ở bài này, mình sẽ tiếp tục phân tích cấu trúc dữ liệu của ArrayList. Qua đó, hy vọng có thể giúp các bạn phân biệt và sử dụng LinkedList và ArrayList đạt hiệu quả cao nhất.

ArrayList

Cấu trúc lưu trữ của ArrayList là gồm các phần tử chiếm giữ các địa chỉ liên tục trong bộ nhớ. Do đó, các thao tác trên ArrayList sẽ có điểm khác biệt so với trên LinkedList.

Hình minh họa cấu trúc ArrayList

Hình minh họa cấu trúc lưu trữ của ArrayList

Insert

Khi insert 1 phần tử vào ArrayList, trường hợp tốt nhất thì ArrayList chỉ cần cập nhật index cho phần tử được thêm vào. Trường hợp xấu là ArrayList không đủ vùng nhớ (mặc định là chứa được 10 phần tử), trình xử lý phải copy toàn bộ các element sang một vùng nhớ khác lớn hơn (x1.5 lần).

Tương tự trong trường hợp insert một phần tử vào vị trí đầu hoặc giữa ArrayList, trường hợp tốt nhất ArrayList sẽ chỉ cập nhật lại index cho các phần tử có index lớn hơn index của phần tử tại vị phần tử mới được thêm vào. Trường hợp xấu tương tự như khi thêm vào cuối. Do đó, độ phức tạp của thao tác insert là O(n)

Delete

Độ phức tạp tương tự như insert.

Get index

Vì các phần tử trên ArrayList nằm liên tục trong vùng nhớ, nên việc tìm kiếm các phần tử của ArrayList là như nhau. Độ phức tạp là O(1).

Tổng kết so sánh giữa LinkedList và ArrayList

Sự khác nhau giữa thao tác trên LinkedList và ArrayList được tổng hợp như sau:

Hình minh họa thao tác trên LinkedList và ArrayList

Tóm lại, chúng ta chỉ cần nhớ khi cần thực hiện nhiều thao tác thêm hoặc xóa element vào List, ta ưu tiên dùng LinkedList. Khi cần thực hiện nhiều đối với thao tác get element trên List, ta ưu tiên dùng ArrayList.

Bài viết phân biệt LinkedList và ArrayList đã hết. Rất mong nhận được ý kiến đóng góp của tất cả các bạn. Hẹn gặp lại các bạn ở các bài viết sau. Xin cảm ơn.

Tham gia bình luận