Trong hướng dẫn này, chúng ta sẽ tìm hiểu chi tiết về Java LinkedList với sự trợ giúp của các ví dụ.
Các LinkedListlớp học của khuôn khổ bộ sưu tập Java cung cấp các chức năng của cấu trúc dữ liệu danh sách liên kết (gấp đôi linkedlist).
Java Double LinkedList
Mỗi phần tử trong danh sách liên kết được gọi là một nút . Nó bao gồm 3 trường:
- Prev - lưu trữ địa chỉ của phần tử trước đó trong danh sách. Nó
nulldành cho phần tử đầu tiên - Tiếp theo - lưu trữ địa chỉ của phần tử tiếp theo trong danh sách. Nó
nulldành cho phần tử cuối cùng - Dữ liệu - lưu trữ dữ liệu thực tế
Tạo danh sách liên kết Java
Đây là cách chúng ta có thể tạo danh sách liên kết trong Java:
LinkedList linkedList = new LinkedList();
Ở đây, Loại cho biết loại danh sách được liên kết. Ví dụ,
// create Integer type linked list LinkedList linkedList = new LinkedList(); // create String type linked list LinkedList linkedList = new LinkedList();
Ví dụ: Tạo LinkedList trong Java
import java.util.LinkedList; class Main ( public static void main(String() args)( // create linkedlist LinkedList animals = new LinkedList(); // Add elements to LinkedList animals.add("Dog"); animals.add("Cat"); animals.add("Cow"); System.out.println("LinkedList: " + animals); ) )
Đầu ra
LinkedList: (Chó, Mèo, Bò)
Trong ví dụ trên, chúng tôi đã tạo một LinkedListcon vật được đặt tên.
Ở đây, chúng tôi đã sử dụng add()phương pháp để thêm các phần tử vào LinkedList. Chúng ta sẽ tìm hiểu thêm về add()phương pháp sau trong hướng dẫn này.
Hoạt động của một Java LinkedList
Các phần tử trong danh sách liên kết không được lưu trữ theo trình tự. Thay vào đó, chúng được phân tán và kết nối thông qua các liên kết ( Trước và Tiếp theo ).
Triển khai Java LinkedList
Ở đây chúng tôi có 3 yếu tố trong một danh sách liên kết.
- Dog - nó là phần tử đầu tiên chứa null làm địa chỉ trước và địa chỉ của Cat là địa chỉ tiếp theo
- Cat - nó là phần tử thứ hai chứa địa chỉ của Dog là địa chỉ trước và địa chỉ của Cow là địa chỉ tiếp theo
- Cow - nó là phần tử cuối cùng giữ địa chỉ của Cat là địa chỉ trước đó và null là phần tử tiếp theo
Để tìm hiểu thêm, hãy truy cập Cấu trúc dữ liệu LinkedList.
Các phương thức của Java LinkedList
LinkedListcung cấp các phương pháp khác nhau cho phép chúng tôi thực hiện các hoạt động khác nhau trong danh sách được liên kết. Chúng ta sẽ xem xét bốn Toán tử LinkedList thường được sử dụng trong hướng dẫn này:
- Thêm các yếu tố
- Truy cập các phần tử
- Thay đổi các yếu tố
- Loại bỏ các yếu tố
1. Thêm các phần tử vào LinkedList
Chúng ta có thể sử dụng add()phương thức để thêm một phần tử (nút) vào cuối LinkedList. Ví dụ,
import java.util.LinkedList; class Main ( public static void main(String() args)( // create linkedlist LinkedList animals = new LinkedList(); // add() method without the index parameter animals.add("Dog"); animals.add("Cat"); animals.add("Cow"); System.out.println("LinkedList: " + animals); // add() method with the index parameter animals.add(1, "Horse"); System.out.println("Updated LinkedList: " + animals); ) )
Đầu ra
LinkedList: (Dog, Cat, Cow) Đã cập nhật LinkedList: (Dog, Horse, Cat, Cow)
Trong ví dụ trên, chúng tôi đã tạo một LinkedList có tên động vật. Ở đây, chúng tôi đã sử dụng add()phương pháp để thêm các yếu tố cho động vật.
Lưu ý tuyên bố,
animals.add(1, "Horse");
Ở đây, chúng tôi đã sử dụng tham số số chỉ mục . Nó là một tham số tùy chọn chỉ định vị trí mà phần tử mới được thêm vào.
Để tìm hiểu thêm về cách thêm phần tử vào LinkedList, hãy truy cập chương trình Java để thêm phần tử vào LinkedList.
2. Truy cập các phần tử LinkedList
Các get()phương pháp của lớp LinkedList được sử dụng để truy cập vào một phần tử từ LinkedList. Ví dụ,
import java.util.LinkedList; class Main ( public static void main(String() args) ( LinkedList languages = new LinkedList(); // add elements in the linked list languages.add("Python"); languages.add("Java"); languages.add("JavaScript"); System.out.println("LinkedList: " + languages); // get the element from the linked list String str = languages.get(1); System.out.print("Element at index 1: " + str); ) )
Đầu ra
LinkedList: (Python, Java, JavaScript) Phần tử ở chỉ mục 1: Java
Trong ví dụ trên, chúng ta đã sử dụng get()phương thức với tham số 1 . Ở đây, phương thức trả về phần tử ở chỉ mục 1 .
Chúng tôi cũng có thể yếu tố tiếp cận của LinkedList sử dụng iterator()và listIterator()phương pháp. Để tìm hiểu thêm, hãy truy cập chương trình Java để truy cập các phần tử của LinkedList.
3. Thay đổi các phần tử của một LinkedList
Các set()phương pháp của LinkedListlớp được sử dụng để thay đổi các yếu tố của LinkedList. Ví dụ,
import java.util.LinkedList; class Main ( public static void main(String() args) ( LinkedList languages = new LinkedList(); // add elements in the linked list languages.add("Java"); languages.add("Python"); languages.add("JavaScript"); languages.add("Java"); System.out.println("LinkedList: " + languages); // change elements at index 3 languages.set(3, "Kotlin"); System.out.println("Updated LinkedList: " + languages); ) )
Đầu ra
LinkedList: (Java, Python, JavaScript, Java) LinkedList đã cập nhật: (Java, Python, JavaScript, Kotlin)
Trong ví dụ trên, chúng tôi đã tạo một ngôn ngữ có tên LinkedList. Lưu ý dòng,
languages.set(3, "Kotlin");
Ở đây, set()phương thức thay đổi phần tử ở chỉ mục 3 thành Kotlin.
4. Xóa phần tử khỏi LinkedList
The remove() method of the LinkedList class is used to remove an element from the LinkedList. For example,
import java.util.LinkedList; class Main ( public static void main(String() args) ( LinkedList languages = new LinkedList(); // add elements in LinkedList languages.add("Java"); languages.add("Python"); languages.add("JavaScript"); languages.add("Kotlin"); System.out.println("LinkedList: " + languages); // remove elements from index 1 String str = languages.remove(1); System.out.println("Removed Element: " + str); System.out.println("Updated LinkedList: " + languages); ) )
Output
LinkedList: (Java, Python, JavaScript, Kotlin) Removed Element: Python New LinkedList: (Java, JavaScript, Kotlin)
Here, the remove() method takes the index number as the parameter. And, removes the element specified by the index number.
To learn more about removing elements from the linkedlist, visit the Java program to remove elements from LinkedList…
Other Methods
| Methods | Description |
|---|---|
contains() | checks if the LinkedList contains the element |
indexOf() | returns the index of the first occurrence of the element |
lastIndexOf() | returns the index of the last occurrence of the element |
clear() | removes all the elements of the LinkedList |
iterator() | returns an iterator to iterate over LinkedList |
LinkedList as Deque and Queue
Since the LinkedList class also implements the Queue and the Deque interface, it can implement methods of these interfaces as well. Here are some of the commonly used methods:
| Methods | Descriptions |
|---|---|
addFirst() | adds the specified element at the beginning of the linked list |
addLast() | adds the specified element at the end of the linked list |
getFirst() | returns the first element |
getLast() | returns the last element |
removeFirst() | removes the first element |
removeLast() | removes the last element |
peek() | returns the first element (head) of the linked list |
poll() | returns and removes the first element from the linked list |
offer() | adds the specified element at the end of the linked list |
Example: Java LinkedList as Queue
import java.util.LinkedList; import java.util.Queue; class Main ( public static void main(String() args) ( Queue languages = new LinkedList(); // add elements languages.add("Python"); languages.add("Java"); languages.add("C"); System.out.println("LinkedList: " + languages); // access the first element String str1 = languages.peek(); System.out.println("Accessed Element: " + str1); // access and remove the first element String str2 = languages.poll(); System.out.println("Removed Element: " + str2); System.out.println("LinkedList after poll(): " + languages); // add element at the end languages.offer("Swift"); System.out.println("LinkedList after offer(): " + languages); ) )
Output
LinkedList: (Python, Java, C) Accessed Element: Python Removed Element: Python LinkedList after poll(): (Java, C) LinkedList after offer(): (Java, C, Swift)
Example: LinkedList as Deque
import java.util.LinkedList; import java.util.Deque; class Main ( public static void main(String() args)( Deque animals = new LinkedList(); // add element at the beginning animals.add("Cow"); System.out.println("LinkedList: " + animals); animals.addFirst("Dog"); System.out.println("LinkedList after addFirst(): " + animals); // add elements at the end animals.addLast("Zebra"); System.out.println("LinkedList after addLast(): " + animals); // remove the first element animals.removeFirst(); System.out.println("LinkedList after removeFirst(): " + animals); // remove the last element animals.removeLast(); System.out.println("LinkedList after removeLast(): " + animals); ) )
Output
LinkedList: (Cow) LinkedList after addFirst(): (Dog, Cow) LinkedList after addLast(): (Dog, Cow, Zebra) LinkedList after removeFirst(): (Cow, Zebra) LinkedList after removeLast(): (Cow)
Iterating through LinkedList
We can use the Java for-each loop to iterate through LinkedList. For example,
import java.util.LinkedList; class Main ( public static void main(String() args) ( // Creating a linked list LinkedList animals = new LinkedList(); animals.add("Cow"); animals.add("Cat"); animals.add("Dog"); System.out.println("LinkedList: " + animals); // Using forEach loop System.out.println("Accessing linked list elements:"); for(String animal: animals) ( System.out.print(animal); System.out.print(", "); ) ) )
Output
LinkedList: (Cow, Cat, Dog) Accessing linked list elements: Cow, Cat, Dog,
LinkedList Vs. ArrayList
Both the Java ArrayList and LinkedList implements the List interface of the Collections framework. However, there exists some difference between them.
| LinkedList | ArrayList |
|---|---|
Implements List, Queue, and Deque interfaces. | Implements List interface. |
| Stores 3 values (previous address, data, and next address) in a single position. | Lưu trữ một giá trị ở một vị trí duy nhất. |
| Cung cấp triển khai danh sách được liên kết kép. | Cung cấp triển khai mảng có thể thay đổi kích thước. |
Bất cứ khi nào một phần tử được thêm vào prevvà nextđịa chỉ được thay đổi. | Bất cứ khi nào một phần tử được thêm vào, tất cả các phần tử sau vị trí đó sẽ được dịch chuyển. |
| Để truy cập một phần tử, chúng ta cần lặp lại từ đầu đến phần tử. | Có thể truy cập ngẫu nhiên các phần tử bằng cách sử dụng chỉ mục. |
Lưu ý : Chúng tôi cũng có thể tạo một LinkedList bằng cách sử dụng các giao diện trong Java. Ví dụ,
// create linkedlist using List List animals1 = new LinkedList(); // creating linkedlist using Queue Queue animals2 = new LinkedList(); // creating linkedlist using Deque Deque animals3 = new LinkedList();
Ở đây, nếu LinkedList được tạo bằng một giao diện, thì chúng ta không thể sử dụng các phương pháp được cung cấp bởi các giao diện khác. Nghĩa là, animal1 không thể sử dụng các phương thức dành riêng cho Queuevà các Dequegiao diện.
