Java: LinkedList

Giới thiệu

Một collection có thứ tự được gọi là một danh sách. Nó còn được gọi là một chuỗi (sequence). Sau đây là các đặc điểm của danh sách:

• Người dùng có quyền kiểm soát từng phần tử trong danh sách.
• Người dùng có thể truy cập và tìm kiếm các phần tử trong danh sách bằng cách sử dụng chỉ mục số nguyên.
• Có thể tồn tại các phần tử trùng lặp trong một danh sách.
• Có thể tồn tại nhiều phần tử rỗng.
• Chỉ mục số nguyên có thể được sử dụng để truy cập các phần tử và tìm kiếm chúng trong danh sách.
• Tương tự như mảng Java, danh sách dựa trên 0.
• Interface List bao gồm bốn phương thức để truy cập được lập chỉ mục vào các phần tử danh sách.

Lưu ý - Đối với một số triển khai nhất định, các hoạt động như vậy có thể thực thi theo thời gian tỷ lệ với giá trị chỉ mục.

Interface List bao gồm các khai báo bổ sung bằng cách sử dụng các phương thức iterator, remove, add, hashCode và equals. Phương thức equals() giúp kiểm tra sự bằng nhau logic của hai đối tượng List. Hai đối tượng List là bằng nhau nếu chúng chứa các phần tử giống nhau theo cùng một thứ tự. Nó cũng có thể bao gồm các khai báo cho các phương thức kế thừa khác.

List cung cấp ListIterator, là một trình lặp đặc biệt. Điều này được sử dụng để chèn và thay thế một phần tử. Điều này cũng được sử dụng để truy cập hai chiều cùng với các hoạt động bình thường. Một phương thức được sử dụng để lấy một trình lặp danh sách, bắt đầu từ một vị trí cụ thể trong danh sách.

Có hai phương thức trong List để tìm kiếm một đối tượng được chỉ định. Tuy nhiên, các phương thức này có thể thực hiện các tìm kiếm tuyến tính tốn kém.

List cũng bao gồm hai phương thức để chèn và loại bỏ nhiều phần tử tùy ý điểm trong danh sách.

Lớp LinkedList thực thi interface List. Một mảng lưu trữ các đối tượng trong các vị trí bộ nhớ liên tiếp, trong khi danh sách được liên kết lưu trữ đối tượng dưới dạng một liên kết riêng biệt. Nó cung cấp cấu trúc dữ liệu danh sách liên kết. Danh sách liên kết là danh sách các đối tượng có liên kết đến đối tượng tiếp theo. Thường có một phần tử dữ liệu được theo sau bởi một phần tử địa chỉ chứa địa chỉ của phần tử tiếp theo trong danh sách theo một trình tự. Mỗi mục như vậy được gọi là một nút.

Danh sách liên kết cho phép chèn và loại bỏ các nút ở bất kỳ vị trí nào trong danh sách, nhưng không cho phép truy cập ngẫu nhiên. Có một số loại danh sách liên kết khác nhau - danh sách liên kết đơn, danh sách liên kết đôi và danh sách liên kết vòng.

Java cung cấp lớp LinkedList trong gói java.util để triển khai danh sách được liên kết.

• LinkedList (): Hàm tạo LinkedList () tạo một danh sách được liên kết trống.
• LinkedList (Collection <? expand E> c): Phương thức khởi tạo LinkedList (Collection <? Expand E> c) tạo một danh sách được liên kết, chứa các phần tử của một tập hợp được chỉ định, theo thứ tự chúng được trả về bởi trình lặp của tập hợp.

Hình 1: hiển thị một danh sách liên kết.

Hình 1: LinkedList

Ví dụ 1 hiển thị việc tạo một thể hiện của lớp LinkedList.

Ví dụ 1:

LinkedList<String> lisObj = new LinkedList<List>();

Các phương thức của lớp LinkedList

Ngoài các phương thức được xác định interface List, các phương thức khác của lớp LinkedList như sau:

addFirst(E obj)

Phương thức này thêm đối tượng đã cho vào đầu danh sách.

Cú pháp:

public void addFirst(E obj)

addLast (E obj)

Phương thức này nối đối tượng đã cho vào cuối danh sách.

Cú pháp:

public Object addLast(E obj)

Cú pháp:

public E getFirst()

getLast()

Phương thức lấy phần tử cuối cùng từ danh sách.

Cú pháp:

public E getLast()

removeFirst()

Phương thức loại bỏ và trả về phần tử đầu tiên từ danh sách.

Cú pháp:

public E removeFirst()

removeLast()

Phương thức loại bỏ và trả về phần tử cuối cùng từ danh sách.

Cú pháp:

public E removeLast ()

Ví dụ 2 hiển thị việc sử dụng các phương thức của lớp LinkedList.

Ví dụ 2:

LinkedList<String> lisObj = new LinkedList<String>(); lisObj.add("John");
lisObj.add("Mary");
lisObj.add("Jack"); lisObj.add("Elvis");
lisObj.add("Martin");
System.out.println("Original content of the list: " + lisObj);
lisObj.removeFirst();
System.out.println("After removing content of the list: " + lisObj);

Trong mã, một đối tượng LinkedList đã được tạo và khởi tạo với các giá trị chuỗi. Tiếp theo, nội dung gốc của danh sách được hiển thị. Sau khi xóa một đối tượng khỏi danh sách, nội dung của danh sách lại được hiển thị.

AutoBoxing và Unboxing

Tính năng autoboxing và unboxing tự động hóa quá trình sử dụng giá trị nguyên thủy vào một collection. Lưu ý rằng các collection chỉ chứa các tham chiếu đối tượng. Vì vậy, các giá trị nguyên thủy, chẳng hạn như int từ Integer, phải được box vào lớp wrapper thích hợp. Nếu giá trị int là bắt buộc, giá trị Integer phải được unbox bằng phương thức intValue(). Tính năng autoboxing và unboxing giúp giảm bớt sự lộn xộn trong mã lệnh.