Danh sách liên kết Java

CHÀO! Tất cả các bài học mới nhất đã được dành cho ArrayList . Cấu trúc dữ liệu này rất thuận tiện và hữu ích. Nó có thể xử lý nhiều nhiệm vụ. Nhưng Java có rất nhiều cấu trúc dữ liệu khác. Tại sao? Trên hết, vì phạm vi nhiệm vụ là rất lớn và cấu trúc dữ liệu hiệu quả nhất là khác nhau đối với các nhiệm vụ khác nhau. Hôm nay chúng ta sẽ gặp một cấu trúc mới: Java LinkedList , một danh sách liên kết kép.

Hãy xem cách nó được tổ chức, tại sao nó được gọi là liên kết kép, nó khác với ArrayList như thế nào . Các phần tử trong Danh sách liên kết Java thực sự là các liên kết trong một chuỗi đơn. Ngoài dữ liệu, mỗi phần tử lưu trữ các tham chiếu đến các phần tử trước đó và tiếp theo. Những tham chiếu này cho phép bạn di chuyển từ phần tử này sang phần tử khác. Đây là cách bạn tạo một cái:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}

Đầu ra: [Xin chào thế giới! Tên tôi là Earl, tôi yêu Java, tôi sống ở Canada] Đây là danh sách của chúng ta: LinkedList - 2

Hãy xem cách thêm một phần tử mới. Điều này được thực hiện bằng cách sử dụng phương thức add() .

earlBio.add(str2);

Tại điểm trong mã, danh sách của chúng tôi bao gồm một phần tử: Chuỗi str1 . Hãy xem điều gì xảy ra tiếp theo trong hình: LinkedList - 3

Kết quả là, str2 và str1 được liên kết thông qua các liên kết tiếp theo và trước đó được lưu trữ trong các nút này của danh sách: LinkedList - 4

Bây giờ bạn đã hiểu ý chính của danh sách liên kết đôi. Chuỗi liên kết này chính xác là thứ làm cho các phần tử LinkedList trở thành một danh sách duy nhất. Không giống như ArrayList , LinkedList không có mảng hoặc bất kỳ thứ gì giống như mảng bên trong. Bất kỳ (tốt, hầu hết) hoạt động với ArrayList đều hoạt động với mảng bên trong. Mọi công việc với Java LinkedListsôi xuống để thay đổi liên kết. Điều này có thể được nhìn thấy rất rõ ràng bằng cách thêm một phần tử vào giữa danh sách:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}

Như bạn có thể thấy, phương thức add() quá tải cho phép bạn chỉ định một chỉ mục cụ thể cho một mục mới. Trong trường hợp này, chúng tôi muốn thêm Chuỗi str2 vào giữa str1 và str3 . Đây là những gì sẽ xảy ra trong nội bộ: LinkedList - 5

Sau khi thay đổi các liên kết nội bộ, str2 đã được thêm vào danh sách thành công: LinkedList - 6

Bây giờ cả 3 phần tử đã được kết nối. Bạn có thể di chuyển qua liên kết tiếp theo từ phần tử đầu tiên trên chuỗi đến phần tử cuối cùng và ngược lại. Vì vậy, chúng tôi khá thoải mái với việc chèn, nhưng còn việc xóa các phần tử thì sao? Nguyên tắc hoàn toàn giống nhau. Chúng tôi chỉ cập nhật các liên kết trong hai phần tử "bên trái và bên phải" của phần tử bị xóa:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       earlBio.remove(1);
       System.out.println(earlBio);
   }
}

Đây là điều sẽ xảy ra nếu chúng ta xóa mục có chỉ số 1 (nó ở giữa danh sách): LinkedList - 7

Sau khi cập nhật các liên kết, chúng ta sẽ nhận được kết quả mong muốn: LinkedList - 8

Không giống như thao tác xóa trong ArrayList , ở đây không cần phải thay đổi hoặc thực hiện các phần tử mảng bất cứ thứ gì thuộc loại này. Chúng tôi chỉ cập nhật các liên kết cho str1 và str3 . Bây giờ chúng trỏ đến nhau và str2 đã " loại bỏ " khỏi chuỗi liên kết và không còn là một phần của danh sách.

Tổng quan về các phương pháp

LinkedList có rất nhiều phương thức chung với ArrayList . Ví dụ: cả hai lớp đều có các phương thức như add() , remove() , indexOf() , clear() , contains() (cho biết một mục có trong danh sách hay không), set() (thay thế một phần tử hiện có) và kích thước() . Mặc dù nhiều trong số chúng hoạt động khác nhau trong nội bộ (như chúng tôi đã tìm thấy với add() và remove() ), kết quả cuối cùng là như nhau. Tuy nhiên, LinkedList có các phương thức riêng biệt để làm việc với phần đầu và phần cuối của danh sách, mà ArrayList không có:

addFirst() , addLast() : Các phương thức này để thêm phần tử vào đầu/cuối danh sách

public class Car {

   String model;

   public Car(String model) {
       this.model = model;
   }

   public static void main(String[] args) {
       LinkedList<Car> cars = new LinkedList<>();
       Car ferrari = new Car("Ferrari 360 Spider");
       Car bugatti = new Car("Bugatti Veyron");
       Car lambo = new Car("Lamborghini Diablo");
       Car ford = new Car("Ford Mondeo");
       Car fiat = new Car("Fiat Ducato");

       cars.add(ferrari);
       cars.add(bugatti);
       cars.add(lambo);
       System.out.println(cars);

       cars.addFirst(ford);
       cars.addLast(fiat);
       System.out.println(cars);
   }

   @Override
   public String toString() {
       return "Car{" +
               "model='" + model + '\'' +
               '}';
   }
}

Đầu ra: [Xe hơi{model='Ferrari 360 Spider'}, Xe hơi{model='Bugatti Veyron'}, Xe hơi{model='Lamborghini Diablo'}] [Xe hơi{model='Ford Mondeo'}, Xe hơi{model=' Ferrari 360 Spider'}, Xe hơi{model='Bugatti Veyron'}, Xe hơi{model='Lamborghini Diablo'}, Xe hơi{model='Fiat Ducato'}] Chúng tôi kết thúc với "Ford" ở đầu danh sách, và "Fiat" ở cuối.

peekFirst() , peekLast() : Các phương thức trả về phần tử đầu tiên/cuối cùng trong danh sách. Họ trả về null nếu danh sách trống.

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.peekFirst());
   System.out.println(cars.peekLast());
}

Đầu ra: Ô tô{model='Ferrari 360 Spider'} Ô tô{model='Lamborghini Diablo'}

pollFirst() , pollLast() : Các phương thức này trả về phần tử đầu tiên/cuối cùng trong danh sách và xóa nó khỏi danh sách. Họ trả về null nếu danh sách trống

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.pollFirst());
   System.out.println(cars.pollLast());

   System.out.println ("What's on the list?");
   System.out.println(cars);
}

Đầu ra: Ô tô{model='Ferrari 360 Spider'} Ô tô{model='Lamborghini Diablo'} Còn lại gì trong danh sách? [Xe hơi{model='Bugatti Veyron'}]

toArray() : Phương thức này trả về một mảng chứa các mục trong danh sách

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   Car[] carsArray = cars.toArray(new Car[3]);
   System.out.println(Arrays.toString(carsArray));
}

Đầu ra: [Xe hơi{model='Ferrari 360 Spider'}, Xe hơi{model='Bugatti Veyron'}, Xe hơi{model='Lamborghini Diablo'}] Bây giờ chúng ta đã biết cách thức hoạt động của LinkedList và cách tổ chức của nó khác với ArrayList . Lợi ích của việc sử dụng LinkedList là gì ? Hơn hết, chúng tôi được lợi khi làm việc ở giữa danh sách. Thao tác chèn và xóa ở giữa LinkedList đơn giản hơn nhiều so với trong ArrayList . Chúng tôi chỉ cần cập nhật các liên kết của các phần tử lân cận và phần tử không mong muốn "rơi ra" khỏi chuỗi liên kết. Nhưng trong một ArrayList , chúng ta phải

kiểm tra xem có đủ dung lượng không (khi chèn)
nếu không thì ta tạo mảng mới và copy dữ liệu vào đó (khi chèn)
chúng tôi xóa/chèn phần tử và di chuyển tất cả các phần tử khác sang phải/trái (tùy thuộc vào loại hoạt động). Và mức độ phức tạp của quá trình này phụ thuộc nhiều vào kích thước của danh sách. Sao chép/di chuyển 10 phần tử là một việc, và thực hiện tương tự với một triệu phần tử là một việc khác.

Nói cách khác, nếu thao tác chèn/xóa ở giữa danh sách là phổ biến nhất trong chương trình của bạn, thì LinkedList sẽ nhanh hơn ArrayList .

về lý thuyết

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new LinkedList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Đầu ra: Thời gian do LinkedList thực hiện (tính bằng mili giây) = 1873

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new ArrayList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Kết quả: Thời gian ArrayList thực hiện (tính bằng mili giây) = 181 Điều đó thật bất ngờ! Chúng tôi đã thực hiện một thao tác trong đó LinkedList sẽ hiệu quả hơn nhiều: chèn 100 mục vào giữa danh sách. Và danh sách của chúng tôi rất lớn: 5.000.000 phần tử. ArrayList đã phải thay đổi vài triệu mục với mỗi lần chèn! Làm thế nào nó giành chiến thắng? Đầu tiên, thời gian cần thiết để ArrayList truy cập các phần tử là cố định (không đổi). Khi bạn viết

list.add(2_000_000, new Integer(Integer.MAX_VALUE));

thì ArrayList [2_000_000] là một địa chỉ bộ nhớ cụ thể (xét cho cùng, danh sách có một mảng bên trong). Tuy nhiên, LinkedList không có mảng. Nó sẽ tìm kiếm phần tử số 2_000_000 dọc theo chuỗi liên kết. Đối với LinkedList, đây không phải là một địa chỉ bộ nhớ, mà là một liên kết vẫn cần đạt được: fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next. next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next……… Kết quả là trong mỗi lần chèn (xóa) vào giữa danh sách , ArrayList đã biết chính xác địa chỉ bộ nhớ cần truy cập, nhưng LinkedList vẫn cần "đến đó". Thứ hai, đó là cấu trúc của ArrayListchính nó. Một hàm bên trong đặc biệt ( System.arrayCopy() ) mở rộng mảng bên trong, đồng thời sao chép và dịch chuyển tất cả các phần tử. Nó rất nhanh, bởi vì nó được tối ưu hóa cho công việc cụ thể này. Nhưng khi bạn không phải "đến" một chỉ mục cụ thể, LinkedList là người chiến thắng. Giả sử chúng ta chèn vào đầu danh sách. Hãy thử chèn một triệu phần tử vào đó:

public class Main {

   public static void main(String[] args) {
       getTimeMsOfInsert(new ArrayList());
       getTimeMsOfInsert(new LinkedList());
   }

   public static long getTimeMsOfInsert(List list) {
       // Write your code here
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); // Calculate the difference
       System.out.println("The result in milliseconds: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}

Đầu ra: Kết quả tính bằng mili giây: 43448 Kết quả tính bằng mili giây: 107 Bây giờ chúng ta nhận được một kết quả hoàn toàn khác! ArrayList mất hơn 43 giây để chèn một triệu mục vào đầu danh sách, trong khi LinkedList làm được điều đó trong 0,1 giây! LinkedList được hưởng lợi ở đây, bởi vì nó không phải chạy qua chuỗi liên kết đến giữa danh sách mỗi lần. Nó ngay lập tức tìm thấy chỉ mục cần thiết ở đầu danh sách, vì vậy thuật toán khác biệt đã là một lợi thế. :) Trên thực tế, cuộc thảo luận " ArrayList so với LinkedList " rất phổ biến và chúng tôi sẽ không đi sâu vào vấn đề này ở cấp độ hiện tại. Điều chính mà bạn cần nhớ là đây:

Không phải tất cả các lợi thế lý thuyết của bất kỳ bộ sưu tập cụ thể nào luôn hoạt động trong thực tế (chúng tôi đã thấy điều này với ví dụ liên quan đến giữa danh sách)
Đừng áp dụng một quan điểm cực đoan khi nói đến việc chọn một bộ sưu tập (" ArrayList luôn nhanh hơn. Hãy sử dụng nó và bạn không thể sai. Không ai đã sử dụng LinkedList trong một thời gian dài").

Mặc dù ngay cả tác giả của LinkedList , Joshua Bloch, cũng nói rằng đây là trường hợp. :) Tuy nhiên, quan điểm này còn lâu mới đúng 100% và chúng tôi đã tự thuyết phục mình về điều này. Trong ví dụ trước của chúng tôi, LinkedList nhanh hơn 400 (!) lần. Một điều nữa là thực sự có rất ít tình huống mà LinkedList là sự lựa chọn tốt nhất. Nhưng chúng tồn tại và vào đúng thời điểm LinkedListcó thể thưởng cho bạn một cách hậu hĩnh. Đừng quên những gì chúng ta đã nói ở đầu bài học: các cấu trúc dữ liệu hiệu quả nhất sẽ khác nhau đối với các tác vụ khác nhau. Không thể chắc chắn 100% cấu trúc dữ liệu nào sẽ tốt nhất cho đến khi bạn biết tất cả các điều kiện của nhiệm vụ của mình. Bạn sẽ biết thêm về các bộ sưu tập này sau, điều này sẽ giúp bạn lựa chọn dễ dàng hơn. Nhưng tùy chọn đơn giản và hiệu quả nhất luôn giống nhau: thử cả hai trên dữ liệu thực tế được sử dụng trong chương trình của bạn. Sau đó, bạn sẽ có thể tự mình xem cả hai loại danh sách hoạt động như thế nào và bạn chắc chắn sẽ không mắc sai lầm. :) Để củng cố những gì bạn đã học, chúng tôi khuyên bạn nên xem một video bài học từ Khóa học Java của chúng tôi

Đọc thêm:
Danh sách liên kết Cấu trúc dữ liệu Java