Class LinkedList<E>
Lớp LinkedList trong Java là một triển khai của danh sách liên kết đôi, cung cấp cấu trúc dữ liệu danh sách liên kết mà bạn có thể sử dụng như một danh sách, ngăn xếp (stack), hoặc hàng đợi (queue).
Một số đặc điểm nổi bật của LinkedList
↳ Chứa phần tử trùng lặp: LinkedList cho phép chứa các phần tử trùng lặp và các phần tử null.
↳ Duy trì thứ tự chèn: Các phần tử được chèn vào danh sách sẽ được duy trì theo đúng thứ tự chèn.
↳ Không đồng bộ hóa: LinkedList không đồng bộ hóa các thao tác. Đối với các ứng dụng đa luồng, bạn cần phải đồng bộ hóa bên ngoài nếu danh sách bị sửa đổi bởi nhiều luồng.
↳ Hiệu suất thao tác: Các thao tác thêm hoặc xóa phần tử là nhanh chóng vì không cần phải di chuyển các phần tử khác như trong ArrayList.
↳ Sử dụng như danh sách, ngăn xếp, hoặc hàng đợi: LinkedList có thể được sử dụng như một danh sách (List), ngăn xếp (Stack), hoặc hàng đợi (Queue), nhờ vào việc triển khai cả List và Deque interfaces.
Các loại LinkedList
Các loại LinkedList được phân chia dựa trên cấu trúc và cách các nút (node) trong danh sách liên kết với nhau. Dưới đây là các loại LinkedList phổ biến:
1. LinkedList đơn (Singly Linked List)
↳ Cấu trúc: Mỗi phần tử trong LinkedList đơn được gọi là một nút (node). Mỗi nút (node) chứa hai phần chính:
↳ Data (Giá trị): Chứa giá trị của phần tử.
↳ Next (Con Trỏ): Là con trỏ hoặc liên kết tới nút kế tiếp trong danh sách.
↳ Head: Là nút đầu tiên trong danh sách. Head chứa con trỏ trỏ đến nút tiếp theo trong danh sách. Nếu danh sách rỗng, Head sẽ là null.
↳ Tail: Là nút cuối cùng trong danh sách. Tail chứa con trỏ Next trỏ đến null, chỉ ra rằng đây là phần tử cuối cùng.
Thư viện chuẩn cho LinkedList đơn (Singly LinkedList)
↳ Cấu trúc dữ liệu Node
Cấu trúc dữ liệu Node
// Định nghĩa một lớp generic Node với kiểu dữ liệu T
class Node<T> {
// Biến lưu trữ dữ liệu của node
T data;
// Tham chiếu đến node tiếp theo trong danh sách liên kết
Node<T> next;
// Constructor để khởi tạo một node với dữ liệu được truyền vào
public Node(T data) {
// Gán giá trị truyền vào cho biến data
this.data = data;
// Khởi tạo biến next là null, tức là node này hiện chưa liên kết với node nào khác
this.next = null;
}
}
↳ Triển khai Singly LinkedList
Triển khai Singly LinkedList
// Định nghĩa lớp SinglyLinkedList với kiểu dữ liệu generic T
public class SinglyLinkedList<T> {
// Biến để lưu trữ node đầu tiên của danh sách liên kết
private Node<T> head;
// Constructor khởi tạo danh sách liên kết rỗng
public SinglyLinkedList() {
this.head = null; // Khi tạo mới, danh sách bắt đầu với head là null
}
// Thêm phần tử vào đầu danh sách
public void addFirst(T data) {
// Tạo node mới với dữ liệu được cung cấp
Node<T> newNode = new Node<>(data);
// Gán next của node mới là head hiện tại
newNode.next = head;
// Cập nhật head để nó trỏ đến node mới
head = newNode;
}
// Thêm phần tử vào cuối danh sách
public void addLast(T data) {
// Tạo node mới với dữ liệu được cung cấp
Node<T> newNode = new Node<>(data);
if (head == null) { // Nếu danh sách rỗng
head = newNode; // Cập nhật head để nó trỏ đến node mới
} else {
// Tìm node cuối cùng trong danh sách
Node<T> current = head;
while (current.next != null) {
current = current.next;
}
// Gán next của node cuối cùng đến node mới
current.next = newNode;
}
}
// Xóa phần tử đầu tiên trong danh sách
public void removeFirst() {
if (head != null) { // Nếu danh sách không rỗng
// Cập nhật head để nó trỏ đến node tiếp theo
head = head.next;
}
}
// Xóa phần tử cuối cùng trong danh sách
public void removeLast() {
if (head == null) { // Nếu danh sách rỗng, không làm gì cả
return;
}
if (head.next == null) { // Nếu danh sách chỉ có một phần tử
head = null; // Cập nhật head thành null
return;
}
// Tìm node trước node cuối cùng
Node<T> current = head;
while (current.next.next != null) {
current = current.next;
}
// Cập nhật next của node trước node cuối cùng thành null
current.next = null;
}
// In ra các phần tử trong danh sách
public void printList() {
Node<T> current = head;
while (current != null) {
System.out.print(current.data + " -> "); // In dữ liệu của node hiện tại
current = current.next; // Di chuyển đến node tiếp theo
}
System.out.println("null"); // Kết thúc danh sách
}
// Kiểm tra danh sách có rỗng hay không
public boolean isEmpty() {
return head == null; // Nếu head là null, danh sách là rỗng
}
// Lấy kích thước của danh sách
public int size() {
int count = 0;
Node<T> current = head;
while (current != null) {
count++; // Tăng kích thước khi di chuyển đến node tiếp theo
current = current.next;
}
return count; // Trả về kích thước danh sách
}
// Tìm kiếm phần tử trong danh sách
public boolean contains(T data) {
Node<T> current = head;
while (current != null) {
if (current.data.equals(data)) { // So sánh dữ liệu của node hiện tại với dữ liệu tìm kiếm
return true; // Nếu tìm thấy phần tử, trả về true
}
current = current.next; // Di chuyển đến node tiếp theo
}
return false; // Nếu không tìm thấy phần tử, trả về false
}
}
2. LinkedList kép (Doubly Linked List)
↳ Cấu trúc: Mỗi phần từ trong LinkedList kép được gọi là một nút (node). Mỗi nút (node) chứa ba thành phần chính:
↳ Previous (Con Trỏ): Con trỏ trỏ tới nút trước đó.
↳ Data (Giá trị): Giá trị của phần tử.
↳ Next (Con Trỏ): Con trỏ trỏ tới nút kế tiếp.
↳ Head: Là nút đầu tiên trong danh sách. Head chứa con trỏ Next trỏ đến nút tiếp theo và Previous của Head sẽ trỏ đến null.
↳ Tail: Là nút cuối cùng trong danh sách. Tail chứa con trỏ Previous trỏ đến nút trước đó và Next của Tail sẽ trỏ đến null.
Điều này cho phép danh sách có thể được duyệt từ đầu đến cuối hoặc ngược lại.
Thư viện chuẩn cho LinkedList kép (Doubly Linked List)
↳ Cấu trúc dữ liệu Node
Cấu trúc dữ liệu Node
// Định nghĩa một lớp generic Node với kiểu dữ liệu T
class Node<T> {
// Biến lưu trữ dữ liệu của node
T data;
// Tham chiếu đến node tiếp theo trong danh sách liên kết
Node<T> next;
// Tham chiếu đến node trước đó trong danh sách liên kết
Node<T> prev;
// Constructor để khởi tạo một node với dữ liệu được truyền vào
public Node(T data) {
// Gán giá trị truyền vào cho biến data
this.data = data;
// Khởi tạo biến next và prev là null, tức là node này chưa liên kết với node nào khác
this.next = null;
this.prev = null;
}
}
↳ Triển khai Doubly LinkedList
Triển khai Doubly LinkedList
// Định nghĩa lớp DoublyLinkedList với kiểu dữ liệu generic T
public class DoublyLinkedList<T> {
// Biến lưu trữ node đầu tiên của danh sách liên kết đôi
private Node<T> head;
// Biến lưu trữ node cuối cùng của danh sách liên kết đôi
private Node<T> tail;
// Constructor khởi tạo danh sách liên kết đôi rỗng
public DoublyLinkedList() {
this.head = null; // Khi tạo mới, head là null
this.tail = null; // Khi tạo mới, tail là null
}
// Thêm phần tử vào đầu danh sách
public void addFirst(T data) {
// Tạo node mới với dữ liệu được cung cấp
Node<T> newNode = new Node<>(data);
if (head == null) { // Nếu danh sách rỗng
head = tail = newNode; // Cập nhật cả head và tail để chúng trỏ đến node mới
} else {
newNode.next = head; // Gán next của node mới là head hiện tại
head.prev = newNode; // Gán prev của head hiện tại là node mới
head = newNode; // Cập nhật head để nó trỏ đến node mới
}
}
// Thêm phần tử vào cuối danh sách
public void addLast(T data) {
// Tạo node mới với dữ liệu được cung cấp
Node<T> newNode = new Node<>(data);
if (tail == null) { // Nếu danh sách rỗng
head = tail = newNode; // Cập nhật cả head và tail để chúng trỏ đến node mới
} else {
newNode.prev = tail; // Gán prev của node mới là tail hiện tại
tail.next = newNode; // Gán next của tail hiện tại là node mới
tail = newNode; // Cập nhật tail để nó trỏ đến node mới
}
}
// Xóa phần tử đầu tiên trong danh sách
public void removeFirst() {
if (head == null) { // Nếu danh sách rỗng, không làm gì cả
return;
}
if (head == tail) { // Nếu danh sách chỉ có một phần tử
head = tail = null; // Cập nhật cả head và tail thành null
} else {
head = head.next; // Cập nhật head để nó trỏ đến node tiếp theo
head.prev = null; // Cập nhật prev của node mới là null
}
}
// Xóa phần tử cuối cùng trong danh sách
public void removeLast() {
if (tail == null) { // Nếu danh sách rỗng, không làm gì cả
return;
}
if (head == tail) { // Nếu danh sách chỉ có một phần tử
head = tail = null; // Cập nhật cả head và tail thành null
} else {
tail = tail.prev; // Cập nhật tail để nó trỏ đến node trước đó
tail.next = null; // Cập nhật next của node mới là null
}
}
// In ra các phần tử trong danh sách từ đầu đến cuối
public void printListForward() {
Node<T> current = head;
while (current != null) {
System.out.print(current.data + " -> "); // In dữ liệu của node hiện tại
current = current.next; // Di chuyển đến node tiếp theo
}
System.out.println("null"); // Kết thúc danh sách
}
// In ra các phần tử trong danh sách từ cuối đến đầu
public void printListBackward() {
Node<T> current = tail;
while (current != null) {
System.out.print(current.data + " -> "); // In dữ liệu của node hiện tại
current = current.prev; // Di chuyển đến node trước đó
}
System.out.println("null"); // Kết thúc danh sách
}
// Kiểm tra danh sách có rỗng hay không
public boolean isEmpty() {
return head == null; // Nếu head là null, danh sách là rỗng
}
// Lấy kích thước của danh sách
public int size() {
int count = 0;
Node<T> current = head;
while (current != null) {
count++; // Tăng kích thước khi di chuyển đến node tiếp theo
current = current.next;
}
return count; // Trả về kích thước danh sách
}
// Tìm kiếm phần tử trong danh sách
public boolean contains(T data) {
Node<T> current = head;
while (current != null) {
if (current.data.equals(data)) { // So sánh dữ liệu của node hiện tại với dữ liệu tìm kiếm
return true; // Nếu tìm thấy phần tử, trả về true
}
current = current.next; // Di chuyển đến node tiếp theo
}
return false; // Nếu không tìm thấy phần tử, trả về false
}
}
3. LinkedList vòng (Circular Linked List)
↳ Cấu trúc: Mỗi phần tử trong LinkedList vòng được gọi là một nút (node). Mỗi nút (node) chứa hai phần chính:
↳ Data (Giá trị): Chứa giá trị của phần tử.
↳ Next (Con Trỏ): Là con trỏ hoặc liên kết tới nút kế tiếp trong danh sách.
↳ Head: Là nút đầu tiên trong danh sách, giống như trong LinkedList đơn hoặc LinkedList kép. Tuy nhiên, trong LinkedList vòng, con trỏ Next của Tail trỏ về Head, tạo thành một vòng tròn.
↳ Tail: Là nút cuối cùng trong danh sách. Trong LinkedList đơn vòng, Next của Tail trỏ về Head. Trong LinkedList kép vòng, Next của Tail trỏ về Head và Previous của Head trỏ về Tail.
Thư viện chuẩn cho LinkedList vòng (Circular Linked List)
↳ Cấu trúc dữ liệu Node
Cấu trúc dữ liệu Node
// Định nghĩa lớp generic Node với kiểu dữ liệu T
class Node<T> {
// Biến lưu trữ dữ liệu của node
T data;
// Tham chiếu đến node tiếp theo trong danh sách liên kết
Node<T> next;
// Constructor để khởi tạo một node với dữ liệu được truyền vào
public Node(T data) {
// Gán giá trị truyền vào cho biến data
this.data = data;
// Khởi tạo biến next là null, tức là node này chưa liên kết với node nào khác
this.next = null;
}
}
↳ Triển khai Circular LinkedList
Triển khai Circular LinkedList
// Định nghĩa lớp CircularLinkedList với kiểu dữ liệu generic T
public class CircularLinkedList<T> {
// Biến lưu trữ node đầu tiên của danh sách liên kết vòng
private Node<T> head;
// Biến lưu trữ node cuối cùng của danh sách liên kết vòng
private Node<T> tail;
// Constructor khởi tạo danh sách liên kết vòng rỗng
public CircularLinkedList() {
this.head = null; // Khi tạo mới, head là null
this.tail = null; // Khi tạo mới, tail là null
}
// Thêm phần tử vào cuối danh sách
public void addLast(T data) {
Node<T> newNode = new Node<>(data); // Tạo node mới với dữ liệu được cung cấp
if (head == null) { // Nếu danh sách rỗng
head = tail = newNode; // Cập nhật cả head và tail để chúng trỏ đến node mới
tail.next = head; // Tạo liên kết vòng bằng cách cho tail.next trỏ đến head
} else {
tail.next = newNode; // Gán next của tail hiện tại là node mới
tail = newNode; // Cập nhật tail để nó trỏ đến node mới
tail.next = head; // Tạo liên kết vòng bằng cách cho tail.next trỏ đến head
}
}
// Thêm phần tử vào đầu danh sách
public void addFirst(T data) {
Node<T> newNode = new Node<>(data); // Tạo node mới với dữ liệu được cung cấp
if (head == null) { // Nếu danh sách rỗng
head = tail = newNode; // Cập nhật cả head và tail để chúng trỏ đến node mới
tail.next = head; // Tạo liên kết vòng bằng cách cho tail.next trỏ đến head
} else {
newNode.next = head; // Gán next của node mới là head hiện tại
head = newNode; // Cập nhật head để nó trỏ đến node mới
tail.next = head; // Tạo liên kết vòng bằng cách cho tail.next trỏ đến head
}
}
// Xóa phần tử đầu tiên trong danh sách
public void removeFirst() {
if (head == null) { // Nếu danh sách rỗng, không làm gì cả
return;
}
if (head == tail) { // Nếu danh sách chỉ có một phần tử
head = tail = null; // Cập nhật cả head và tail thành null
} else {
head = head.next; // Cập nhật head để nó trỏ đến node tiếp theo
tail.next = head; // Tạo liên kết vòng bằng cách cho tail.next trỏ đến head mới
}
}
// Xóa phần tử cuối cùng trong danh sách
public void removeLast() {
if (head == null) { // Nếu danh sách rỗng, không làm gì cả
return;
}
if (head == tail) { // Nếu danh sách chỉ có một phần tử
head = tail = null; // Cập nhật cả head và tail thành null
} else {
Node<T> current = head;
while (current.next != tail) { // Di chuyển đến node trước tail
current = current.next;
}
tail = current; // Cập nhật tail để nó trỏ đến node trước đó
tail.next = head; // Tạo liên kết vòng bằng cách cho tail.next trỏ đến head
}
}
// In ra các phần tử trong danh sách
public void printList() {
if (head == null) { // Nếu danh sách rỗng
System.out.println("Danh sách rỗng.");
return;
}
Node<T> current = head;
do {
System.out.print(current.data + " -> "); // In dữ liệu của node hiện tại
current = current.next; // Di chuyển đến node tiếp theo
} while (current != head); // Lặp lại cho đến khi trở lại head
System.out.println("(vòng lại về đầu)"); // Thông báo vòng lại về đầu
}
// Kiểm tra danh sách có rỗng hay không
public boolean isEmpty() {
return head == null; // Nếu head là null, danh sách là rỗng
}
// Lấy kích thước của danh sách
public int size() {
if (head == null) { // Nếu danh sách rỗng
return 0;
}
int count = 0;
Node<T> current = head;
do {
count++; // Tăng kích thước khi di chuyển đến node tiếp theo
current = current.next;
} while (current != head); // Lặp lại cho đến khi trở lại head
return count; // Trả về kích thước danh sách
}
// Tìm kiếm phần tử trong danh sách
public boolean contains(T data) {
if (head == null) { // Nếu danh sách rỗng
return false;
}
Node<T> current = head;
do {
if (current.data.equals(data)) { // So sánh dữ liệu của node hiện tại với dữ liệu tìm kiếm
return true; // Nếu tìm thấy phần tử, trả về true
}
current = current.next; // Di chuyển đến node tiếp theo
} while (current != head); // Lặp lại cho đến khi trở lại head
return false; // Nếu không tìm thấy phần tử, trả về false
}
}
Cách hoạt động của LinkedList:
Thêm phần tử:
↳ Thêm vào đầu: Tạo một nút mới và trỏ Next của nó tới Head hiện tại. Sau đó cập nhật Head để trỏ tới nút mới.
↳ Thêm vào cuối: Duyệt qua các nút cho đến khi tới Tail, sau đó trỏ Next của Tail tới nút mới. Cập nhật Tail trỏ tới nút mới.
Xóa phần tử:
↳ Xóa ở đầu: Trỏ Head tới nút tiếp theo của nút hiện tại (Head = Head.Next).
↳ Xóa ở cuối: Duyệt qua các nút cho đến khi tìm thấy nút đứng trước Tail, sau đó trỏ Next của nó tới null và cập nhật Tail trỏ tới nút đó.
↳ Duyệt qua các phần tử: Duyệt qua các phần tử trong LinkedList bắt đầu từ Head cho đến khi gặp null.
↳ Tìm kiếm phần tử: Duyệt qua các phần tử từ Head và so sánh giá trị của mỗi nút với giá trị cần tìm kiếm.
Khai báo Class LinkedList<E> trong Java
Để sử dụng Class LinkedList<E>, bạn cần import gói java.util vào đầu file Java của mình. Gói này cung cấp các lớp và giao diện để làm việc với các collection trong Java.
Cú pháp câu lệnh import:
Cú Pháp
import java.util.LinkedList;
Cú pháp khai báo Class LinkedList <E>:
Cú Pháp
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable
Dưới đây là giải thích chi tiết về cú pháp khai báo này:
↳ public: Lớp LinkedList có thể được sử dụng từ bất kỳ đâu trong chương trình.
↳ class: Từ khóa khai báo một lớp trong Java.
↳ LinkedList<E>: Tên lớp là LinkedList, sử dụng generic E để đại diện cho kiểu phần tử chứa trong danh sách liên kết.
↳ extends AbstractSequentialList<E>: Lớp LinkedList kế thừa từ lớp AbstractSequentialList<E>. AbstractSequentialList là một lớp cơ sở trừu tượng cung cấp một số phương thức cơ bản cho các lớp danh sách tuần tự. LinkedList mở rộng và thực hiện các phương thức này bằng cách sử dụng cấu trúc dữ liệu danh sách liên kết đôi.
↳ implements List<E>: Lớp LinkedList triển khai interface List, nghĩa là hỗ trợ các thao tác như thêm, xóa, truy cập phần tử theo chỉ số(index).
↳ implements Deque<E>: Đồng thời LinkedList cũng là một Deque – tức là hỗ trợ thao tác với cả hai đầu của danh sách (double-ended queue) như addFirst, removeLast...
↳ implements Cloneable: Lớp LinkedList triển khai giao diện Cloneable, có nghĩa là bạn có thể tạo bản sao của đối tượng LinkedList bằng cách sử dụng phương thức clone(). Tuy nhiên, việc thực hiện Cloneable không đảm bảo rằng clone() sẽ hoạt động chính xác và bạn cần phải thực hiện clone() một cách thận trọng.
↳ implements Serializable: Lớp LinkedList cũng thực hiện giao diện Serializable, cho phép đối tượng LinkedList có thể được tuần tự hóa (serialized). Điều này có nghĩa là bạn có thể lưu trữ trạng thái của đối tượng LinkedList vào một luồng (stream) và phục hồi nó từ luồng sau đó.
Các constructor của lớp LinkedList
Khi làm việc với LinkedList trong Java, việc khởi tạo (tạo ra) một đối tượng LinkedList là bước đầu tiên. LinkedList cung cấp một vài cách để bạn có thể khởi tạo một danh sách mới, tùy thuộc vào nhu cầu của mình. Dưới đây là các constructor chính mà bạn sẽ thường sử dụng:
↳ LinkedList(): Khởi tạo một danh sách rỗng.
↳ LinkedList(Collection<? extends E> c): Khởi tạo một danh sách chứa các phần tử của bộ sưu tập đã cho, theo thứ tự chúng được trả về bởi iterator của bộ sưu tập.
Ví dụ
// Tạo một danh sách rỗng
LinkedList<String> fruits = new LinkedList<>();
// Tạo một danh sách chứa các phần tử từ một bộ sưu tập khác
List<String> colors = Arrays.asList("red", "green", "blue");
LinkedList<String> list = new LinkedList<>(colors);
Lưu ý:
↳ Khi tạo một LinkedList từ một bộ sưu tập khác, các phần tử sẽ được sao chép vào LinkedList mới. Thay đổi bộ sưu tập gốc sẽ không ảnh hưởng đến LinkedList đã được tạo.
Các phương thức chính trong lớp LinkedList
LinkedList là một triển khai cụ thể của giao diện List, phù hợp cho các trường hợp cần thao tác với các phần tử ở đầu hoặc cuối danh sách một cách hiệu quả. Dưới đây là danh sách tất cả các phương thức của Class LinkedList<E> trong Java:
↳ boolean add(E e): Thêm phần tử e vào cuối danh sách.
↳ void add(int index, E element): Chèn phần tử element vào vị trí index trong danh sách.
↳ boolean addAll(Collection<? extends E> c): Thêm tất cả các phần tử trong collection c vào cuối danh sách.
↳ boolean addAll(int index, Collection<? extends E> c): Chèn tất cả các phần tử trong collection c vào vị trí index trong danh sách.
↳ void addFirst(E e): Thêm phần tử e vào đầu danh sách.
↳ void addLast(E e): Thêm phần tử e vào cuối danh sách.
↳ void clear(): Xóa tất cả các phần tử khỏi danh sách.
↳ Object clone(): Trả về một bản sao nông của instance LinkedList này.
↳ boolean contains(Object o): Trả về true nếu danh sách chứa phần tử o.
↳ Iterator<E> descendingIterator(): Trả về một iterator duyệt qua các phần tử trong danh sách theo thứ tự ngược.
↳ element(): Lấy phần tử đầu tiên của danh sách mà không xóa nó.
↳ get(int index): Lấy phần tử tại vị trí index trong danh sách.
↳ getFirst(): Lấy phần tử đầu tiên của danh sách.
↳ getLast(): Lấy phần tử cuối cùng của danh sách.
↳ int indexOf(Object o): Trả về chỉ số lần xuất hiện đầu tiên của phần tử o trong danh sách, hoặc -1 nếu danh sách không chứa phần tử o.
↳ int lastIndexOf(Object o): Trả về chỉ số lần xuất hiện cuối cùng của phần tử o trong danh sách, hoặc -1 nếu danh sách không chứa phần tử o.
↳ ListIterator<E> listIterator(int index): Trả về một list iterator duyệt qua các phần tử trong danh sách theo thứ tự đúng, bắt đầu từ vị trí index đã cho.
↳ boolean offer(E e): Thêm phần tử e vào cuối danh sách.
↳ boolean offerFirst(E e): Thêm phần tử e vào đầu danh sách.
↳ boolean offerLast(E e): Thêm phần tử e vào cuối danh sách.
↳ peek(): Lấy phần tử đầu tiên của danh sách mà không xóa nó.
↳ peekFirst(): Lấy phần tử đầu tiên của danh sách mà không xóa nó.
↳ peekLast(): Lấy phần tử cuối cùng của danh sách mà không xóa nó.
↳ poll(): Lấy và xóa phần tử đầu tiên của danh sách.
↳ pollFirst(): Lấy và xóa phần tử đầu tiên của danh sách.
↳ pollLast(): Lấy và xóa phần tử cuối cùng của danh sách.
↳ pop(): Lấy và xóa phần tử đầu tiên của danh sách (được coi là đỉnh của stack).
↳ void push(E e): Thêm phần tử e vào đầu danh sách (được coi là đáy của stack).
↳ remove(): Lấy và xóa phần tử đầu tiên của danh sách.
↳ remove(int index): Xóa phần tử tại vị trí index trong danh sách.
↳ boolean remove(Object o): Xóa phần tử đầu tiên xuất hiện của phần tử o trong danh sách.
↳ removeFirst(): Xóa và trả về phần tử đầu tiên của danh sách.
↳ oolean removeFirstOccurrence(Object o): Xóa phần tử đầu tiên xuất hiện của phần tử o trong danh sách (khi duyệt từ đầu đến cuối).
↳ removeLast(): Xóa và trả về phần tử cuối cùng của danh sách.
↳ boolean removeLastOccurrence(Object o): Xóa phần tử cuối cùng xuất hiện của phần tử o trong danh sách (khi duyệt từ đầu đến cuối).
↳ set(int index, E element): Thay thế phần tử tại vị trí index trong danh sách bằng phần tử element.
↳ int size(): Trả về số lượng phần tử trong danh sách.
↳ Spliterator<E> spliterator(): Tạo một Spliterator duyệt qua các phần tử trong danh sách.
↳ Object[] toArray(): Trả về một mảng chứa tất cả các phần tử trong danh sách theo thứ tự đúng (từ phần tử đầu tiên đến phần tử cuối cùng).
↳ <T> T[] toArray(T[] a): Trả về một mảng chứa tất cả các phần tử trong danh sách theo thứ tự đúng (từ phần tử đầu tiên đến phần tử cuối cùng); kiểu thời gian chạy của mảng được trả về là kiểu của mảng đã cho.
Ví dụ về cách sử dụng các phương thức thêm phần tử trong LinkedList
Dưới đây là một ví dụ minh họa về cách sử dụng các phương thức thêm phần tử của LinkedList trong một lớp Java:
Ví dụ: Example.java
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class Example {
public static void main(String[] args) {
// Tạo một LinkedList với kiểu dữ liệu Integer
LinkedList<Integer> list = new LinkedList<>();
// Thêm phần tử vào cuối danh sách
list.add(10);
System.out.println("Sau khi sử dụng add(E e): " + list);
// Chèn phần tử vào vị trí index
list.add(1, 20);
System.out.println("Sau khi sử dụng add(int index, E element): " + list);
// Thêm tất cả các phần tử của một collection vào cuối danh sách
List<Integer> moreNumbers = Arrays.asList(30, 40);
list.addAll(moreNumbers);
System.out.println("Sau khi sử dụng addAll(Collection<? extends E> c): " + list);
// Thêm tất cả các phần tử của một collection vào vị trí index
List<Integer> additionalNumbers = Arrays.asList(50, 60);
list.addAll(2, additionalNumbers);
System.out.println("Sau khi sử dụng addAll(int index, Collection<? extends E> c): " + list);
// Thêm phần tử vào đầu danh sách
list.addFirst(5);
System.out.println("Sau khi sử dụng addFirst(E e): " + list);
// Thêm phần tử vào cuối danh sách (tương tự add(E e))
list.addLast(70);
System.out.println("Sau khi sử dụng addLast(E e): " + list);
}
}
Kết quả của chương trình là:
Sau khi sử dụng add(int index, E element): [10, 20]
Sau khi sử dụng addAll(Collection<? extends E> c): [10, 20, 30, 40]
Sau khi sử dụng addAll(int index, Collection<? extends E> c): [10, 20, 50, 60, 30, 40]
Sau khi sử dụng addFirst(E e): [5, 10, 20, 50, 60, 30, 40]
Sau khi sử dụng addLast(E e): [5, 10, 20, 50, 60, 30, 40, 70]
Ví dụ cách sử dụng các phương thức xóa phần tử trong LinkedList
Dưới đây là ví dụ minh họa cách sử dụng các phương thức xóa phần tử của LinkedList trong một lớp Java:
Ví dụ: Example.java
import java.util.LinkedList;
public class Example {
public static void main(String[] args) {
// Tạo một LinkedList với kiểu dữ liệu Integer và thêm các phần tử vào
LinkedList<Integer> list = new LinkedList<>();
list.add(10);
list.add(20);
list.add(30);
list.add(40);
list.add(30); // Thêm phần tử trùng lặp để kiểm tra removeFirstOccurrence và removeLastOccurrence
list.add(50);
// In danh sách hiện tại
System.out.println("Danh sách hiện tại: " + list);
// Xóa phần tử tại vị trí index 2
list.remove(2);
System.out.println("Sau khi sử dụng remove(int index): " + list);
// Xóa phần tử đầu tiên có giá trị bằng 40
list.remove(Integer.valueOf(40)); // remove(Object o)
System.out.println("Sau khi sử dụng remove(Object o): " + list);
// Xóa và trả về phần tử đầu tiên
Integer firstElement = list.removeFirst();
System.out.println("Phần tử đầu tiên bị xóa: " + firstElement);
System.out.println("Sau khi sử dụng removeFirst(): " + list);
// Xóa và trả về phần tử cuối cùng
Integer lastElement = list.removeLast();
System.out.println("Phần tử cuối cùng bị xóa: " + lastElement);
System.out.println("Sau khi sử dụng removeLast(): " + list);
// Xóa lần xuất hiện đầu tiên của phần tử có giá trị bằng 30
list.removeFirstOccurrence(30);
System.out.println("Sau khi sử dụng removeFirstOccurrence(Object o): " + list);
// Xóa lần xuất hiện cuối cùng của phần tử có giá trị bằng 30
list.removeLastOccurrence(30);
System.out.println("Sau khi sử dụng removeLastOccurrence(Object o): " + list);
// Xóa tất cả các phần tử trong danh sách
list.clear();
System.out.println("Sau khi sử dụng clear(): " + list);
}
}
Kết quả của chương trình là:
Danh sách hiện tại: [10, 20, 30, 40, 30, 50] Sau khi sử dụng
remove(int index): [10, 20, 40, 30, 50] Sau khi sử dụng
remove(Object o): [10, 20, 30, 50]Phần tử đầu tiên bị xóa: 10 Sau
khi sử dụng removeFirst(): [20, 30, 50] Phần tử cuối cùng bị xóa: 50
Sau khi sử dụng removeLast(): [20, 30] Sau khi sử dụng
removeFirstOccurrence(Object o): [20] Sau khi sử dụng
removeLastOccurrence(Object o): [20] Sau khi sử dụng clear(): []
Ví dụ cách sử dụng các phương thức liên quan đến việc truy xuất và kiểm tra trong LinkedList
Dưới đây là ví dụ minh họa cách sử dụng các phương thức liên quan đến việc truy xuất và kiểm tra phần tử của LinkedList trong một lóp java:
Ví dụ: Example.java
import java.util.LinkedList;
public class Example {
public static void main(String[] args) {
// Tạo một LinkedList với kiểu dữ liệu Integer và thêm các phần tử vào
LinkedList<Integer> list = new LinkedList<>();
list.add(10);
list.add(20);
list.add(30);
list.add(40);
list.add(30); // Thêm phần tử trùng lặp để kiểm tra indexOf và lastIndexOf
list.add(50);
// In danh sách hiện tại
System.out.println("Danh sách hiện tại: " + list);
// Lấy phần tử tại vị trí index 2
Integer elementAtIndex2 = list.get(2);
System.out.println("Phần tử tại vị trí index 2: " + elementAtIndex2);
// Kiểm tra xem danh sách có chứa phần tử 30 không
boolean contains30 = list.contains(30);
System.out.println("Danh sách có chứa phần tử 30 không: " + contains30);
// Trả về chỉ số của lần xuất hiện đầu tiên của phần tử 30
int indexOf30 = list.indexOf(30);
System.out.println("Chỉ số của lần xuất hiện đầu tiên của 30: " + indexOf30);
// Trả về chỉ số của lần xuất hiện cuối cùng của phần tử 30
int lastIndexOf30 = list.lastIndexOf(30);
System.out.println("Chỉ số của lần xuất hiện cuối cùng của 30: " + lastIndexOf30);
// Kiểm tra xem danh sách có rỗng không
boolean isEmpty = list.isEmpty();
System.out.println("Danh sách có rỗng không: " + isEmpty);
// Trả về số lượng phần tử trong danh sách
int size = list.size();
System.out.println("Số lượng phần tử trong danh sách: " + size);
// Lấy phần tử đầu hoặc cuối mà không xóa
Integer firstElementPeek = list.peek();
Integer firstElementPeekFirst = list.peekFirst();
Integer lastElementPeekLast = list.peekLast();
System.out.println("Phần tử đầu (peek): " + firstElementPeek);
System.out.println("Phần tử đầu (peekFirst): " + firstElementPeekFirst);
System.out.println("Phần tử cuối (peekLast): " + lastElementPeekLast);
// Lấy phần tử đầu hoặc cuối (tương tự peek)
Integer firstElement = list.element();
Integer firstElementGetFirst = list.getFirst();
Integer lastElementGetLast = list.getLast();
System.out.println("Phần tử đầu (element): " + firstElement);
System.out.println("Phần tử đầu (getFirst): " + firstElementGetFirst);
System.out.println("Phần tử cuối (getLast): " + lastElementGetLast);
}
}
Kết quả của chương trình là:
Phần tử tại vị trí index 2: 30
Danh sách có chứa phần tử 30 không: true
Chỉ số của lần xuất hiện đầu tiên của 30: 2
Chỉ số của lần xuất hiện cuối cùng của 30: 4
Danh sách có rỗng không: false
Số lượng phần tử trong danh sách: 6
Phần tử đầu (peek): 10
Phần tử đầu (peekFirst): 10
Phần tử cuối (peekLast): 50
Phần tử đầu (element): 10
Phần tử đầu (getFirst): 10
Phần tử cuối (getLast): 50
Ví dụ LinkedList với đối tượng do người dùng định nghĩa
Dưới đây là một ví dụ về cách sử dụng LinkedList với các đối tượng do người dùng định nghĩa. Chúng ta sẽ tạo một lớp Student để biểu diễn thông tin của sinh viên, sau đó thêm các đối tượng Student vào LinkedList và thực hiện một số thao tác cơ bản trên danh sách này.
Ví dụ: Example.java
package style;
import java.util.LinkedList;
class Student {
private String name;
private int age;
private double grade;
// Constructor
public Student(String name, int age, double grade) {
this.name = name;
this.age = age;
this.grade = grade;
}
// Getters
public String getName() {
return name;
}
public int getAge() {
return age;
}
public double getGrade() {
return grade;
}
// Override phương thức toString để in thông tin sinh viên
@Override
public String toString() {
return "Student{" +
"Tên='" + name + '\'' +
", Tuổi=" + age +
", Điểm=" + grade +
'}';
}
}
public class LinkedListExample {
public static void main(String[] args) {
// Tạo một LinkedList để chứa các đối tượng Student
LinkedList<Student> studentList = new LinkedList<>();
// Thêm các sinh viên vào danh sách
studentList.add(new Student("Nam", 20, 8.5));
studentList.add(new Student("Linh", 22, 7.8));
studentList.add(new Student("Phong", 21, 9.0));
// In danh sách các sinh viên
System.out.println("Danh sách sinh viên:");
for (Student student : studentList) {
System.out.println(student);
}
// Lấy sinh viên tại vị trí index 1
Student studentAtIndex1 = studentList.get(1);
System.out.println("\nSinh viên tại vị trí index 1: " + studentAtIndex1);
// Kiểm tra xem danh sách có chứa sinh viên với tên "Linh" không
boolean containsLinh = studentList.contains(new Student("Linh", 22, 7.8));
System.out.println("\nDanh sách có chứa sinh viên Linh không: " + containsLinh);
// Xóa sinh viên đầu tiên trong danh sách
Student removedStudent = studentList.removeFirst();
System.out.println("\nSinh viên đầu tiên bị xóa: " + removedStudent);
// In lại danh sách sau khi xóa
System.out.println("\nDanh sách sinh viên sau khi xóa:");
for (Student student : studentList) {
System.out.println(student);
}
}
}
Kết quả của chương trình là:
Danh sách sinh viên:
Student{Tên='Nam', Tuổi=20, Điểm=8.5}
Student{Tên='Linh', Tuổi=22, Điểm=7.8}
Student{Tên='Phong', Tuổi=21, Điểm=9.0}
Sinh viên tại vị trí index 1: Student{Tên='Linh', Tuổi=22, Điểm=7.8}
Danh sách có chứa sinh viên Linh không: false
Sinh viên đầu tiên bị xóa: Student{Tên='Nam', Tuổi=20, Điểm=8.5}
Danh sách sinh viên sau khi xóa:
Student{Tên='Linh', Tuổi=22, Điểm=7.8}
Student{Tên='Phong', Tuổi=21, Điểm=9.0}
Ví dụ về cách sử dụng iterator() với LinkedList
Dưới đây là một ví dụ về cách sử dụng phương thức iterator() để trả về một Iterator và duyệt qua các phần tử của LinkedList trong java:
Ví dụ: Example.java
import java.util.Iterator;
import java.util.LinkedList;
public class Example {
public static void main(String[] args) {
// Tạo một LinkedList với kiểu dữ liệu Integer và thêm các phần tử vào
LinkedList<Integer> list = new LinkedList<>();
list.add(10);
list.add(20);
list.add(30);
list.add(40);
list.add(50);
// Trả về một Iterator để duyệt qua các phần tử
Iterator<Integer> iterator = list.iterator();
System.out.println("Duyệt qua các phần tử của LinkedList:");
// Sử dụng Iterator để duyệt qua các phần tử trong danh sách
while (iterator.hasNext()) {
Integer element = iterator.next();
System.out.println(element);
}
}
}
Kết quả của chương trình là:
10
20
30
40
50
Ví dụ về cách sử dụng listIterator() với LinkedList
Dưới đây là một ví dụ về cách sử dụng phương thức listIterator() để trả về một ListIterator và duyệt qua các phần tử của LinkedList với kiểu dữ liệu Double:
Ví dụ: Example.java
import java.util.LinkedList;
import java.util.ListIterator;
public class Example {
public static void main(String[] args) {
// Tạo một LinkedList với kiểu dữ liệu Double và thêm các phần tử vào
LinkedList<Double> list = new LinkedList<>();
list.add(10.5);
list.add(20.2);
list.add(30.3);
list.add(40.4);
list.add(50.5);
// Trả về một ListIterator để duyệt qua các phần tử
ListIterator<Double> listIterator = list.listIterator();
System.out.println("Duyệt qua các phần tử của LinkedList theo thứ tự từ đầu đến cuối:");
// Duyệt qua các phần tử từ đầu đến cuối
while (listIterator.hasNext()) {
Double element = listIterator.next();
System.out.println(element);
}
System.out.println("Duyệt qua các phần tử của LinkedList theo thứ tự từ cuối về đầu:");
// Duyệt qua các phần tử từ cuối về đầu
while (listIterator.hasPrevious()) {
Double element = listIterator.previous();
System.out.println(element);
}
}
}
Kết quả của chương trình là:
Duyệt qua các phần tử của LinkedList theo thứ tự từ đầu đến cuối:
10.5
20.2
30.3
40.4
50.5
Duyệt qua các phần tử của LinkedList theo thứ tự từ cuối về đầu:
50.5
40.4
30.3
20.2
10.5
Ví dụ sử dụng phương thức descendingIterator() với LinkedList
Dưới đây là một ví dụ về cách sử dụng phương thức descendingIterator() để trả về một iterator cho phép duyệt qua các phần tử của LinkedList theo thứ tự ngược:
Ví dụ: Example.java
import java.util.Iterator;
import java.util.LinkedList;
public class Example {
public static void main(String[] args) {
// Tạo một LinkedList với kiểu dữ liệu String và thêm các phần tử vào
LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.add("Cherry");
list.add("Date");
list.add("Elderberry");
// Trả về một Iterator để duyệt qua các phần tử theo thứ tự ngược
Iterator<String> descendingIterator = list.descendingIterator();
System.out.println("Duyệt qua các phần tử của LinkedList theo thứ tự ngược:");
// Duyệt qua các phần tử từ cuối lên đầu
while (descendingIterator.hasNext()) {
String element = descendingIterator.next();
System.out.println(element);
}
}
}
Kết quả của chương trình là:
Elderberry
Date
Cherry
Banana
Apple
Ví dụ ử dụng phương thức toArray(T[] a) với LinkedList
Dưới đây là một ví dụ về cách sử dụng phương thức toArray(T[] a) để chuyển một LinkedList thành một mảng có kiểu dữ liệu được chỉ định, cụ thể là mảng String[]:
Ví dụ: Example.java
import java.util.LinkedList;
public class Example {
public static void main(String[] args) {
// Tạo một LinkedList với kiểu dữ liệu String và thêm các phần tử vào
LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.add("Cherry");
list.add("Date");
list.add("Elderberry");
// Chuyển LinkedList thành một mảng kiểu String[]
String[] array = list.toArray(new String[0]);
// In các phần tử trong mảng
System.out.println("Các phần tử trong mảng:");
for (String element : array) {
System.out.println(element);
}
}
}
Kết quả của chương trình là:
Apple
Banana
Cherry
Date
Elderberry
So sánh ArrayList and LinkedList
Cả ArrayList và LinkedList đều là các lớp trong Java thuộc gói java.util, được sử dụng để lưu trữ danh sách các phần tử. Tuy nhiên, chúng có những đặc điểm và hiệu suất khác nhau phù hợp với các trường hợp sử dụng cụ thể. Dưới đây là sự so sánh giữa ArrayList và LinkedList:
Điểm giống giữa class ArrayList và class LinkedList
Dưới đây là tóm tắt các điểm giống nhau giữa ArrayList và LinkedList:
↳ Phần tử null: Cả ArrayList và LinkedList đều cho phép lưu trữ các phần tử null.
↳ Giao diện List: Cả hai đều triển khai giao diện List, vì vậy chúng có nhiều phương thức chung như add(), remove(), get(), set(), và các phương thức khác.
↳ Thứ tự phần tử: Cả hai đều duy trì thứ tự của các phần tử theo thứ tự chèn vào.
↳ Không đồng bộ hóa: Cả hai đều không đồng bộ hóa mặc định, có nghĩa là chúng không an toàn trong môi trường đa luồng. Bạn cần phải đồng bộ hóa thủ công nếu chúng được truy cập bởi nhiều luồng cùng lúc.
Điểm khác biệt giữa class ArrayList và class LinkedList
Dưới đây là tóm tắt các điểm khác nhau giữa ArrayList và LinkedList:
| Đặc điểm | ArrayList | LinkedList |
|---|---|---|
| Cấu trúc | Mảng động (Dynamic Array) | Danh sách liên kết kép (Doubly Linked List) |
| Thao tác truy xuất phần tử | Nhanh, thời gian truy xuất là O(1) | Chậm, thời gian truy xuất là O(n) |
| Thao tác thêm/xóa phần tử | Thêm/xóa ở cuối là O(1) Thêm/xóa ở giữa/đầu là O(n) | Thêm/xóa ở đầu/cuối là O(1) Thêm/xóa ở giữa là O(n) |
| Thêm/xóa ở giữa | Chậm (O(n)) | Nhanh (O(1)) |
| Sử dụng bộ nhớ | Sử dụng ít bộ nhớ hơn | Sử dụng nhiều bộ nhớ hơn do cần lưu trữ liên kết |
| Dung lượng ban đầu | Khi khởi tạo có dung lượng ban đầu là 10. | Khi khởi tạo, LinkedList tạo một danh sách rỗng mà không có dung lượng ban đầu cố định. |
| Khả năng sử dụng | Chỉ có thể hoạt động như một danh sách (List) | Có thể hoạt động như một danh sách (List) hoặc một hàng đợi (Queue) |
| Mục đích sử dụng | Thích hợp cho việc lưu trữ và truy cập dữ liệu. | Thích hợp cho việc thao tác với dữ liệu, như thêm, xóa, hoặc sắp xếp. |
| Vị trí lưu trữ | Các phần tử được lưu trữ liên tiếp trong bộ nhớ. | Các phần tử được lưu trữ không liên tiếp, mỗi phần tử chứa tham chiếu đến phần tử trước và sau nó. |
Khi nào nên sử dụng?
↳ ArrayList: Thích hợp cho các thao tác truy cập nhanh vào các phần tử theo chỉ số, nhưng không hiệu quả khi thêm hoặc xóa phần tử ở giữa danh sách.
↳ LinkedList: Thích hợp cho các thao tác thêm và xóa phần tử ở đầu hoặc giữa danh sách, nhưng truy cập phần tử bằng chỉ số sẽ chậm hơn.
Dưới đây là một ví dụ đơn giản trong đó chúng ta sử dụng cả ArrayList và LinkedList :
Ví dụ: Example.java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Example {
public static void main(String[] args) {
// Khởi tạo ArrayList và LinkedList
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
// Thêm phần tử vào cuối danh sách
for (int i = 0; i < 5; i++) {
arrayList.add(i);
linkedList.add(i);
}
// In danh sách ban đầu
System.out.println("ArrayList ban đầu: " + arrayList);
System.out.println("LinkedList ban đầu: " + linkedList);
// Thêm phần tử ở giữa danh sách
arrayList.add(2, 100);
linkedList.add(2, 100);
// In danh sách sau khi thêm phần tử
System.out.println("ArrayList sau khi thêm phần tử ở giữa: " + arrayList);
System.out.println("LinkedList sau khi thêm phần tử ở giữa: " + linkedList);
// Xóa phần tử ở giữa danh sách
arrayList.remove(2);
linkedList.remove(2);
// In danh sách sau khi xóa phần tử
System.out.println("ArrayList sau khi xóa phần tử ở giữa: " + arrayList);
System.out.println("LinkedList sau khi xóa phần tử ở giữa: " + linkedList);
// Truy cập phần tử ở giữa danh sách
int arrayListElement = arrayList.get(2);
int linkedListElement = linkedList.get(2);
// In phần tử ở giữa
System.out.println("Phần tử thứ 2 trong ArrayList: " + arrayListElement);
System.out.println("Phần tử thứ 2 trong LinkedList: " + linkedListElement);
}
}
Kết quả của chương trình là:
ArrayList ban đầu: [0, 1, 2, 3, 4]
LinkedList ban đầu: [0, 1, 2, 3, 4]
ArrayList sau khi thêm phần tử ở giữa: [0, 1, 100, 2, 3, 4]
LinkedList sau khi thêm phần tử ở giữa: [0, 1, 100, 2, 3, 4]
ArrayList sau khi xóa phần tử ở giữa: [0, 1, 2, 3, 4]
LinkedList sau khi xóa phần tử ở giữa: [0, 1, 2, 3, 4]
Phần tử thứ 2 trong ArrayList: 2
Phần tử thứ 2 trong LinkedList: 2
Như vậy, bạn đã nắm được các phương thức chính của LinkedList. Khác với ArrayList, LinkedList đặc biệt hiệu quả cho các thao tác thêm hoặc xóa phần tử ở đầu và cuối danh sách. Việc lựa chọn giữa ArrayList và LinkedList tùy thuộc vào nhu cầu cụ thể của ứng dụng bạn: cần truy cập ngẫu nhiên nhanh chóng hay thao tác chèn/xóa hiệu quả. Hiểu rõ ưu điểm của LinkedList sẽ giúp bạn tối ưu hóa hiệu suất khi làm việc với các cấu trúc dữ liệu động trong Java.