Giới thiệu
Trong framework Collection, lớp List con của Collection là cấu trúc dữ liệu được sử dụng để lưu trữ dữ liệu có thứ tự và có thể trùng lặp. Bài viết này sẽ phân tích cách các lớp triển khai của List được thực hiện thông qua mã nguồn.
Triển khai List chủ yếu được chia thành hai loại: mảng và danh sách liên kết.
Đặc điểm của mảng:
- Địa chỉ lưu trữ bộ nhớ liên tục
- Hiệu suất truy vấn cao
- Hiệu suất thêm/xóa thấp
- Phù hợp cho kịch bản lưu trữ tuần tự, truy vấn thường xuyên
Đặc điểm của danh sách liên kết:
- Địa chỉ lưu trữ bộ nhớ phân tán
- Hiệu suất truy vấn thấp
- Hiệu suất thêm/xóa cao
- Phù hợp cho kịch bản thêm/xóa thường xuyên mà số lần truy vấn ít
Ngoài ra, khi sử dụng bộ sưu tập, cần xem xét vấn đề an toàn luồng, liệu có thể thao tác an toàn trong tình huống đa luồng hay không.
I. Phân tích nguồn ArrayList
1.1, Khởi tạo ArrayList
Như tên gọi, ArrayList được thực hiện thông qua mảng. Hãy bắt đầu với hàm khởi tạo, ArrayList có ba phương thức khởi tạo:
1 /** Mảng lưu trữ dữ liệu của ArrayList */
2 transient Object[] internalArray;
3
4 /** Mảng rỗng mặc định */
5 private static final Object[] DEFAULT_EMPTY_ARRAY = {}
6
7 /**
8 * Phương thức khởi tạo mặc định: khởi tạo một mảng Object rỗng cho nội bộ
9 * */
10 public ArrayList() {
11 this.internalArray = DEFAULT_EMPTY_ARRAY;
12 }
13
14 /**
15 * Truyền dung lượng cho danh sách
16 * */
17 public ArrayList(int initialCapacity) {
18 if (initialCapacity > 0) {
19 // Khởi tạo mảng Object với dung lượng chỉ định
20 this.internalArray = new Object[initialCapacity];
21 } else if (initialCapacity == 0) {
22 // Khởi tạo mảng rỗng
23 this.internalArray = EMPTY_ARRAY;
24 } else {
25 // Dung lượng không hợp lệ
26 throw new IllegalArgumentException("Dung lượng không hợp lệ: "+
27 initialCapacity);
28 }
29 }
30
31 /**
32 * Truyền đối tượng bộ sưu tập Collection
33 * */
34 public ArrayList(Collection<? extends E> c) {
35 // Chuyển đổi đối tượng bộ sưu tập thành mảng Object
36 internalArray = c.toArray();
37 if ((currentSize = internalArray.length) != 0) {
38 // c.toArray có thể (không chính xác) không trả về Object[] (xem 6260652)
39 if (internalArray.getClass() != Object[].class)
40 // Sao chép dữ liệu từ bộ sưu tập thông qua phương thức Arrays.copyOf
41 internalArray = Arrays.copyOf(internalArray, currentSize, Object[].class);
42 } else {
43 // Khởi tạo mảng rỗng
44 this.internalArray = EMPTY_ARRAY;
45 }
46 }
Có thể thấy ArrayList có một mảng Object bên trong có tên là internalArray để lưu trữ dữ liệu phần tử của List, quá trình khởi tạo thực chất là quá trình khởi tạo mảng Object, mặc định là mảng rỗng, cũng có thể truyền vào mảng có dung lượng chỉ định, hoặc truyền vào bộ sưu tập, sao chép dữ liệu từ bộ sưu tập vào mảng Object.
1.2, Chèn dữ liệu vào ArrayList
Việc chèn dữ liệu vào List có thể chèn vào cuối, chèn vào vị trí chỉ định, chèn toàn bộ bộ sưu tập, hoặc chèn toàn bộ bộ sưu tập vào vị trí chỉ định. Mã nguồn cho phương thức chèn như sau:
1 /** Dung lượng mặc định */
2 private static final int DEFAULT_CAPACITY = 10;
3
4 /** Số lần sửa đổi */
5 protected transient int modificationCount = 0;
6
7 /** Chèn phần tử vào cuối List */
8 public boolean add(E e) {
9 /** Mở rộng mảng, tăng dung lượng lên 1 */
10 ensureCapacityInternal(currentSize + 1); // Tăng modificationCount!!
11 /** Gán phần tử chèn vào vị trí chỉ định, vị trí là giá trị của currentSize, sau đó tự tăng currentSize
12 * Lưu ý currentSize và kích thước mảng có thể khác nhau
13 * */
14 internalArray[currentSize++] = e;
15 return true;
16 }
17
18 /**
19 * Đảm bảo dung lượng của mảng đủ, nếu không thì mở rộng
20 * */
21 private void ensureCapacityInternal(int minCapacity) {
22 ensureExplicitCapacity(calculateCapacity(internalArray, minCapacity));
23 }
24
25 private void ensureExplicitCapacity(int minCapacity) {
26 // Tăng modificationCount một lần
27 modificationCount++;
28
29 /**
30 * Khi dung lượng cần thiết lớn hơn kích thước mảng, thì mở rộng; nếu không thì không cần mở rộng
31 * */
32 if (minCapacity - internalArray.length > 0)
33 /** Mở rộng mảng */
34 grow(minCapacity);
35 }
36
37 /**
38 * Tính toán dung lượng cần thiết sau khi mở rộng
39 * Tham số là kích thước mảng hiện tại và dung lượng mong muốn sau khi mở rộng
40 * */
41 private static int calculateCapacity(Object[] internalArray, int minCapacity) {
42 if (internalArray == DEFAULT_EMPTY_ARRAY) {
43 /** Khi mảng rỗng, tức là vừa khởi tạo
44 * Đặt dung lượng mảng là giá trị lớn nhất giữa mặc định và dung lượng cần thiết, dung lượng mặc định là 10,
45 * tức là khi dung lượng cần thiết nhỏ hơn 10, sẽ cấp phát 10 dung lượng một lần; ngược lại sẽ cấp phát dung lượng cần thiết
46 * */
47 return Math.max(DEFAULT_CAPACITY, minCapacity);
48 }
49 /** Khi mảng không rỗng, trả về giá trị dung lượng tối thiểu */
50 return minCapacity;
51 }
52
53 /**
54 * Mở rộng mảng
55 * Tham số là dung lượng tối thiểu cần thiết
56 * */
57 private void grow(int minCapacity) {
58 // Kích thước mảng cũ
59 int oldCapacity = internalArray.length;
60 // Kích thước mới sau khi mở rộng là 1.5 lần kích thước cũ
61 int newCapacity = oldCapacity + (oldCapacity >> 1);
62 // Nếu kích thước mảng mới nhỏ hơn dung lượng tối thiểu cần thiết, thì tính theo dung lượng tối thiểu cần thiết
63 if (newCapacity - minCapacity < 0)
64 newCapacity = minCapacity;
65 // Nếu kích thước mảng mới lớn hơn độ dài tối đa của List, thì tính theo độ dài tối đa của List, độ dài tối đa của List là giá trị lớn nhất của Integer trừ 8
66 /**
67 * Độ dài tối đa của ArrayList là 2^31-8, tại sao cần trừ 8, vì một số máy ảo sẽ giữ lại một số thông tin đầu trong mảng, để tránh tràn bộ nhớ
68 * đã giữ lại 8 bit để lưu trữ thông tin đầu
69 * */
70 if (newCapacity - MAX_ARRAY_SIZE > 0)
71 newCapacity = hugeCapacity(minCapacity);
72 // Sử dụng phương thức Arrays.copyOf để tạo mảng mới
73 internalArray = Arrays.copyOf(internalArray, newCapacity);
74 }
Khi gọi phương thức chèn, bước đầu tiên là kiểm tra dung lượng của mảng có đủ hay không, nếu không đủ thì mở rộng mảng, lần đầu dung lượng là 10, các lần mở rộng sau mỗi lần mở rộng 1.5 lần so với dung lượng cũ, hoặc nếu chèn một lần quá nhiều vượt quá 1.5 lần thì sẽ mở rộng theo dung lượng thực tế cần thiết. Độ dài tối đa khi mở rộng là 2^31-8.
Sau khi mở rộng xong, đặt phần tử chèn vào vị trí số lượng phần tử hiện tại của mảng, và tự tăng currentSize.
Xem xét phương thức chèn phần tử vào vị trí chỉ định, sau khi chèn phần tử vào vị trí chỉ định, tất cả các phần tử sau vị trí đó sẽ dịch chuyển một vị trí về sau. Mã nguồn như sau:
1 /**
2 * Chèn phần tử vào vị trí chỉ định
3 * */
4 public void add(int index, E element) {
5 rangeCheckForAdd(index);
6
7 // Đảm bảo dung lượng của list đủ
8 ensureCapacityInternal(currentSize + 1); // Tăng modificationCount!!
9 /**
10 * Sao chép dữ liệu từ vị trí index của mảng internalArray đến vị trí index+1 của mảng internalArray
11 * Hiệu quả là:
12 * 1, Mảng internalArray mở rộng +1
13 * 2, Dữ liệu từ vị trí index trở đi của mảng internalArray đều dịch chuyển một vị trí về sau
14 */
15
16 System.arraycopy(internalArray, index, internalArray, index + 1,
17 currentSize - index);
18 // Lưu phần tử chèn vào vị trí index của mảng
19 internalArray[index] = element;
20 currentSize++;
21 }
22
23 /** Kiểm tra index có nằm trong phạm vi dung lượng của List không */
24 private void rangeCheckForAdd(int index) {
25 // Nếu index lớn hơn currentSize hoặc index<0, thì ném ngoại lệ
26 if (index > currentSize || index < 0)
27 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
28 }
Có thể thấy phương thức chèn phần tử vào vị trí chỉ định và phương thức chèn trực tiếp có một số khác biệt, sau đó sẽ gọi phương thức rangeCheckForAdd để kiểm tra index có hợp lệ không, giá trị của index phải lớn hơn 0 và nhỏ hơn hoặc bằng giá trị currentSize, tức là vị trí của mảng chỉ có thể nằm trong khoảng [0]~[currentSize].
Sau đó gọi phương thức System.arraycopy để thực hiện thao tác sao chép mảng, mảng được mở rộng +1, và dữ liệu sau index đều dịch chuyển một vị trí về sau.
Sau khi phân tích hai phương thức add, hai phương thức chèn hàng loạt addAll về cơ bản có nguyên tắc giống nhau, có thể tự phân tích mã nguồn nếu có hứng thú.
1.3, Lấy dữ liệu từ ArrayList
Vì ArrayList là mảng, nên việc lấy phần tử ở vị trí chỉ định thực chất là lấy dữ liệu ở vị trí chỉ định của mảng, mã nguồn như sau:
1 /** Lấy phần tử ở vị trí chỉ định */
2 public E get(int index) {
3 rangeCheck(index);
4 /** Trả trực tiếp dữ liệu ở vị trí chỉ định của mảng */
5 return internalArray(index);
6 }
7
8 /** Kiểm tra index có hợp lệ không */
9 private void rangeCheck(int index) {
10 if (index >= currentSize)
11 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
12 }
1.4, Xóa dữ liệu từ ArrayList
Việc xóa dữ liệu từ ArrayList thường có hai cách, một là xóa dữ liệu ở vị trí chỉ định, một là xóa dữ liệu có giá trị phần tử chỉ định, cả hai chỉ xóa một dữ liệu, ngay cả khi List có nhiều giá trị trùng lặp, cũng chỉ xóa giá trị đầu tiên phù hợp, mã nguồn như sau:
1 /** Xóa phần tử ở vị trí chỉ định */
2 public E remove(int index) {
3 rangeCheck(index);
4 modificationCount++;
5 // Lấy phần tử cần xóa
6 E oldValue = internalArray(index);
7 /** Số lượng dữ liệu cần di chuyển = currentSize - index - 1;
8 * Tức là số lượng phần tử cần di chuyển, tất cả các phần tử sau index đều cần di chuyển
9 * */
10 int numMoved = currentSize - index - 1;
11 if (numMoved > 0)
12 /** Gọi phương thức System.arraycopy để di chuyển dữ liệu bắt đầu từ index+1 đến vị trí index, tương đương với việc di chuyển tất cả dữ liệu sau index lên một vị trí */
13 System.arraycopy(internalArray, index+1, internalArray, index,
14 numMoved);
15 /** Đặt vị trí cuối cùng của mảng thành null, vì mặc dù dữ liệu sau index đã dịch chuyển lên, nhưng dữ liệu ở vị trí cuối cùng vẫn tồn tại, nên cần đặt thành null để xử lý */
16 internalArray[--currentSize] = null; // clear to let GC do its work
17 return oldValue;
18 }
19
20 /** Xóa phần tử có giá trị chỉ định */
21 public boolean remove(Object o) {
22 /**
23 * Duyệt mảng, xóa dữ liệu đầu tiên có giá trị giống với tham số, ngay cả khi có nhiều giá trị trùng lặp, cũng chỉ xóa đầu tiên
24 * */
25 if (o == null) {
26 for (int index = 0; index < currentSize; index++)
27 if (internalArray[index] == null) {
28 fastRemove(index);
29 return true;
30 }
31 } else {
32 for (int index = 0; index < currentSize; index++)
33 if (o.equals(internalArray[index])) {
34 fastRemove(index);
35 return true;
36 }
37 }
38 return false;
39 }
1.5, An toàn luồng của ArrayList
Như chúng ta biết, ArrayList không an toàn về mặt luồng, vì ArrayList không thực hiện bất kỳ thao tác nào liên quan đến an toàn luồng. Trong tình huống luồng đơn sẽ không có vấn đề gì, nhưng trong tình huống đa luồng sẽ dễ xảy ra vấn đề về dữ liệu hỗn loạn, ví dụ phương thức chèn dữ liệu, mã nguồn như sau:
1 public boolean add(E e) {
2 ensureCapacityInternal(currentSize + 1); // Tăng modificationCount!!
3 <strong>internalArray[currentSize++] = e;
</strong>4 return true;
5 }
Trong đó khi chèn dữ liệu sử dụng thao tác internalArray[currentSize++] = e, nhưng thao tác currentSize++ không phải là thao tác nguyên tử, mà được chia thành hai bước: internalArray[currentSize]=e và currentSize++, vì vậy khi luồng A gọi thực hiện internalArray[currentSize]=e, nếu lúc này luồng B cũng gọi phương thức add, và cũng thực hiện internalArray[currentSize], sẽ dẫn đến luồng B ghi đè dữ liệu do luồng A chèn, sau đó luồng AB lần lượt thực hiện thao tác currentSize++, kết quả dẫn đến giá trị currentSize là 2, nhưng trong mảng chỉ có một dữ liệu, lúc này đã xảy ra vấn đề không an toàn về mặt luồng.
Lại ví dụ như khi mở rộng, giả sử hai luồng đồng thời chèn dữ liệu đều xác định cần thực hiện thao tác mở rộng, lúc này sẽ dẫn đến hai luồng đồng thời mở rộng dữ liệu, từ đó mảng được mở rộng thành 1.5 * 2 = 3 lần dung lượng, mặc dù không dẫn đến vấn đề rõ ràng, nhưng rõ ràng đây cũng không phải là thao tác an toàn về mặt luồng.
Tương tự như vậy, các thao tác không phải là truy vấn khác cũng tồn tại vấn đề tương tự, vì vậy nếu sử dụng ArrayList trong tình huống luồng đơn thì không có vấn đề gì, nhưng trong tình huống đa luồng cần cân nhắc kỹ lưỡng khi sử dụng ArrayList.
1.5, Tổng kết ArrayList:
1, Cấu trúc dữ liệu dưới đáy của ArrayList là mảng, khởi tạo mặc định kích thước là 0, khi dung lượng không đủ sẽ mở rộng, lần đầu là 10, vượt quá thì mở rộng theo dung lượng 1.5 lần, khi chèn hàng loạt nếu vượt quá 1.5 lần thì mở rộng theo dung lượng thực tế cần thiết
2, Việc truy vấn dữ liệu của ArrayList chỉ cần trả dữ liệu ở vị trí chỉ định của mảng nội bộ
3, Việc xóa dữ liệu của ArrayList cần di chuyển dữ liệu sau vị trí chỉ định của mảng lên trước, sau đó đặt vị trí cuối cùng của mảng thành null để xử lý
4, Khi mở rộng và xóa dữ liệu, ArrayList đều gọi phương thức System.arraycopy để thực hiện sao chép mảng
5, ArrayList không an toàn về mặt luồng, khi mở rộng và chèn dữ liệu đều không an toàn
II. Phân tích nguồn LinkedList
LinkedList là cấu trúc lưu trữ List dựa trên danh sách liên kết, cách sử dụng và ArrayList như một đũa, chỉ khác là cấu trúc dưới đáy hoàn toàn khác với ArrayList, phân tích mã nguồn như sau:
2.1, Khởi tạo LinkedList
LinkedList có hai hàm khởi tạo, một là hàm khởi tạo không tham số, một là hàm khởi tạo tham số là Collection, hàm khởi tạo có tham số bên trong cũng gọi hàm khởi tạo không tham số rồi gọi phương thức addAll() để lưu trữ phần tử của bộ sưu tập vào List, sau đó sẽ xem dần khi chèn dữ liệu.
1 /** Nút đầu của danh sách liên kết */
2 transient Node<E> headNode;
3 /** Nút cuối của danh sách liên kết */
4 transient Node<E> tailNode;
5 /** Lớp nội bộ của LinkedList
6 * Node: nút của danh sách liên kết
7 * */
8 private static class Node<E> {
9 E data; // Dữ liệu thực của nút
10 Node<E> next; // Tham chiếu đến nút tiếp theo
11 Node<E> prev; // Tham chiếu đến nút trước đó
12 Node(Node<E> prev, E element, Node<E> next) {
13 this.data = element;
14 this.next = next;
15 this.prev = prev;
16 }
17 }
18
19 /** Khởi tạo không tham số */
20 public LinkedList() {
21 }
22 /** Hàm khởi tạo tham số là Collection */
23 public LinkedList(Collection<? extends E> c) {
24 this();
25 addAll(c);
26 }
Có thể thấy LinkedList về mặt khởi tạo đã khác với ArrayList, quá trình khởi tạo của LinkedList không có bất kỳ thao tác nào, trong khi quá trình khởi tạo của ArrayList cần khởi tạo mảng Object bên trong.
2.2, Chèn dữ liệu vào LinkedList
Mã nguồn thực hiện của add(E e) như sau
/** Chèn phần tử */
public boolean add(E e) {
linkLast(e); // Gọi phương thức nội bộ linkLast(e)
return true;
}
/** Chèn phần tử từ cuối danh sách liên kết */
void linkLast(E e) {
// 1. Lấy nút cuối cùng của danh sách liên kết
final Node<E> l = tailNode;
// 2. Tạo nút mới, tham chiếu nút trước là nút cuối hiện tại; dữ liệu là dữ liệu chèn; tham chiếu nút sau là null
final Node<E> newNode = new Node<>(l, e, null);
// 3. Gán nút hiện tại cho tham chiếu nút cuối
tailNode = newNode;
// 4. Nếu nút cuối hiện tại là null, nghĩa là danh sách liên kết hiện tại rỗng, thì nút đầu và nút cuối đều là nút mới chèn hiện tại
if (l == null)
headNode = newNode;
// 5. Nếu nút cuối hiện tại không phải là null, thì gán nút hiện tại cho tham chiếu next của nút cuối hiện tại
else
l.next = newNode;
// 6. Tự tăng độ dài danh sách liên kết
currentSize++;
modificationCount++;
}
Từ mã nguồn có thể thấy, định dạng lưu trữ dữ liệu của LinkedList là một danh sách liên kết hai chiều, nút là đối tượng Node của lớp nội bộ Node, đối tượng Node lưu trữ dữ liệu được lưu, tham chiếu nút trước và sau, khi chèn nút thực chất là tạo một đối tượng Node mới, thêm vào cuối danh sách liên kết, tham chiếu next của nút cuối hiện tại trỏ đến nút mới.
Từ việc chèn dữ liệu cũng có thể so sánh với ArrayList, khi chèn dữ liệu vào ArrayList liên quan đến việc mở rộng, sao chép mảng, v.v., trong khi khi chèn dữ liệu vào LinkedList chỉ cần tạo một nút mới, và tham chiếu next của nút cuối hiện tại trỏ đến nút mới, quá trình không ảnh hưởng đến các nút khác trong List. Vì vậy hiệu suất cao hơn nhiều so với ArrayList.
Ngoài việc chèn phần tử vào cuối danh sách liên kết, còn có thể chèn nút mới vào vị trí chỉ định, chỉ là quy trình sẽ phức tạp hơn một chút, vì cần duyệt danh sách liên kết mới tìm được vị trí cần chèn.
Mã nguồn thực hiện của add(int index, E e) như sau:
1 /** Chèn phần tử vào vị trí chỉ định */
2 public void add(int index, E element) {
3 // 1. Kiểm tra giá trị index có hợp lệ không
4 checkPositionIndex(index);
5 // 2. Nếu index == currentSize, nghĩa là chèn phần tử từ cuối danh sách liên kết, logic thực hiện tương đương với phương thức add(E e)
6 if (index == currentSize)
7 linkLast(element);
8 // 3. Nếu index < currentSize, nghĩa là cần chèn từ giữa danh sách liên kết, trực tiếp gọi phương thức linkBefore
9 else
10 linkBefore(element, node(index));
11 }
12
13 /** Lấy đối tượng Node ở vị trí chỉ định */
14 Node<E> node(int index) {
15 /**
16 * Khi index < currentSize/2 thì duyệt từ nút đầu để tìm nút index
17 * */
18 if (index < (currentSize >> 1)) {
19 Node<E> x = headNode;
20 for (int i = 0; i < index; i++)
21 x = x.next;
22 return x;
23 }
24 /**
25 * Khi index >= currentSize/2 thì duyệt từ nút cuối để tìm nút index
26 * */
27 else {
28 Node<E> x = tailNode;
29 for (int i = currentSize - 1; i > index; i--)
30 x = x.prev;
31 return x;
32 }
33 }
34
35
36 /** Chèn nút trước nút chỉ định */
37 void linkBefore(E e, Node<E> succ) {
38 // 1. Lấy nút trước của nút index
39 final Node<E> pred = succ.prev;
40 // 2. Tạo nút mới
41 final Node<E> newNode = new Node<>(pred, e, succ);
42 // 3. Tham chiếu prev của nút index hiện tại trỏ đến nút mới
43 succ.prev = newNode;
44 // 4. Khi nút index là nút đầu, nút mới là nút đầu
45 if (pred == null)
46 headNode = newNode;
47 // 5. Khi nút index không phải là nút đầu, tham chiếu next của nút trước hiện tại trỏ đến nút mới
48 else
49 pred.next = newNode;
50 currentSize++;
51 modificationCount++;
52 }
53
54 /** Kiểm tra index có hợp lệ không, giá trị index cần lớn hơn 0 và nhỏ hơn hoặc bằng currentSize */
55 private void checkPositionIndex(int index) {
56 if (!isPositionIndex(index))
57 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
58 }
59
60 private boolean isPositionIndex(int index) {
61 return index >= 0 && index <= currentSize;
62 }
Có thể thấy chủ yếu chia thành một vài bước:
1, Kiểm tra index có hợp lệ không
2, Nếu giá trị index là giá trị currentSize, nghĩa là trực tiếp chèn từ cuối danh sách liên kết
3, Nếu giá trị index không phải là giá trị currentSize, nghĩa là cần chèn từ giữa danh sách liên kết, các bước chèn từ giữa danh sách liên kết như sau:
3.1, Tìm đến đối tượng Node ở vị trí index hiện tại, bằng cách tìm kiếm nhị phân, nếu ở nửa trên của danh sách liên kết thì duyệt từ nút đầu; nếu ở nửa dưới của danh sách liên kết thì duyệt từ nút cuối
3.2, Tạo nút mới, tham chiếu prev của nút mới trỏ đến nút trước; tham chiếu next trỏ đến nút sau, và sửa đổi tham chiếu next và prev của các nút trước và sau.
Có thể thấy mặc dù việc chèn phần tử vào cuối danh sách liên kết khá đơn giản, nhưng một khi chèn từ giữa danh sách liên kết, cần duyệt một nửa danh sách liên kết mới tìm được vị trí cần chèn, sau đó sửa đổi tham chiếu của các nút trước và sau, mặc dù hiệu suất thao tác chèn vẫn còn khá cao, nhưng quá trình tìm vị trí vẫn còn khá phức tạp. Vì vậy LinkedList không phù hợp với thao tác chèn dữ liệu từ giữa.
2.3, Xóa dữ liệu từ LinkedList
1 /** Xóa phần tử ở vị trí chỉ định */
2 public E remove(int index) {
3 // Kiểm tra giá trị index có hợp lệ không
4 checkElementIndex(index);
5 // Gọi phương thức unlink để xóa Node ở vị trí chỉ định
6 return unlink(node(index));
7 }
8
9 /** Xóa phần tử có giá trị chỉ định */
10 public boolean remove(Object o) {
11 // 1. Khi tham số là null, thì duyệt từ nút đầu, xóa nút đầu tiên có giá trị null
12 if (o == null) {
13 for (Node<E> x = headNode; x != null; x = x.next) {
14 if (x.data == null) {
15 unlink(x);
16 return true;
17 }
18 }
19 }
20 // 2. Khi tham số không phải là null, thì duyệt từ nút đầu, xóa nút đầu tiên có giá trị của phương thức equals là true
21 else {
22 for (Node<E> x = headNode; x != null; x = x.next) {
23 if (o.equals(x.data)) {
24 unlink(x);
25 return true;
26 }
27 }
28 }
29 return false;
30 }
31
32 /**
33 * Loại bỏ đối tượng Node chỉ định khỏi danh sách liên kết
34 * */
35 E unlink(Node<E> x) {
36 /** 1. Lấy giá trị, nút trước, nút sau của đối tượng Node */
37 final E element = x.data;
38 final Node<E> next = x.next;
39 final Node<E> prev = x.prev;
40
41 /** 2. Tham chiếu next của nút trước trỏ đến nút sau
42 * Tham chiếu prev của nút sau trỏ đến nút trước
43 * Đặt toàn bộ tham chiếu item, next, prev của nút hiện tại thành null, để GC thu hồi
44 * */
45
46 if (prev == null) {
47 headNode = next;
48 } else {
49 prev.next = next;
50 x.prev = null;
51 }
52
53 if (next == null) {
54 tailNode = prev;
55 } else {
56 next.prev = prev;
57 x.next = null;
58 }
59 x.data = null;
60 currentSize--;
61 modificationCount++;
62 return element;
63 }
Từ mã nguồn có thể thấy, dù là xóa nút ở vị trí chỉ định hay xóa nút có giá trị chỉ định, thực chất đều là duyệt tìm đối tượng Node này, sau đó gọi phương thức unlink để xóa nút này, quá trình xóa khá đơn giản, thực chất là để các nút trước và sau chỉ vào nhau, tham chiếu next của nút trước trỏ đến nút sau, tham chiếu prev của nút sau trỏ đến nút trước, sau đó đặt toàn bộ thuộc tính của nút hiện tại thành null để chờ được thu hồi.
2.4, An toàn luồng của LinkedList
Tương tự như ArrayList, LinkedList cũng không an toàn về mặt luồng, trong quá trình chèn và x đều là không an toàn về mặt luồng, trong tình huống đa luồng sẽ xảy ra vấn đề về dữ liệu không nhất quán, ví dụ khi chèn dữ liệu vào cuối danh sách liên kết
1 /** Chèn phần tử từ cuối danh sách liên kết */
2 void linkLast(E e) {
3 // 1. Lấy nút cuối cùng của danh sách liên kết
4 final Node<E> l = tailNode;
5 // 2. Tạo nút mới, tham chiếu nút trước là nút cuối hiện tại; dữ liệu là dữ liệu chèn; tham chiếu nút sau là null
6 final Node<E> newNode = new Node<>(l, e, null);
7 // 3. Gán nút hiện tại cho tham chiếu nút cuối
8 tailNode = newNode;
9 // 4. Nếu nút cuối hiện tại là null, nghĩa là danh sách liên kết hiện tại rỗng, thì nút đầu và nút cuối đều là nút mới chèn hiện tại
10 if (l == null)
11 headNode = newNode;
12 // 5. Nếu nút cuối hiện tại không phải là null, thì gán nút hiện tại cho tham chiếu next của nút cuối hiện tại
13 else
14 l.next = newNode;
15 // 6. Tự tăng độ dài danh sách liên kết
16 currentSize++;
17 modificationCount++;
18 }
Khi hai luồng đều thực hiện đến bước thứ tư, phát hiện nút đầu hiện tại là null, thì đều đặt thành nút đầu của mình, như vậy luồng thứ hai sẽ thay thế tham chiếu first do luồng thứ nhất đặt.
2.5, Tổng kết LinkedList
1, LinkedList khi khởi tạo và chèn dữ liệu đều không cần thao tác mở rộng, có thể nói độ dài của LinkedList là vô hạn, nhưng do currentSize là kiểu int, nên độ dài thực tế tối đa vẫn là giá trị lớn nhất của int
2, Quá trình chèn của LinkedList thực chất là tạo nút mới, sau đó sửa đổi tham chiếu prev hoặc next của các nút trước và sau
3, LinkedList khi chèn vào cuối có hiệu suất cao nhất, nhưng nếu liên quan đến việc truy vấn hoặc chèn vào giữa danh sách liên kết, thì cần duyệt danh sách liên kết, ảnh hưởng đến hiệu suất
4, Khi duyệt danh sách liên kết, LinkedList đã được tối ưu hóa, thông qua chia đôi danh sách liên kết, chỉ duyệt nửa đầu của danh sách liên kết từ nút đầu hoặc nửa sau của danh sách liên kết từ nút cuối
5, LinkedList cũng không an toàn về mặt luồng, trong tình huống đa luồng chèn/xóa dữ liệu sẽ xảy ra hiện tượng dữ liệu bị ghi đè hoặc không nhất quán.
III. Thêm
3.1, Sự khác biệt giữa ArrayList và LinkedList?
1, Cấu trúc dữ liệu dưới đáy của ArrayList là mảng lưu trữ dữ liệu; cấu trúc dưới đáy của LinkedList là danh sách liên kết hai chiều
2, Việc chèn/xóa dữ liệu của ArrayList cần thực hiện thao tác khởi tạo và mở rộng mảng, vì vậy sẽ chiếm nhiều bộ nhớ hơn; LinkedList không cần dung lượng, chỉ lưu trữ dữ liệu hiệu quả, vì vậy không chiếm thêm bộ nhớ
3, Dữ liệu lưu trữ của ArrayList trong bộ nhớ là liên tục, khi truy cập liên tục và truy vấn có hiệu suất cao; dữ liệu lưu trữ của LinkedList trong bộ nhớ là phân tán, hiệu suất truy vấn thấp, thường cần bắt đầu duyệt từ một đầu
4, Khi mở rộng, ArrayList cần thực hiện thao tác sao chép mảng, tăng thêm tiêu hiệu năng; LinkedList không cần mở rộng, thao tác chèn/xóa nút chỉ cần sửa đổi tham chiếu của các nút liền kề, hiệu suất chèn/xóa dữ liệu cao
5, ArrayList phù hợp với kịch bản truy vấn nhiều, chèn/xóa ít; LinkedList phù hợp với kịch bản truy vấn ít, chèn/xóa thường xuyên
3.2, Hiệu suất chèn dữ liệu của ArrayList chắc chắn thấp hơn LinkedList không? Hiệu suất truy vấn của LinkedList chắc chắn thấp hơn ArrayList không?
Chắc chắn không
Hiệu suất chèn dữ liệu của ArrayList thực chất chỉ cần gán dữ liệu vào vị trí chỉ định của mảng, nếu mảng đã được mở rộng sẵn, thao tác chèn dữ liệu chỉ có một bước gán mảng, hiệu suất cũng rất cao, chỉ khi liên quan đến việc mở rộng và xóa dữ liệu mới liên quan đến việc sao chép mảng mới dẫn đến hiệu suất kém; và LinkedList nếu chèn dữ liệu vào vị trí chỉ định, còn cần duyệt trước để tìm đến nút tương ứng với index, nếu danh sách liên kết đủ dài, hiệu suất chèn cũng tương đối thấp;
Hiệu suất truy vấn thấp của LinkedList chủ yếu do cần duyệt, nhưng nếu mỗi lần đều truy vấn dữ liệu ở hai đầu, thì có thể truy vấn một lần là tìm được dữ liệu, tránh quá trình duyệt, hiệu suất truy vấn cũng tương đối cao.
3.3, Sự khác biệt giữa phương thức System.arraycopy() và Arrays.copyOf()?
Việc sao chép mảng bên trong của ArrayList đều thông qua phương thức System.arraycopy() hoặc Arrays.copyOf() để thực hiện, nguyên lý thực hiện cơ bản của hai phương thức này giống nhau, vì phương thức Arrays.copyOf() thực chất bên dưới cũng gọi phương thức System.arraycopy() để thực hiện
Phương thức System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length) có tác dụng sao chép các phần tử có độ dài length từ vị trí srcPos bắt đầu của mảng nguồn src đến vị trí destPos của mảng đích dest, đây là một phương thức phương thức gốc.
Còn phương thức Arrays.copyOf([] original, int newLength) có tác dụng tương đương với việc tạo một mảng mới, độ dài mảng là newLength, nếu độ dài lớn hơn original thì tương đương với việc mở rộng, nếu nhỏ hơn original thì tương đương với việc cắt bớt;
Bên dưới chính là gọi phương thức System.arraycopy(original, 0, new Array(), 0, (độ dài của original và newLength lấy giá trị nhỏ nhất))
3.4, Làm thế nào để thực hiện ArrayList và LinkedList an toàn về mặt luồng?
ArrayList và LinkedList đều không an toàn về mặt luồng, nếu muốn sử dụng trong tình huống đa luồng, cần sử dụng một số cách an toàn về mặt luồng, chủ yếu có các cách sau:
1, Sử dụng các lớp công cụ bộ sưu tập an toàn về mặt luồng, như Vector, CopyOnWriteArrayList, ConcurrentLinkedQueue, v.v.
Vector nguyên lý thực hiện và ArrayList gần như giống hệt nhau, chỉ là Vector tất cả các phương thức đối bên ngoài đều thông qua Syncrhonized để thực hiện hiệu quả đồng bộ
CopyOnWriteArrayList và ConcurrentLinkedQueue đều là lớp con List an toàn về mặt luồng trong JUC được thực hiện thông qua CAS+volatile
2, Sử dụng phương thức Collections.synchroniizedList(List list) để chuyển đổi đối tượng ArrayList hoặc LinkedList thành bộ sưu tập an toàn về mặt luồng, nhưng nguyên lý thực hiện của Collections là có một lớp nội bộ tĩnh thực hiện List, phương thức thực hiện List chính là gọi phương thức của lớp con List được truyền vào tham số, trước khi gọi thêm từ khóa Synchronized để quản lý đồng bộ, về bản chất vẫn là đồng bộ thông qua Synchronized
3, Đồng bộ gọi phương thức, ví dụ như trước khi gọi phương thức của ArrayList và LinkedList, người gọi tự xử lý đồng bộ, để tránh đa luồng thao tác ArrayList và LinkedList. Ví dụ như thông qua ReentrantLock, Synchronzied, v.v. để đồng bộ gọi phương thức của List