Mục lục
ArrayList và LinkedList là 2 implementation nổi tiếng của List interface, chúng được sinh ra với các mục đích sử dụng khác nhau mà trong bài viết này chúng ta sẽ cùng nhau tìm hiểu.
ArrayList
Nội bộ bên trong ArrayList sử dụng một array để triển khai List interface. Vì array có kích thước cố định nên ArrayList sẽ tại một array với kích thước cố định ban đầu. Trong quá trình sử dụng nếu số lượng phần tử cần được lưu vượt quá kích thước của array thì nó sẽ khởi tạo một array mới với kích thước lớn hơn để lưu trữ.
Thêm phần tử
Khi chúng ta khởi tạo một ArrayList rỗng, nó sẽ khởi tạo một array nội bộ bên trong (gọi là backing array) với kích thước mặc định là 10.
Khi thêm một phần tử vào ArrayList mảng backing array vẫn còn chỗ chứa thì cung việc đơn giản chỉ là thêm nó vào vị trí tiếp theo liền kề vị trí cuối cùng được thêm vào backing array.
backingArray[size] = newItem; size++;
Vì vậy trong trường hợp tốt nhất và trung bình thì time complexity là O(1). khá nhanh. Tuy nhiên, khi backing array trở nên nên đầy thì việc thêm phần tử trở nên phức tạp hơn.
Để thêm một phần tử mới, chúng ta cần khởi tạo một backing array mới với dung lượng lớn hơn, sau đó sao chép toàn bộ phần tử từ backing array cũ sang backing array mới. Cuối cùng là thêm phần tử mới vào backing array mới. Vì thế trong trường hợp này việc thêm phần tử có time complexity là O(n).
Truy cập theo index
Việc truy xuất các phần tử theo index trong ArrayList là một điều tuyệt vời, chúng ta chỉ tốn O(1) để lấy một phần tử tại vị trí index được chỉ định.
Xoá phần tử tại vị trí index
Giả sử chúng ta muốn xoá phần tử tại vị trí index 6 ra khởi ArrayList. Quá trình này sẽ diễn ra như hình bên dưới.
Sau khi xoá phần tử tại vị trí index 6, chúng ta phải du chuyển các phần tử ngay sau đó về phía bên trái một đơn vị.Vì vậy, time complexity là O(1) ở trường hợp tốt nhất và O(n) ở mức trung bình và trường hợp xấu nhất.
Ứng dụng và hạn chế
hông thường, ArrayList là lựa chọn mặc định cho nhiều nhà phát triển khi họ cần List implementation. Thực tế thì nó sẽ là một lựa chọn tốt khi các hoạt động đọc dữ liệu diễn ra nhiều hơn số lần ghi.
Đôi khi chúng ta cần đọc và ghi thường xuyên như nhau. Nếu chúng ta có ước tính về số lượng phần tử tối đa có thể, thì việc sử dụng ArrayList vẫn có ý nghĩa. Nếu đúng như vậy, chúng ta có thể khởi tạo ArrayList với dung lượng ban đầu:
int possibleUpperBound = 10_000; List<String> items = new ArrayList<>(possibleUpperBound);
Việc này sẽ giúp chúng ta giảm thiểu tối đa việc phải phân bổ lại array khi kích thước của nó không còn đủ để lưu trữ.
Ngoài ra, array được đánh chỉ mục với giá trị kiểu int trong Java, vì vậy số lượng phần tử tối đa được lưu trữ bên trong ArrayList không vượt quá 2^32.
LinkedList
LinkedList, như cái tên thì nó sử dụng các node liên kết để lưu trữ và truy xuất các phần tử. Ví dụ
Mỗi node chứa 2 con trỏ, trỏ đến phần tử liền trước và liền sau nó, cấu trúc dữ liệu này còn được gọi là doubly linked.
Thêm phần tử
Để thêm một phần tử trong LinkedList, chúng ta chỉ cần trỏ last element đến phần tử được thêm mới.
Và sau đó cập nhật con trỏ last.
Trải qua 2 hoạt động trên, time complexity để thêm một phần tử trên Linkedlist luôn là O(1).
Truy cập theo index
Không giống như ArrayList, để truy cập một phần tử tại vị trí index chúng ta cần đi qua lần lượt từng phần tử trước đó đến khi đi đến được vị trí của phần tử cần truy xuất. Vì vậy trong trường hợp trung bình và xấu nhất thì time complexity là O(n).
Xoá phần tử tại vị trí index
Để xoá một phần tử trong Linkedlist, chúng ta cũng cần duyệt qua các phần tử cho đến khi gặp được phần tử cần xoá và sau đó ngắt lên kết giữa node bị xoá với node trước và sau nó. Vì vậy trong trường hợp trung bình và xấu nhất thì time complexity là O(n).
Ứng dụng
LinkedList phù hợp hơn ArrayList khi các hoạt động thêm phần tử xảy ra thường xuyên hơn là đọc. Ngoài ra, nó có thể được sử dụng trong các trường hợp việc đọc dữ liệu đa số là đọc phần tử đầu tiên và cuối cùng.
Nguồn