NỘI DUNG BÀI VIẾT
1. Linked Lists
Một danh sách liên kết được thực thi sử dụng cấu trúc liên kết.
Vì MyArrayList được thực thi bằng cách sử dụng một mảng, nên phương thức get(int index) và set(int index, E e) để truy cập và sửa đổi một phần tử thông qua một chỉ số và phương thức add(E e) để thêm một phần tử vào cuối danh sách là hiệu quả. Tuy nhiên, các phương thức add(int index, E e) và remove(int index) không hiệu quả, vì chúng đòi hỏi phải di chuyển một số lượng lớn các phần tử. Bạn có thể sử dụng cấu trúc liên kết để thực hiện một danh sách để nâng cao hiệu quả để thêm và xóa một phần tử ở đầu danh sách.
2. Node
Trong một danh sách liên kết, mỗi phần tử được chứa trong một đối tượng, gọi là node. Khi một phần tử mới được thêm vào danh sách, một node được tạo để chứa nó. Mỗi node được liên kết với node kế tiếp, như thể hiện trong hình 24.7.
Một node có thể được tạo từ định nghĩa một lớp như sau:
class Node<E> {
E element; Node<E> next;
public Node(E e) {
element = e;
}
}
Hình 24.7 Danh sách liên kết bao gồm bất kỳ số node nào được nối liền với nhau
Sử dụng biến head để tham chiếu tới node đầu tiên trong danh sách, và biến tail tham chiếu đến node cuối cùng. Nếu danh sách trống, head và tail là null.
Dưới đây là một ví dụ về tạo danh sách liên kết để lưu giữ ba node. Mỗi node lưu trữ một phần tử chuỗi.
Bước 1: Khai báo head và tail.
Node<String> head = null; Danh sách bây giờ là rỗng Node<String> tail = null;
head và tail đều là null. Danh sách là rỗng
Bước 2: Tạo node đầu tiên và nối nó vào danh sách, như trong hình 24.8. Sau khi node đầu tiên được chèn vào sanh sách, head và tail đều trỏ tới node này.
Hình 24.8 Nối node đầu tiền vào danh sách. Cả head và tail đều trỏ tới node này.
Bước 3: Tạo node thứ hai và nối nó vào danh sách, như thể hiện trong hình 24.9a. Để nối node thứ hai vào danh sách, liên kết node đầu tiên với node mới. Node mới bây giờ là node đuôi, vì vậy bạn nên di chuyển tail để trỏ đến node mới này, như thể hiện trong hình 24.9b.
Hình 24.9 Nối node thứ hai vào danh sách. Tail bây giờ trỏ tới node mới
Bước 4: Tạo node thứ ba và nối nó vào danh sách, như trong Hình 24.10a. Để nối node mới vào danh sách, liên kết node cuối cùng trong danh sách với node mới. Node mới bây giờ là node đuôi, vì vậy bạn nên di chuyển tail để trỏ đến node mới này, như thể hiện trong hình 24.10b.
Hình 24.10 Nối node thứ ba vào danh sách
Mỗi node chứa phần tử (element) và một trường dữ liệu được đặt tên là next để trỏ đến phần tử tiếp theo. Nếu nút là cuối cùng trong danh sách, trường dữ liệu next chứa giá trị null. Bạn có thể sử dụng thuộc tính này để phát hiện nút cuối. Ví dụ, bạn có thể viết các vòng lặp sau đây để duyệt toàn bộ các nút trong danh sách.
Node current = head;
while(current != null){
System.out.println(current.element);
current = current.next();
}
Biến current trỏ đến nút đầu tiên trong danh sách (dòng 1). Trong vòng lặp, element của nút hiện tại được lấy ra (dòng 3), và sau đó current trỏ tới node tiếp theo (dòng 4). Vòng lặp tiếp tục cho đến khi nút hiện tại là null.
3. Lớp MyLinkedList
Lớp MyLinkedList sử dụng cấu trúc liên kết để thực thi một danh sách động. Nó được kế thừa từ lớp MyAbstractList. Ngoài ra, nó cung cấp các phương thức addFirst, addLast, removeFirst, removeLast, getFirst, và getLast, như thể hiện trong hình 24.11.
Hình 24.11: MyLinkedList thực thi một danh sách sử dụng danh sách liên kết của các node.
4. Thực thi MyLinkedList
4.1 Thực thi addFirst(e)
Phương thức addFirst(e) tạo node mới để chứa phần tử e. Node mới trở thành node đầu tiên trong danh sách. Phương thức này có thể được thực thi như sau:
public void addFirst(E e) {
Node newNode = new Node<>(e); // Create a new node
newNode.next = head; // link the new node with the head
head = newNode; // head points to the new node
size++; // Increase list size
if (tail == null) // The new node is the only node in list
tail = head;
}
Phương thức addFirst(e) tạo một node mới để lưu element (dòng 2) và chèn node vào đầu danh sách (dòng 3) như thể hiện trong hình 24.12a. Sau khi chèn, head trỏ đến element của node mới (dòng 4) như thể hiện trong hình 24.12b.
Hình 24.12 Một phẩn tử mới được thêm vào đầu danh sách
Nếu danh sách rỗng (dòng 7), cả head và tail sẽ trỏ đến node mới (dòng 8). Sau khi node được tạo, kích thước (size) sẽ tăng lên 1 (dòng 5)
4.2 Thực thi addLast(e)
Phương thức addLast(e) tạo một node chứa element và nối node đó vào cuối danh sách. Phương thức này có thể được thực thi như sau:
public void addLast(E e) {
Node newNode = new Node<>(e); // Create a new node for e
if (tail == null) {
head = tail = newNode; // The only node in list
}
else {
tail.next = newNode; // Link the new node with the last node
tail = tail.next; // tail now points to the last node
}
size++; // Increase size
}
Phương thức addLast(e) tạo một node mới để lưu element (dòng 2) và nối nó vào cuối danh sách. Xem xét 2 trường hợp sau:
- Nếu danh sách rỗng (dòng 4), cả head và tail sẽ trỏ tới node mới (dòng 5)
- Nếu không, liên kết với node cuối cùng trong danh sách (dòng 8), tail bây giờ phải trỏ tới node mới (dòng 9). Hình 24.13a và hình 24.13b chỉ ra node mới cho element e trước và sau khi chèn.
Trong bất kỳ trường hợp nào, sau khi nút được tạo, kích thước (size) sẽ được tăng lên 1 (dòng 12).
Hình 24.13: element mới được thêm vào cuối của dánh sách.
4.3 Thực thi add(index, e)
Phương thức add(index, e) chèn element vào danh sách ở một vị trí xác định. Phương thức có thể được cài đặt như sau:
public void add(int index, E e) {
if (index == 0) addFirst(e); // Insert first
else if (index >= size) addLast(e); // Insert last
else { // Insert in the middle
Node current = head;
for (int i = 1; i < index; i++)
current = current.next;
Node temp = current.next;
current.next = new Node(e);
(current.next).next = temp;
size++;
}
}
Có 3 trường hợp khi chèn một element vào danh sách:
- Nếu index là 0, gọi addFirst(e) (dòng 2) để chèn element vào đầu danh sách
- Nếu index lớn hơn hoặc bằng size, gọi addLast(e) (dòng 3) để chèn element vào cuối danh sách
- Còn lại, tạo node mới để lưu element mới và xác định nới để chèn nó. Như hình 24.14a, node mới được chèn vào giữa node current và temp. Phương thức thực hiện gán node mới vào current.next và gán temp vào next của node mới, như thể hiện trong hình 24.14b. Kích thước bây giờ tăng lên 1 (dòng 11)
Hình 24.14: element mới được chèn vào giữa của danh sách.
4.4 Thực thi removeFirst()
Phương thức removeFirst() method xoá phần tử đầu tiên khỏi dánh sách. Phương thức được thực thi như sau:
public E removeFirst() {
if (size == 0) return null; // Nothing to delete
else {
Node temp = head; // Keep the first node temporarily
head = head.next; // Move head to point to next node
size--; // Reduce size by 1
if (head == null) tail = null; // List becomes empty
return temp.element; // Return the deleted element
}
}
Xem xét 2 trường hợp:
- Nếu danh sách rỗng, không có phần tử nào bị xoá, do đó trả về null (dòng 2)
- Ngoài ra, xoá phần tử khỏi dánh sách bằng cách trỏ head tới node thứ hai. Hình 24.15a và 24.15b hiển thị dánh sách liên kết trước và sau khi xoá. Kích thước sẽ giảm 1 sau kho xoá (dòng 6). Nếu dánh ách trở nên rỗng sau khi gỡ bỏ phần tử, tail phải được đặt thành null (dòng 7)
Hình 24.15 Node đầu tiền bị xoá khỏi danh sách
4.5 Thực thi removeLast()
Phương thức removeLast() m xoá phần tử cuối cùng khỏi dánh sách. Phương thức có thể được cài đặt như sau:
public E removeLast() {
if (size == 0) return null; // Nothing to remove
else if (size == 1) { // Only one element in the list
Node temp = head;
head = tail = null; // list becomes empty
size = 0;
return temp.element;
} else {
Node current = head;
for (int i = 0; i < size - 2; i++)
current = current.next;
Node temp = tail;
tail = current;
tail.next = null;
size--;
return temp.element;
}
}
Xem xét 3 trường hợp:
- Nếu danh sách rỗng, trả về null (dòng 2)
- Nếu dánh sách chỉ chứa 1 node, node này bị xoá, head và tail cùng trỏ tới null (dòng 5). Kích thước lúc này bằng 0 (dòng 6), và trả về giá trị element của phần tử bị xoá (dòng 7)
- Ngoài ra, node cuối cùng bị xoá (dòng 17) và tail được xác định lại để trỏ tới node thứ 2. Hình 24.16a và hình 24.16b hiển thị node cuối trước và sau khi nó bị xoá. Kích thước giảm đi 1 khi khi phần tử bị xoá (dòng 18( và trả về giá trị element của phần tử bị xoá (dòng 19)
Hình 24.16 Node cuối bị xoá khỏi danh sách.
4.6 Thực thi remove(index)
Phương thức remove(index) tìm một node ở vị trí xác định và xoá nó. Phương thức được cài đặt như sau:
public E remove(int index) {
if (index < 0 || index >= size) return null; // Out of range
else if (index == 0) return removeFirst(); // Remove first
else if (index == size - 1) return removeLast(); // Remove last
else {
Node previous = head;
for (int i = 1; i < index; i++) {
previous = previous.next;
}
Node current = previous.next;
previous.next = current.next;
size--;
return current.element;
}
}
Xem xét 4 trường hợp:
- Nếu index vượt quá phạm vị của danh sách (ví dụ index < 0 || index >= size), trả về null (dòng 2)
- Nếu index là 0, gọi removeFirst() để xoá node đầu tiên (dòng 3)
- Nếu index là size – 1, gọi removeLast() để xoá node cuối cùng (dòng 4)
- Ngoài ra, xác định vị trí node tại index. Đặt current xác định node này và previous xác định node trước nó, như thể hiện trong hình 24.17a. Gán current.next cho previous.next để loại bỏ node hiện tại, như thể hiện trong hình 24.17b.
Hình 24.17 Một node bị xoá khỏi dánh sách.
Listing 24.6 cho phép thực thi MyLinkedList. Phương thức iterator() được định nghĩa trong interface java.lang.Iterable được thực thi để trả về một thể hiện trên java.util.Iterator (dòng 126-128). Lớp LinkedListIterator thực thi Iterator với các phương thức cụ thể cho hasNext, next, và remove (các dòng 134-149). Việc thực thi này sử dụng current để trỏ đến vị trí hiện tại của phần tử đang được duyệt qua (dòng 132). Ban đầu, current trỏ tới đầu danh sách.
LISTING 24.6 MyLinkedList.java
5. So sánh MyArrayList và MyLinkedList
Cả MyArrayList và MyLinkedList đều có thể được sử dụng để lưu danh sách. MyArrayList được thực thi bằng cách sử dụng một mảng và MyLinkedList được thực thi bằng cách sử dụng một danh sách liên kết. Tổng thời gian thực thi của MyArrayList nhỏ hơn so với MyLinkedList. Tuy nhiên, MyLinkedList hiệu quả hơn nếu bạn cần chèn các phần tử vào và xóa các phần tử từ đầu danh sách. Bảng 24.1 tóm tắt độ phức tạp của các phương thức trong MyArrayList và MyLinkedList. Lưu ý rằng MyArrayList là giống như java.util.ArrayList và MyLinkedList cũng giống như java.util.LinkedList.
Bảng 24.1 Độ phức tạp thời gian thực hiện các phương thức trong MyArrayList và MyLinkedList
