Java Collection - List
List
là một giao diện con củaCollection
, nó cho phép lưu trữ các phần tử có thể lặp lại.
Giới thiệu về List
List
là một giao diện mô tả một hàng đợi có thứ tự.
AbstractList
là một lớp trừu tượng kế thừa từ AbstractCollection
. AbstractList
triển khai tất cả các phương thức trong giao diện List
ngoại trừ size()
và get(int location)
.
AbstractSequentialList
là một lớp trừu tượng kế thừa từ AbstractList
. AbstractSequentialList
triển khai tất cả các phương thức trong giao diện List
liên quan đến việc thao tác trên danh sách dựa trên chỉ mục.
ArrayList và LinkedList
ArrayList
và LinkedList
là hai cách triển khai phổ biến nhất của List
.
ArrayList
được triển khai dựa trên mảng động và có giới hạn về dung lượng. Khi số lượng phần tử vượt quá dung lượng tối đa, nó sẽ tự động mở rộng.LinkedList
được triển khai dựa trên danh sách liên kết hai chiều và không có giới hạn về dung lượng.ArrayList
có tốc độ truy cập ngẫu nhiên nhanh, nhưng tốc độ chèn và xóa ngẫu nhiên chậm.LinkedList
có tốc độ chèn và xóa ngẫu nhiên nhanh, nhưng tốc độ truy cập ngẫu nhiên chậm.- Cả
ArrayList
vàLinkedList
đều không an toàn đối với luồng.
Vector và Stack
Vector
và Stack
được thiết kế để làm các triển khai an toàn đối với luồng của List
và thay thế cho ArrayList
.
Vector
-Vector
tương tự nhưArrayList
, cũng triển khai giao diệnList
. Tuy nhiên, tất cả các phương thức chính trongVector
đều được đồng bộ hóa bằng từ khóasynchronized
, đảm bảo tính an toàn của các hoạt động.Stack
-Stack
cũng là một collection được đồng bộ hóa, các phương thức của nó cũng được đồng bộ hóa bằng từ khóasynchronized
. Nó thực tế là một lớp con củaVector
.
ArrayList
Từ góc độ cấu trúc dữ liệu,
ArrayList
có thể được coi là một danh sách tuyến tính có khả năng mở rộng.
Điểm chính của ArrayList
ArrayList
là một danh sách, tương đương với một mảng động. ArrayList
có dung lượng khởi tạo mặc định là 10
và khi thêm phần tử, nếu dung lượng đã đầy, nó sẽ tự động mở rộng lên 1.5
lần dung lượng ban đầu. Do đó, khi khởi tạo ArrayList
, nên chỉ định dung lượng khởi tạo phù hợp để giảm thiểu chi phí mở rộng.
Định nghĩa của ArrayList
:
Từ định nghĩa của ArrayList, có thể thấy một số đặc điểm cơ bản của ArrayList:
ArrayList
triển khai giao diệnList
và kế thừa từAbstractList
, nó hỗ trợ tất cả các hoạt động củaList
.ArrayList
triển khai giao diệnRandomAccess
, hỗ trợ truy cập ngẫu nhiên.RandomAccess
là một giao diện đánh dấu, nghĩa là “bất kỳ lớp triển khai giao diện này đều hỗ trợ truy cập ngẫu nhiên nhanh chóng”. TrongArrayList
, chúng ta có thể nhanh chóng lấy phần tử bằng chỉ số của nó; đó là truy cập ngẫu nhiên nhanh chóng.ArrayList
triển khai giao diệnCloneable
, mặc định là sao chép nông.ArrayList
triển khai giao diệnSerializable
, hỗ trợ tuần tự hóa, có thể truyền qua tuần tự hóa.
Cơ chế của ArrayList
Cấu trúc dữ liệu của ArrayList
ArrayList bao gồm hai thành phần quan trọng: elementData
và size
.
size
- là kích thước thực tế của mảng động.elementData
- là một mảngObject
dùng để lưu trữ các phần tử được thêm vàoArrayList
.
Tuần tự hóa của ArrayList
ArrayList có khả năng mở rộng động, do đó không phải lúc nào cũng sử dụng toàn bộ mảng để lưu trữ các phần tử. Vì vậy, ArrayList đã tùy chỉnh cách tuần tự hóa của nó. Cụ thể là:
- Mảng lưu trữ phần tử (
elementData
) được đánh dấu bằng từ khóatransient
, cho phép nó bị bỏ qua trong quá trình tuần tự hóa Java. - ArrayList ghi đè các phương thức
writeObject()
vàreadObject()
để kiểm soát quá trình tuần tự hóa mảng chỉ chứa phần tử đã được điền.
💡 Nếu bạn không quen với cách tuần tự hóa Java, bạn có thể tham khảo: Java Serialization
Phương thức khởi tạo của ArrayList
Lớp ArrayList triển khai ba phương thức khởi tạo:
- Phương thức đầu tiên là phương thức khởi tạo mặc định, ArrayList sẽ tạo một mảng rỗng.
- Phương thức thứ hai là phương thức khởi tạo ArrayList với giá trị khởi tạo.
- Phương thức thứ ba là phương thức khởi tạo ArrayList với một tập hợp đã cho.
Khi thêm phần tử vào ArrayList, nếu số lượng phần tử vượt quá dung lượng hiện tại, nó sẽ tính toán dung lượng mới trước khi mở rộng. Việc mở rộng mảng có thể dẫn đến việc sao chép toàn bộ mảng. Do đó, khi khởi tạo ArrayList, nên chỉ định một dung lượng khởi tạo xấp xỉ để giảm số lần mở rộng mảng.
Truy cập phần tử của ArrayList
Việc truy cập phần tử trong ArrayList
được thực hiện dựa trên chỉ số của phần tử đó.
Cách triển khai rất đơn giản, chỉ cần truy cập phần tử trong mảng dựa trên chỉ số, nên tốc độ rất nhanh, có độ phức tạp thời gian là O(1).
Thêm phần tử vào ArrayList
ArrayList
có hai phương thức để thêm phần tử: một là thêm phần tử vào cuối mảng, hai là thêm phần tử vào bất kỳ vị trí nào.
Sự khác biệt giữa hai phương thức thêm phần tử là:
- Khi thêm phần tử vào bất kỳ vị trí nào, tất cả các phần tử ở vị trí đó và sau đó đều phải được sao chép lại.
- Khi thêm phần tử vào cuối mảng, nếu không cần mở rộng, không có quá trình sao chép và sắp xếp các phần tử.
Cả hai phương thức thêm phần tử đều kiểm tra dung lượng của mảng trước khi thêm phần tử. Nếu dung lượng không đủ, nó sẽ tự động mở rộng lên 1.5
lần dung lượng ban đầu.
Các phương thức thêm phần tử của ArrayList
được triển khai dựa trên mã nguồn quan trọng sau:
Khi thực hiện thao tác thêm phần tử (add
), ArrayList
sẽ gọi phương thức ensureCapacityInternal
để đảm bảo rằng dung lượng đủ.
- Nếu dung lượng đủ, dữ liệu sẽ được ghi vào vị trí
size+1
trong mảng vàsize
tăng lên 1. - Nếu dung lượng không đủ, phải sử dụng phương thức
grow
để mở rộng mảng. Dung lượng mới được tính bằng cách nhân dung lượng cũ với1.5
. Quá trình mở rộng mảng thực chất là sao chép mảng gốc thành một mảng mới. Vì vậy, tốt nhất là chỉ định kích thước khởi tạo xấp xỉ khi tạo đối tượngArrayList
để giảm số lần mở rộng mảng.
Xóa phần tử khỏi ArrayList
Phương thức xóa của ArrayList
tương tự như phương thức thêm phần tử vào bất kỳ vị trí nào.
Sau mỗi lần xóa thành công, ArrayList
sẽ thực hiện việc sao chép lại mảng và xóa phần tử cuối cùng.
Fail-Fast của ArrayList
ArrayList
sử dụng modCount
để ghi lại số lần thay đổi cấu trúc. Thay đổi cấu trúc là thêm hoặc xóa ít nhất một phần tử, hoặc điều chỉnh kích thước mảng. Chỉ đơn giản đặt giá trị của một phần tử không được tính là thay đổi cấu trúc.
Khi thực hiện tuần tự hóa hoặc lặp qua ArrayList
, cần so sánh modCount
trước và sau thao tác. Nếu có sự thay đổi, ArrayList
sẽ ném ra ConcurrentModificationException
.
LinkedList
Từ góc độ cấu trúc dữ liệu,
LinkedList
có thể được coi là một danh sách liên kết hai chiều.
Điểm chính của LinkedList
LinkedList
được triển khai dựa trên cấu trúc danh sách liên kết hai chiều. Vì nó là danh sách liên kết hai chiều, nên truy cập tuần tự sẽ rất hiệu quả, trong khi truy cập ngẫu nhiên có hiệu suất thấp.
Định nghĩa LinkedList:
Từ định nghĩa của LinkedList
, chúng ta có thể rút ra một số đặc điểm cơ bản của LinkedList
:
LinkedList
triển khai giao diệnList
và kế thừaAbstractSequentialList
, nó hỗ trợ tất cả các hoạt động củaList
.LinkedList
triển khai giao diệnDeque
, nó cũng có thể được sử dụng như một hàng đợi (Queue
) hoặc hàng đợi hai đầu (Deque
), ngoài ra, nó cũng có thể được sử dụng để triển khai ngăn xếp.LinkedList
triển khai giao diệnCloneable
, mặc định là sao chép nông.LinkedList
triển khai giao diệnSerializable
, hỗ trợ tuần tự hóa.LinkedList
không an toàn đa luồng.
Nguyên lý của LinkedList
Cấu trúc dữ liệu LinkedList
LinkedList
bên trong duy trì một danh sách liên kết hai chiều.
LinkedList
truy cập dữ liệu thông qua con trỏ đầu và cuối (biến first
và last
) của danh sách liên kết.
size
- đại diện cho số lượng nút trong danh sách liên kết, ban đầu là 0.first
vàlast
- lần lượt là con trỏ đầu và cuối của danh sách liên kết.
Node
là một lớp nội bộ của LinkedList
, nó đại diện cho một phiên bản phần tử trong danh sách. Node
chứa ba thành phần:
prev
là nút trước đó của nút hiện tại;next
là nút tiếp theo của nút hiện tại;item
là giá trị chứa trong nút hiện tại.
Tuần tự hóa LinkedList
LinkedList
cũng như ArrayList
, nó cũng tùy chỉnh cách tuần tự hóa của riêng mình. Cụ thể là:
- Đặt
size
(kích thước danh sách liên kết),first
vàlast
(con trỏ đầu và cuối của danh sách liên kết) thànhtransient
, để chúng có thể được bỏ qua trong quá trình tuần tự hóa Java. - Ghi đè phương thức
writeObject()
vàreadObject()
để kiểm soát quá trình tuần tự hóa, chỉ xử lý các phần tử trong danh sách liên kết có thể được liên kết với con trỏ đầu.
Truy cập phần tử trong LinkedList
Cài đặt truy cập phần tử của LinkedList
chủ yếu dựa trên mã nguồn quan trọng sau đây:
Thuật toán để lấy phần tử thứ index của LinkedList
như sau:
- Kiểm tra xem index thuộc nửa trước hay nửa sau của danh sách liên kết.
- Nếu thuộc nửa trước, bắt đầu tìm kiếm từ con trỏ đầu; nếu thuộc nửa sau, bắt đầu tìm kiếm từ con trỏ cuối.
Hiệu suất truy cập phần tử của LinkedList
là O(N) (trường hợp cực đoan, quét qua N/2 phần tử); so với O(1) của ArrayList
, rõ ràng là chậm hơn nhiều.
Khuyến nghị sử dụng vòng lặp lặp qua LinkedList
, không sử dụng vòng lặp for
truyền thống. Lưu ý: cú pháp foreach sẽ được biên dịch thành vòng lặp lặp qua, nhưng trong quá trình lặp, không được phép thay đổi độ dài của List
, tức là không thể thực hiện thêm hoặc xóa phần tử.
Thêm phần tử vào LinkedList
LinkedList
có nhiều phương thức để thêm phần tử:
add(E e)
: Phương thức thêm phần tử mặc định (thêm vào cuối danh sách)add(int index, E element)
: Thêm phần tử vào bất kỳ vị trí nàoaddFirst(E e)
: Thêm phần tử vào đầu danh sáchaddLast(E e)
: Thêm phần tử vào cuối danh sách
Cài đặt thêm phần tử của LinkedList
chủ yếu dựa trên mã nguồn quan trọng sau đây:
Thuật toán như sau:
- Đóng gói dữ liệu mới thêm vào trong
Node
. - Nếu thêm phần tử vào đầu danh sách, thì con trỏ đầu
first
trỏ đếnNode
mới,prev
củafirst
trước đó trỏ đếnNode
mới. - Nếu thêm phần tử vào cuối danh sách, thì con trỏ cuối
last
trỏ đếnNode
mới,next
củalast
trước đó trỏ đếnNode
mới.
Xóa phần tử khỏi LinkedList
Cài đặt xóa phần tử của LinkedList
chủ yếu dựa trên mã nguồn quan trọng sau đây:
Thuật toán như sau:
- Tìm kiếm phần tử cần xóa trong danh sách liên kết, sau đó gọi phương thức
unlink
để xóa nút. - Phương thức
unlink
xóa nút như sau:- Nếu nút hiện tại có nút trước, thì cho nút trước trỏ đến nút tiếp theo của nút hiện tại; nếu không, cho con trỏ đầu của danh sách liên kết trỏ đến nút tiếp theo.
- Nếu nút hiện tại có nút sau, thì cho nút sau trỏ đến nút trước của nút hiện tại; nếu không, cho con trỏ cuối của danh sách liên kết trỏ đến nút trước.
Các vấn đề thường gặp với List
Vấn đề với Arrays.asList
Trong quá trình phát triển ứng dụng, chúng ta thường chuyển đổi mảng gốc thành cấu trúc dữ liệu List để tiếp tục thực hiện các thao tác Stream khác nhau. Thông thường, chúng ta sẽ sử dụng phương thức Arrays.asList để chuyển đổi mảng thành List.
【Ví dụ】Chuyển đổi mảng kiểu nguyên thủy thành List
【Kết quả】
11:26:33.214 [main] INFO com.hnv99.javacore.collections.list.AsListProblem - list:[[I@ae45eb6] size:1 class:class [I
Số lượng phần tử trong mảng là 3, nhưng số lượng phần tử trong danh sách sau khi chuyển đổi là 1.
Từ đó có thể thấy, vấn đề đầu tiên của Arrays.asList là: không thể sử dụng trực tiếp Arrays.asList để chuyển đổi mảng kiểu nguyên thủy.
Nguyên nhân là: phương thức Arrays.asList nhận đối số biến đổi kiểu T có thể thay đổi, và cuối cùng mảng int được coi là một đối tượng và trở thành kiểu T:
Việc lặp qua danh sách như vậy chắc chắn sẽ gây ra lỗi, có hai cách để khắc phục, nếu sử dụng phiên bản Java8 trở lên, bạn có thể sử dụng phương thức Arrays.stream để chuyển đổi, nếu không, bạn có thể khai báo mảng int là một mảng Integer bọc:
【Ví dụ】Cách chuyển đổi mảng số nguyên sang List đúng
【Ví dụ】Chuyển đổi mảng kiểu tham chiếu thành List
Ném ra ngoại lệ java.lang.UnsupportedOperationException
.
Lý do ném ra ngoại lệ là: vấn đề thứ hai của Arrays.asList là: List trả về từ Arrays.asList không hỗ trợ thao tác thêm và xóa. List trả về từ Arrays.asList không phải là ArrayList mà chúng ta mong đợi, mà là lớp ArrayList bên trong của Arrays.
Kiểm tra mã nguồn, chúng ta có thể thấy ArrayList trả về từ Arrays.asList kế thừa từ AbstractList, nhưng không ghi đè phương thức add và remove.
Vấn đề thứ ba của Arrays.asList là: sửa đổi mảng gốc sẽ ảnh hưởng đến List mà chúng ta nhận được. ArrayList thực sự sử dụng trực tiếp mảng gốc.
Cách giải quyết rất đơn giản, chỉ cần tạo một ArrayList mới và khởi tạo List trả về từ Arrays.asList:
Vấn đề với List.subList
List.subList trực tiếp tham chiếu đến List gốc, cũng có thể coi là chia sẻ “lưu trữ”, và thực hiện sửa đổi cấu trúc trực tiếp trên List gốc sẽ dẫn đến lỗi xuất hiện ở SubList.
Lý do gây ra OOM là 1000 danh sách có 100.000 phần tử mỗi danh sách trong vòng lặp không bao giờ được thu hồi, vì nó luôn được tham chiếu mạnh bởi List trả về từ phương thức subList.
Cách giải quyết là:
【Ví dụ】SubList tham chiếu mạnh List gốc
Ném ra ngoại lệ java.util.ConcurrentModificationException
.
Cách giải quyết:
Một cách là không sử dụng trực tiếp SubList trả về từ phương thức subList, mà là tạo một ArrayList mới và chuyển SubList vào trong phương thức khởi tạo để xây dựng một ArrayList độc lập;
Một cách khác là sử dụng phương thức skip và limit của Stream trong Java 8 để bỏ qua các phần tử trong luồng và giới hạn số lượng phần tử trong luồng, cũng có thể đạt được mục đích cắt SubList.