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

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

  1. Pingback: Stack và Queue trong Java » Thach Le

  2. Pingback: Phân biệt LinkedList và ArrayList trong Java (phần 2) » Thach Le

Tham gia bình luận