So sánh linkedlist và array list

Cả hai lớp ArrayList và LinkedList đều được implements từ giao tiếp List và duy trì thứ tự của phần tử được thêm vào.

Cả hai lớp này đều là lớp không đồng bộ (non-synchronized). Có vài sự khác nhau giữa ArrayList và LinkedList được đưa ra như trong bảng dưới đây:

Dưới đây là ví dụ đơn giản về việc sử dụng ArrayList và LinkedList trong java

import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class ArraylistAndLinkedListExample { public static void main(String args[]) { List<String> arrayList = new ArrayList<String>(); arrayList.add("Java"); arrayList.add("C++"); arrayList.add("PHP"); arrayList.add("Python"); List<String> linkedList = new LinkedList<String>(); linkedList.add("Hiberante"); linkedList.add("Struts2"); linkedList.add("Spring"); linkedList.add("Mybatis"); System.out.println("arraylist: " + arrayList); System.out.println("linkedlist: " + linkedList); } }

arraylist: [Java, C++, PHP, Python]
linkedlist: [Hiberante, Struts2, Spring, Mybatis]

Chào mọi ng ! Mình có đọc qua các cách giải thích từ trang nước ngoài nhưng vẫn chưa hiểu, và đã có thành viên hỏi về chủ đề tương tự nhưng mình thấy vẫn chưa đủ. Cái nào nhanh hơn? Hay sử dụng như thế nào để tối ưu nhất giữa ArrayList và List??

Cám ơn mọi ng

Sự khác nhau giữa LinkedList và ArrayList

Sự khác nhau lớn nhất giữa ArrayList và LinkedList nằm ở chỗ có cấu trúc dữ liệu khác, nếu bạn hiểu được cấu trúc của 2 ArrayList và LinkedList thì những khác biệt dưới đây sẽ rất dễ hiểu

1. Array là cấu trúc dữ liệu có chỉ mục(index) nên tìm kiếm trên Array nhanh hơn, độ phức tạp khi tìm kiếm một phần tử trong Array là O(1). Trái lại, với LinkedList chúng ta không thể truy cập phần tử theo chỉ mục hoặc ngẫu nhiên mà phải duyệt qua các phần tử nên độ phức tạp là O(n)

2. Chèn phần tử mới vào LinkedList dễ dàng và nhanh hơn so với ArrayList vì LinkedList không có rủi ro về thay đổi kích thước và sao chép dữ liệu sang mảng mới nếu mảng đầy chỉ với độ phức tạo O(1), nhưng với ArrayList thì rất hạn chế để thực hiện thêm mới và sao chép dữ liệu khi đầy thì độ phức tạp là O(n). Bên cạnh đó, ArrayList cần cập nhật lại chỉ mục nếu thêm một phần tử vào giữa mảng.

3. Xóa phần tử trong mảng giống như thêm mới thì LinkdedList có hiệu suất tốt hơn ArrayList.

4. LinkedList chiếm nhiều bộ nhớ hơn ArrayList vì trong ArrayList mỗi phần tử chỉ chứa một đối tượng dữ liệu còn LinkedList thì mỗi phần tử(node) lại chứa dữ liệu và địa chỉ của phần tử trước và phần tử sau.

Khi nào dùng LinkedList và ArrayList

LinkedList không được dùng nhiều như ArrayList nhưng có một số trường hợp LinkedList là sự lựa chọn hợp lí hơn ArrayList. Chúng ta nên dùng LinkedList nếu:

1. Ứng dụng không cần truy cập ngẫu nhiên trong mảng. Vì nếu cần chúng ta sẽ phải duyệt qua mảng để tìm kiếm phần tử phù hợp, độ phức tạp là O(n)

2)Ứng dụng thao tác thêm mới, xóa nhiều hơn truy cập dữ liệu. Khi đó thêm mới và xóa không phải thay đổi kích thước mảng nên nhanh hơn ArrayList.

2 Likes

Bạn còn biết List không? Tại mình cần biết hết để lựa chọn cái nào. Cám ơn b

Không so sánh được vì 2 cái này khác nhau, List là một interface, và ArrayList có thể xem là một implement của List.

Nếu dùng List (List a = new ArrayList(); ) sẽ có ưu điểm là bạn có thể chuyển đổi ArrayList sang Vector, LinkedList dễ dàng thông qua các method có trong List interface, còn nếu dùng kiểu: ArrayList a = new ArrayList(); thì bạn sẽ khó làm được điều này, bạn sẽ chỉ dùng được những method trong ArrayList.

Tóm lại là xem kỹ về interface trong OOP để hiểu phần này dễ dàng hơn.

7 Likes

Sơ ý quá, mình hiểu rồi. Cám ơn b nhiều

Tại mình cần biết hết để lựa chọn cái nào

Trong Java List là interface, là giao diện bên ngoài chứ bản thân nó k có gì vì vậy nó không thể tạo ra đối tượng mới. Muốn sử dụng List bạn phải implement nó qua arraylist và linklist.

Nếu bạn hỏi List trong C# thì List có thể sử dụng và tạo đối tượng như arraylist. Vì nó là 1 Generic class implement từ IList, ICollection, IEnumerable.

Điều đặc biệt quan trọng là nếu bạn dùng List. Bạn không cần ép kiểu trong trường hợp dùng các obj khác nhau như arraylist

1 Like