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.

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

Chào mừng các bạn đã quay trở lại với thachleblog. Bài viết hôm nay mình sẽ phân tích điểm chung và khác biệt giữa LinkedList và ArrayList trong Java. Hai cấu trúc dữ liệu rất quen thuộc trong lập trình Java. Câu hỏi này cũng rất thường gặp trong các buổi phỏng vấn Java. Vậy điểm khác biệt giữa LinkedList và ArrayList là gì, quan trọng nhất là khi nào dùng LinkedList và ArrayList. Nào, chúng ta cùng bắt đầu nhé.

LinkedList và ArrayList đều là 2 implementation của List interface, vì vậy chúng đều mang đặc điểm chung của List.
collection-interface

Hình minh họa đặc điểm kế thừa của ArrayList và LinketList, nguồn

LinkedList implement 2 interface là List và Queue, ArrayList chỉ implement interface List do đó cấu trúc lưu trữ của LinkedList khác ArrayList.

LinkedList

LinkedList có single LinkedList, double Linked List… vì LinkedList trong Java là double Linked nên khi mình nhắc đến Linked List các bạn sẽ hiểu là mình đang nói đến double LinkedList nhé.

Cấu trúc dữ liệu của LinkedList bao gồm các node, tuy nhiên LinkedList chỉ lưu địa chỉ của node đầu tiên (head) và node cuối cùng (tail)

Head sẽ có 1 liên kết chỉ đến null và 1 liên kết chỉ đến node tiếp theo. Các node tiếp theo cũng sẽ có 1 liên kết chỉ đến node kề trước và node tiếp theo, cứ như vậy đến tail. Tail cũng sẽ có 1 liên kết chỉ đến node kề phía trước và 1 liên kết chỉ đến null (để xác định node cuối cùng)

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

Hình minh họa cấu trúc dữ liệu của Linked List (Single)

Cần chú ý các node này sẽ chiếm giữ các ô nhớ không liên tục trên bộ nhớ, khác với Array và ArrayList sẽ chiếm giữ các ô nhớ liên tục. Chính điều này sẽ quyết định đến tốc độ khi thao tác trên LinkedList.

Insert


Khi thêm một phần tử vào LinkedList bằng lệnh add(), phần tử đó sẽ được thêm vào sau tail, con trỏ trỏ đến tail chỉ cần trỏ đến phần tử được thêm vào. Tương tự khi thêm phần tử vào head. Khi thêm phần tử vào vị trí khác head và tail, LinkedList cũng chỉ việc thay đổi các con trỏ kề trước và sau. Do đó độ phức tạp là O(1)

Delete

Sự thay đổi tương tự như khi insert.

Get element

Do đặc điểm LinkedList chỉ lưu giá trị của 2 node head và tail, do đó để tìm một phần tử trong LinkedList, trình xử lý phải duyệt từ phần tử đầu hoặc phần tử cuối (tùy vào index của phần tử cần tìm). Do đó, độ phức tạp sẽ là O(n).

Bài viết phân biệt LinkedList và ArrayList phần 1 đến đây là hết. Các bạn nhớ theo dõi phần 2 để rõ hơn nhé.