So sánh arraylist và linkedlist java

Nhìn từ diagram ở trên, thì tất cả đều implement List Interface. Chúng khá giống nhau về cách sử dụng. Điểm khác nhau chính là cách hoạt động của chúng sẽ dẫn đến sự khác nhau về performance cho những trường hợp sử dụng khác nhau.

• ArrayList được thiết kế như một resizable array. Nếu có thêm nhiều phần tử được thêm vào, kích thước của nó sẽ được tự động tăng lên. Những phần tử của nó có thể được truy cập trực tiếp bằng cách sử dụng các method get và set.
• LinkedList được thiết kế như một double linked list. Performance của nó trong việc add và remove tốt hơn so với ArrayList, nhưng lại kém hơn khi sử dụng các method get và set.
• Vector thì giống với ArrayList, chỉ khác là nó được synchronized. ArrayList sẽ là sự lựa chọn tốt hơn nếu chương trình của bạn thread-safe.

Vector và ArrayList yêu cầu nhiều không gian lưu trữ hơn những phần tử đã được add vào. Đọc thêm ở

https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html https://docs.oracle.com/javase/7/docs/api/java/util/Vector.html

LinkedList implement List, tuy nhiên nó cũng implement Queue interface, nên sẽ có thêm các method khác so với ArrayList và Vector, chẳng hạn như offer(), peek(), pool() ... . Note: capacity mặc định khi khởi tạo của ArrayList là tương đối nhỏ,một thói quen tốt khi khởi tạo ArrayList là tạo nó với capacity lớn hơn (tùy trường hợp), điều này có thể tránh việc resize khi thêm nhiều phần tử vào list.

3. ArrayList example

ArrayList al = new ArrayList();
al.add(3);
al.add(2);
al.add(1);
al.add(4);
al.add(5);
al.add(6);
al.add(6);
Iterator iter1 = al.iterator();
while(iter1.hasNext()){
System.out.println(iter1.next());
}

4. LinkedList example

LinkedList ll = new LinkedList();
ll.add(3);
ll.add(2);
ll.add(1);
ll.add(4);
ll.add(5);
ll.add(6);
ll.add(6);
Iterator iter2 = al.iterator();
while(iter2.hasNext()){
System.out.println(iter2.next());
}

Nhìn vào những ví dụ trên này, thì ArrayList và LinkedList sử dụng khá giống nhau. Điểm khác nhau thật sự nằm ở sự triển khai và hoạt động phía bên trong của chúng

5. Vector

Vector gần giống với ArrayList. điểm khác biệt là Vector được synchronize. Vì vậy, nó sẽ tốn tài nguyên hơn so với ArrayList. Thông thường, hầu hết mọi người sẽ sử dụng ArrayList thay vì Vector, họ sẽ tự điều khiển việc synchronize theo cách của họ.

6. Performance of ArrayList vs LinkedList

Bảng độ phức tạp của ArrayList & LinkedList :

Tôi sử dụng đoạn code sau để test performance

ArrayList arrayList = new ArrayList();
LinkedList linkedList = new LinkedList();
// ArrayList add
long startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
arrayList.add(i);
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("ArrayList add:  " + duration);
// LinkedList add
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
linkedList.add(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList add: " + duration);
// ArrayList get
startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
arrayList.get(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("ArrayList get:  " + duration);
// LinkedList get
startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
linkedList.get(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList get: " + duration);
// ArrayList remove
startTime = System.nanoTime();
for (int i = 9999; i >=0; i--) {
arrayList.remove(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("ArrayList remove:  " + duration);
// LinkedList remove
startTime = System.nanoTime();
for (int i = 9999; i >=0; i--) {
linkedList.remove(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList remove: " + duration);

Kết quả :

ArrayList add: 13265642
LinkedList add: 9550057
ArrayList get: 1543352
LinkedList get: 85085551
ArrayList remove: 199961301
LinkedList remove: 85768810

Sự khác biệt về hiệu suất của chúng là điều dễ nhận thấy. LinkedList nhanh hơn trong quá trình add và remove, nhưng chậm hơn trong get. Dựa trên bảng độ phức tạp thuật toán ở trên và kết quả test, chúng ta có thể biết được khi nào nên dùng cái gì. Nói ngắn gọn , LinkedList nên được sử dụng nếu :

Mảng cơ bản trong Java là cố định về số phần tử, nghĩa là sau khai báo chúng không thể mở rộng, hay cắt bớt số phần tử. Nếu muốn có thêm chức năng này thì dùng ArrayList trong package java.util

import java.util.ArrayList; //... ArrayList colors = new ArrayList(); Bạn cũng có thể khai báo chi ngay ra kiểu các phần tử mảng này lưu trữ

//Khai báo kiểu phần tử String, khởi tạo với 10 phần tử ArrayList colors = new ArrayList(10); Nên nhớ ArrayList lưu giữ các phần tử là đối tượng, nên các kiểu nguyên thủy int, double, float ... không dùng được. Thay vào đó hãy dùng các lớp tương ứng như Integer, Double, Float ...

Một số phương thức ArrayList

• add(Object o) thêm phần tử vào cuối
• add(int index, Object element) chèn phần tử vào vị trí index
• remove(int index) xóa phần tử có chỉ số index
• clear() xóa mọi phần tử
• contains(Object o) kiểm tra mảng có chứa phần tử
• get(int index) lấy phần tủ có chỉ số index
• indexOf(Object o) lấy chỉ số trong mảng của phần tử
• size() lấy số phần tử
• toArray() chuyển thành mảng

import java.util.ArrayList; public class MyClass {

public static void main(String[ ] args) {  
    ArrayList<String> colors = new ArrayList<String>(3);
    colors.add("Red");  
    colors.add("Blue");  
    colors.add("Green");  
    colors.add("Orange");  
    colors.remove("Green");  
    colors.add("Pink");  
    colors.add("Yellow");
    System.out.println(colors.get(1));  
    System.out.println(colors.contains("Orange"));  
    System.out.println(colors.size());  
    System.out.println(colors);  
}  

  Blue  
  true  
  5  
  [Red,Blue,Orange,Pink,Yellow]  */

LinkedList

LinkedList có cú pháp, khai báo rất giống với ArrayList, bạn dễ dàng đổi từ ArrayList sang LinkedList bằng cách thay kiểu đối tượng.

Điều khác biết giữa LinkedList và ArrayList là cách chúng lưu trữ dữ liệu. ArrayList tốt để lưu trữ và truy cập dữ liệu, nó gần giống với mảng thông thường. LinkedList thì tốt để tương quản lý dữ liệu, như chèn và xóa một lượng lớn phần tử.

ArrayList và LinkedList khác nhau như thế nào?

ArrayList: Thích hợp cho việc lưu trữ và truy cập dữ liệu khi bạn cần nhanh chóng truy cập các phần tử theo chỉ số. Ví dụ: danh sách điểm của một lớp học. LinkedList: Thích hợp cho các thao tác thêm/xoá dữ liệu thường xuyên, chẳng hạn như danh sách cuộc gọi hoặc hàng đợi (queue) với việc thêm/xoá phần tử ở cả hai đầu.

ArrayList và LinkedList khi nào đúng cái 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.

Hoạt động xóa trong LinkedList là nhanh hơn trong ArrayList tại sao?

Thao tác thêm và xóa phần tử với LinkedList nhanh hơn ArrayList. Bởi vì nó không cần sắp xếp lại các phần tử sau khi thêm hoặc xóa. Nó chỉ cần cập nhật lại tham chiếu tới phần tử phía trước và sau nó.

Sự khác biệt giữa ArrayList và vector là gì?

Khác nhau của ArrayList và VectorVector là synchronized. ArrayList là nhanh hơn vì nó là non-synchronized. Vector là chậm hơn ví nó là synchronized. Tức là, trong môi trường đa luồng, các thread giữ nó ở trong trạng thái runnable hoặc non-runnable cho đến khi thread hiện tại giải phóng đối tượng đó.