1. LinkedList
Trong quá trình triển khai lớp LinkedList trong Java, có một lớp Node đại diện cho một nút trong danh sách liên kết đôi. Trong lớp Node nó đồng thới có thêm biến giữ giá trị và hai tham chiếu đến Node tiếp theo và trước nó.
Và để quản lý được các phần tử, LinkedList cung cấp 2 con trỏ rất quan trọng là Node first, và Node last. Với Node first sẽ trỏ đến phần tử đâu tiên và Node last sẽ trỏ đến phần tử cuối cùng của danh sách.
Cấu trúc lớp Node
Mô hình LinkedList triển khai các node
Một số điểm nổi bật của LinkedList:
- Có thể chứa các phần tử trùng lặp
- Duy trì thứ tự của phần tử được thêm vào.
- Không đồng bộ (non-synchronized).
- Thao tác thêm/ xóa (add/ remove) phần tử nhanh vì không cần phải dịch chuyển nếu bất kỳ phần tử nào thêm/ xoá khỏi danh sách.
- LinkedList có thể được sử dụng như danh sách (list), stack (ngăn xếp) hoặc queue (hàng đợi).
- Các phần tử trong LinkedList có thể nằm cách ly nhau (không liên tục) trong bộ nhớ. Nó là một liên kết có tính hai chiều giữa các phần tử. Mỗi phần tử trong danh sách cầm giữ một tham chiếu đến đối phần tử đằng trước nó và tham chiếu đến phần tử ngay sau nó.
Algorithms
Thêm phần tử
Để thêm 1 phần tử bào LinkedList, chúng ta thường sử dụng phương thức add() hoặc addLast(), khi đó phương thức linkedLast() sẽ được gọi. Trong phương thức này, 1 lớp Node mới sẽ được tạo:
new Node<>(null, value, null);Ở ví dụ này ta giả sử LinkedList chưa có phần tử nào, nên Node next và Node prev của Node mới sẽ là null.
Trường hợp nếu LinkedList đang chứa phần tử thì Node next của phần tử trước nó sẽ được link tới Node vừa tạo. Cuối cùng LinkedList sẽ xác định lại phần tử cuối cùng bằng cách gán Node last bằng Node vừa mới tạo. Cũng tương tự cho trường hợp phương thức linkFirst() được gọi nhưng thay vì link Node next, Node prev của phần tử đứng phía sẽ được link tới nó. Và LinkedList sẽ xác định lại Node first = Node vừa mới tạo.
Chèn phần tử
Giống như bước ở trên, 1 lớp Node sẽ được tạo, với contructor là 2 Node trước vào sau nó, cũng như giá trị được thêm vào List. Sau đó cập nhật lại 2 Node trước và sau nó 2 Node tương ứng prev và next
Xóa phần tử
Để xóa 1 phần tử, chúng ta cần gọi phương thức remove(), removeFirst() hay removeLast(). Khi một trong các phương thức này được gọi với tham số là chỉ mục (index). LinkedList sẽ tính toán lại phần tử trước và sau của phần tử cần xóa và cập nhật lại các Node next và prev giữa chúng. Khi đó Node cần xóa sẽ trở thành Node "mồi côi", và nó sẽ được GarbageCollection tự động xóa đi.
Kết luận
Rõ ràng ta có thể thấy, các hoạt động thêm, xóa các phần tử trên LinkedList không tốn quá nhiều hiệu năng khi so sánh với ArrayList/Vector (do không phải sắp xếp/tạo lại mảng nội bộ). Tuy nhiên do LinkedList chỉ có 2 con trỏ để quản lý danh sách nên việc để tìm và truy cập phần tử đó sẽ trở nên khó khăn hơn, khi phải duyệt từ đầu hoặc cuối danh sách. ArrayList là 1 Random Access nên có thể truy cập ngay lập tức phần tử đó thông qua các chỉ mục. Do đó, nếu xét về khía cạnh truy xuất dữ liệu thì ArrayList sẽ cho hiệu năng cao hơn.
2. Stack
Algorithms
| Phương thức | Công dụng |
|---|---|
| Object peek( ) | Trả về phần tử trên cùng của Stack, nhưng không loại bỏ nó ra khỏi Stack. Khi được gọi, phương thức này lấy phần tử cuối cùng của mảng nội bộ thông qua phương thức của Vector elementAt(len - 1) |
| Object pop( ) | Trả về phần tử trên cùng của Stack, loại bỏ nó ra khỏi Stack. Lấy lên phần tử cuối cùng trong mảng thông qua peek() sau đó tiến hành xóa phần tử đó thông qua phương thức removeElementAt(len - 1) của Vector |
| Object push(Object element) | Thêm phần tử vào cuối mảng thông qua phương thức addElement(item); của Vector và đồng thời trả lại phần tử vừa được thêm vào. |
| boolean empty() | Kiểm tra nếu Stack này là trống. Trả về true nếu nó trống và false nếu stack chứa các phần tử. Thường được nên được sử dụng trước khi phương thức peek( ) được gọi để tránh ngoại lệ EmptyStackException |
Kết luận
Có thể thấy lớp Stack triển khai trên Vector nên sẽ gặp một số vấn đề về hiệu suất do phải đồng bộ hóa.
No comments:
Post a Comment