Cấu trúc dữ liệu danh sách liên kết trong Java

Các cấu trúc dữ liệu khác nhau được tạo cho các mục đích khác nhau. Bạn có thể biết về ArrayList (nếu vẫn chưa biết, chúng tôi khuyên bạn nên đọc về nó trước). Trong bài viết này, chúng ta sẽ tìm hiểu về LinkedList và nhận ra tập hợp này tốt cho việc gì. Nếu bạn xem nguồn mã lớp LinkedList Java 8 (hoặc phiên bản mới hơn của ngôn ngữ) (trên trang web của Oracle hoặc trong IDE của bạn, trong trường hợp IDEA: crtl+B trên tên lớp), bạn sẽ thấy khai báo tiếp theo:

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

Hiện tại, thông tin quan trọng nhất từ ​​mã là LinkedList thực hiện các giao diện List và Deque . Giao diện Danh sách giữ nguyên trình tự thêm mục và cho phép truy cập mục theo chỉ mục. Hàng đợi “thông thường” hỗ trợ thêm các phần tử vào cuối và trích xuất chúng từ đầu. Deque là hàng đợi hai chiều và nó hỗ trợ thêm và xóa các phần tử từ cả hai phía. Bạn có thể coi nó là sự kết hợp giữa ngăn xếp và hàng đợi. Vì vậy, LinkedList là một triển khai của hai điều này và nó cho phép chúng tôi tạo một hàng đợi hai chiều bao gồm bất kỳ đối tượng nào kể cả null. LinkedListlà một tập hợp các phần tử. Chúng ta có thể thấy nó trong mã nguồn của lớp, lần này hãy chú ý đến các trường:

transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

Mọi phần tử, chúng tôi thường gọi nó là Node , chứa một đối tượng và tham chiếu đến hai đối tượng lân cận — đối tượng trước và đối tượng tiếp theo. Do đó, nó không hiệu quả lắm về mặt sử dụng bộ nhớ. Vì LinkedList thực sự là một cấu trúc hai chiều, chúng ta có thể dễ dàng thêm hoặc bớt các phần tử từ cả hai phía.

LinkedList Constructor

Quay lại mã nguồn, chúng ta có thể phát hiện ra rằng LinkedList có hai hàm tạo

• LinkedList() không có tham số được sử dụng để tạo danh sách trống.
• >LinkedList(Collection<? extends E> c) dùng để tạo danh sách chứa các phần tử của bộ sưu tập đã chỉ định, theo thứ tự, chúng được trả về bởi bộ lặp của bộ sưu tập.

Tuyên bố LinkedList

Trên thực tế, một danh sách được liên kết (Java hoặc bất kỳ ngôn ngữ nào khác) bao gồm một chuỗi các nút. Mỗi nút được thiết kế để lưu trữ một đối tượng thuộc loại được xác định khi tạo. Vì vậy, để tạo LinkedList , mã Java là phần tiếp theo:

LinkedList<Integer> myList = new LinkedList<>();

Chúng tôi đã có một đối tượng để giữ một chuỗi các số nguyên và liên kết đến các hàng xóm. Tuy nhiên, nó trống rỗng vào lúc này.

Hoạt động chính của LinkedList

Như thường lệ, trong trường hợp Bộ sưu tập, bạn có thể đặt các phần tử vào LinkedList (đến cuối hoặc vào giữa), xóa khỏi đó và lấy phần tử theo chỉ mục. Vì vậy, đây là:

• add(E element) Nối phần tử đã chỉ định vào cuối danh sách này;
• add(int index, E element) Chèn phần tử vào chỉ số vị trí xác định ;
• get(int index) Trả về phần tử ở vị trí xác định trong danh sách này;
• remove(int index) Loại bỏ phần tử ở vị trí chỉ mục;
• remove(Object o) Xóa lần xuất hiện đầu tiên của ? o phần tử từ danh sách này nếu nó ở đó.
• remove() Lấy và loại bỏ phần tử đầu tiên của danh sách.

Triển khai danh sách liên kết trong Java, thêm và xóa các phần tử. Ví dụ

Hãy thử thực hành các thao tác này. Đầu tiên, triển khai Java LinkedList: tạo LinkedList gồm các chuỗi, thêm vào đó 3 phần tử. Sau đó loại bỏ một, sau đó thêm một ở giữa.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

Kết quả chạy chương trình này:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

Danh sách liên kết là một phần của khung Bộ sưu tập , bạn có thể sử dụng Iterator để xóa các phần tử, cũng như một trình lặp đặc biệt cho danh sách - ListIterator . Hơn nữa, các hoạt động với iterator cung cấp các lợi ích chính của lớp LinkedList : thực hiện tốt các thao tác chèn/xóa. Sử dụng Iterator, bạn có thể nhận được thời gian cố định cho chúng. Ở phần sau của bài viết này, chúng ta sẽ viết một ví dụ mã để so sánh ArrayList và LinkedList+Iterator

• Iterator.remove() loại bỏ phần tử cuối cùng được trả về bởi iterator này.
• ListIterator.add(E element) chèn một phần tử vào danh sách

Ví dụ về LinkedList trong Java: cách thức hoạt động của Iterator

Ở đây chúng tôi có một mã ví dụ Java LinkedList nhỏ , nơi chúng tôi thử thêm và xóa thông qua Iterator.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
 
       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);
 
   }
}

Kết quả chạy chương trình này:

linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

Các hoạt động danh sách liên kết Java khác :

• addFirst() , addLast() thêm phần tử vào đầu/cuối danh sách
• clear() xóa tất cả các phần tử khỏi danh sách
• chứa(Đối tượng o) trả về true nếu danh sách chứa phần tử o.
• indexOf(Object o) trả về chỉ mục của lần xuất hiện đầu tiên của phần tử o hoặc -1 nếu nó không có trong danh sách.
• set(int index, E element) thay thế phần tử ở vị trí chỉ mục bằng phần tử
• size() Trả về số lượng phần tử trong danh sách.
• toArray() trả về một mảng chứa tất cả các phần tử của danh sách từ phần tử đầu tiên đến phần tử cuối cùng.

BTW là một hàng đợi có hai kích thước, LinkedList trong Java có các hoạt động cụ thể của ngăn xếp:

• pop() bật một phần tử từ ngăn xếp (được biểu thị bằng danh sách)
• push(E e) đẩy một phần tử vào ngăn xếp (được biểu thị bằng danh sách này)

Cách đảo ngược LinkedList: ví dụ

Đây là một ví dụ nhỏ, một nhiệm vụ phổ biến nhưng dễ dàng cho người mới bắt đầu. Chúng tôi có một LinkedList và nên đảo ngược nó. Thuật toán đơn giản nhất là đi qua LinkedList theo thứ tự ngược lại và đặt mọi phần tử vào phần tử mới. Tuy nhiên, có thể bạn sẽ tìm thấy một cách tốt hơn? Đây là mã của chương trình java danh sách liên kết ngược:

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

Kết quả:

[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

LinkedList vs ArrayList: khi nào nên sử dụng cái đầu tiên

Cả LinkedList và ArrayList đều là các triển khai của giao diện Danh sách . LinkedList thực hiện nó với một danh sách liên kết kép. ArrayList thực hiện nó bằng cách sử dụng một mảng thay đổi kích thước động. Như bạn đã biết, mỗi nút của LinkedList chứa các Đối tượng và hai tham chiếu đến các nút lân cận. Điều đó có nghĩa là chi phí bộ nhớ bổ sung để lưu trữ các tham chiếu giữa các phần tử trong trường hợp Java LinkedList . ArrayList thực hiện nó với một mảng thay đổi kích thước động. Một số hoạt động của LinkedList và ArrayList trông giống nhau, nhưng chúng hoạt động theo một cách khác. Trong ArrayListtrường hợp, bạn thao tác với các mảng bên trong, trong LinkedList — với các tham chiếu. ArrayList là cách triển khai Danh sách phổ biến nhất . Bạn chắc chắn nên sử dụng ArrayList khi quyền truy cập chỉ mục là ưu tiên vì các hoạt động này được thực hiện trong thời gian không đổi. Tính trung bình cộng vào cuối danh sách cũng được thực hiện trong thời gian cố định. Hơn nữa, ArrayList không có chi phí bổ sung để lưu trữ một loạt các phần tử. Bạn có thể coi là Nhược điểm tốc độ chèn và xóa các thao tác khi nó được thực hiện không ở cuối danh sách. LinkedListhữu ích hơn trong trường hợp thực hiện thao tác chèn và xóa theo một số cách: nếu bạn sử dụng trình vòng lặp, nó sẽ xảy ra trong thời gian không đổi. Hoạt động truy cập theo chỉ mục được thực hiện bằng cách tìm kiếm từ đầu đến cuối (tùy theo cái nào gần hơn) đến phần tử mong muốn. Tuy nhiên, đừng quên chi phí bổ sung để lưu trữ các tham chiếu giữa các phần tử. Vì vậy, ở đây các hoạt động LinkedList và ArrayList tiêu chuẩn với thời gian chạy thuật toán. N đề cập đến số lượng các mặt hàng đã có trong danh sách. O(N) có nghĩa là trong trường hợp xấu nhất, chúng ta nên “đi bộ” qua toàn bộ danh sách cho đến khi tìm thấy vị trí cần thiết, ví dụ, để chèn phần tử mới vào danh sách. Ô(1)có nghĩa là hoạt động xảy ra trong thời gian không đổi, độc lập với số lượng mục.

Độ phức tạp thời gian của LinkedList

Độ phức tạp thời gian của ArrayList

Khi nào nên sử dụng LinkedList: Ví dụ

Chắc chắn, ArrayList là cách triển khai Danh sách phổ biến nhất . Tuy nhiên, bạn có thể gặp các tình huống khi các thao tác thêm/xóa được yêu cầu quá thường xuyên. Trong trường hợp đó, tất cả LinkedList cùng với Iterator có thể hữu ích. Đây là một ví dụ. Chúng ta có một danh sách dài và chúng ta nên xóa mọi phần tử khỏi danh sách này. Hãy thực hiện nhiệm vụ này với ArrayList và LinkedList + Iterator . Chúng tôi so sánh thời gian của mọi thao tác và in ra bảng điều khiển. Đây là mã:

import java.util.*;
import java.util.function.BiPredicate;
 
public class ListTest2 {
 
   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());
 
       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }
 
   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);
 
           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }
 
   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
 
   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

Kết quả cho ArrayList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

Kết quả cho LinkedList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

Như bạn có thể thấy trong trường hợp này LinkedList hiệu quả hơn nhiều. Hãy Trung thực. Trong phát triển phần mềm thực tế, việc sử dụng LinkedList là một loại sự kiện hiếm gặp. Tuy nhiên, một chuyên gia nên biết về sự tồn tại của cấu trúc dữ liệu này và những lợi thế của nó. Nếu trong mã thực, LinkedList là một vị khách hiếm hoi, thì trên các cuộc phỏng vấn của Java Junior, nó rất phổ biến. Chưa hết, đây là những gì Joshua Bloch đã viết về LinkedList :

AddOn: Danh sách liên kết đơn Java

Không có Danh sách liên kết đơn lẻ trong Bộ sưu tập cổ điển trong Java, Danh sách liên kết đơn lẻ là cấu trúc trong đó mọi nút chứa Đối tượng và tham chiếu đến Nút tiếp theo, nhưng không phải cho nút trước đó. Danh sách liên kết trong Java là liên kết hai, nhưng không ai can thiệp vào việc bạn tạo Cấu trúc dữ liệu của riêng mình, chẳng hạn như Danh sách liên kết đơn lẻ, mã>. Dưới đây là một số bước để giải quyết các nhiệm vụ này:

1. Tạo một lớp Node với hai thuộc tính, dữ liệu và tiếp theo. Tiếp theo là một tham chiếu đến nút tiếp theo.
2. Tạo lớp FirstLast với hai thuộc tính là head và tail.
3. Tạo một phương thức add() để thêm một nút mới vào danh sách. Trước tiên hãy kiểm tra xem danh sách có trống không ( head == null ). Nếu vậy, đầu và đuôi tham chiếu đến nút mới. Nếu danh sách không trống, nút mới sẽ được thêm vào cuối, do đó thuộc tính tiếp theo của phần đuôi đề cập đến nút được thêm vào và nút mới trở thành phần đuôi của danh sách.

Nhân tiện, bạn cũng có thể thử tạo LinkedList của riêng mình như một bài tập. Chúc may mắn trong học tập của bạn.