Danh sách liên kết trong Java

Xin chào! Tất cả các bài giảng gần đây đều được dành để nghiên cứu danh sách ArrayList . Cấu trúc dữ liệu này rất thuận tiện và cho phép bạn giải quyết nhiều vấn đề. Tuy nhiên, Java có nhiều cấu trúc dữ liệu khác. Tại sao? Trước hết, vì phạm vi của các nhiệm vụ hiện có rất rộng và đối với các nhiệm vụ khác nhau, các cấu trúc dữ liệu khác nhau sẽ hiệu quả nhất . Hôm nay chúng ta sẽ làm quen với cấu trúc mới - danh sách liên kết đôi LinkedList . Hãy cùng tìm hiểu xem nó hoạt động như thế nào, tại sao nó được gọi là kết nối kép và nó khác với ArrayList như thế nào . Trong LinkedList, các phần tử thực sự là các liên kết trong một chuỗi. Mỗi phần tử, ngoài dữ liệu mà nó lưu trữ, còn có một liên kết đến phần tử trước và phần tử tiếp theo . Các liên kết này cho phép bạn di chuyển từ phần tử này sang phần tử khác. Nó được tạo ra như thế này:

public class Main {

   public static void main(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 Moscow");

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

       System.out.println(earlBio);

   }
}

Phần kết luận:

[Hello World! My name is Earl, I love Java, I live in Moscow]

Cấu trúc danh sách của chúng ta sẽ như thế này: Hãy xem cách thêm một phần tử mới. Việc này được thực hiện bằng cách sử dụng add().

earlBio.add(str2);

Tại thời điểm dòng mã này, 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: Kết quả là str2, và str1được kết nối thông qua các liên kết được lưu trữ trong chúng nextvà previous: Bây giờ bạn nên hiểu ý chính của một danh sách liên kết đôi. Các phần tử LinkedListlà một danh sách duy nhất nhờ vào chuỗi liên kết này. Không có mảng bên trong LinkedList, như in ArrayList, hoặc bất cứ thứ gì tương tự. Tất cả công việc với ArrayList (nói chung) đều bắt nguồn từ việc làm việc với mảng bên trong. Tất cả công việc LinkedListđều liên quan đến việc thay đổi liên kết. Điều này được thấy rất rõ 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(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 Moscow");

       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 nạp chồng add()cho phép bạn chỉ định một chỉ mục cụ thể cho phần tử mới. Trong trường hợp này, chúng tôi muốn thêm một dòng str2giữa str1và str3. Đây là những gì sẽ xảy ra bên trong: Và do thay đổi các liên kết nội bộ, phần tử str2đã được thêm thành công vào danh sách: Bây giờ cả 3 phần tử đều được liên kết. Từ phần tử đầu tiên dọc theo chuỗi, nextbạn có thể đi đến phần tử cuối cùng và quay lại. Chúng ta ít nhiều đã tìm ra cách chèn, nhưng còn việc xóa các phần tử thì sao? Nguyên lý hoạt động là như nhau. Chúng tôi chỉ đơn giản là xác định lại các liên kết của hai phần tử “ở hai bên” của phần tử bị loại bỏ:

public class Main {

   public static void main(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 Moscow");

       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 phần tử có chỉ mục 1 (nó nằm ở giữa danh sách): Sau khi xác định lại các liên kết, chúng ta nhận được kết quả mong muốn: Không giống như xóa, ArrayListkhông có sự thay đổi nào của các phần tử mảng và những thứ tương tự. Chúng tôi chỉ đơn giản là xác định lại các tham chiếu của các phần tử str1và str3. Lúc này chúng chỉ vào nhau, và đối tượng đó str2đã “bỏ” khỏi chuỗi liên kết này và không còn nằm trong danh sách nữa.

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

Nó LinkedListcó nhiều điểm tương đồng với ArrayListcác phương pháp. Ví dụ: các phương thức như add(), remove(), indexOf(), clear()( contains()là phần tử có trong danh sách), set()(chèn phần tử có thay thế) size()đều có trong cả hai lớp. Mặc dù (như chúng ta đã thấy trong ví dụ add()và remove()) nhiều trong số chúng hoạt động nội bộ khác nhau, nhưng cuối cùng thì chúng cũng làm điều tương tự. Tuy nhiên, nó LinkedListcó 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, những phương thức này không có trong ArrayList:

• addFirst(), addLast(): phương thức 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 + '\'' +
               '}';
   }
}

Phần kết luận:

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]
[Car{model='Ford Mondeo'}, Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}]

Kết quả là Ford đứng đầu danh sách và Fiat đứng cuối.

• peekFirst(), peekLast(): trả về phần tử đầu tiên/cuối cùng của danh sách. Trả về nullnế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());
}

Phần kết luận:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}

• pollFirst(), pollLast(): trả về phần tử đầu tiên/cuối cùng của danh sách và xóa nó khỏi danh sách . Trả về nullnế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 left on the list?");
   System.out.println(cars);
}

Phần kết luận:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
What осталось в списке?
[Car{model='Bugatti Veyron'}]

• toArray(): trả về một mảng các phần tử 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));
}

Phần kết luận:

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]

Bây giờ chúng ta biết nó hoạt động như thế nào LinkedListvà nó khác với ArrayList. Lợi ích của việc sử dụng là gì LinkedList? Trước hết, khi làm việc với phần giữa của danh sách . Việ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 xác định lại liên kết của các phần tử lân cận và phần tử không cần thiết sẽ “rơi ra” khỏi chuỗi liên kết. Trong khi ở trong ArrayListchúng tôi:

• kiểm tra xem có đủ dung lượng không (khi chèn)
• nếu chưa đủ thì tạo mảng mới và sao chép dữ liệu vào đó (khi dán)
• xóa/chèn một phần tử và dịch 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 thao tác). Hơn nữa, độ phức tạp của quá trình này phụ thuộc rất nhiều vào kích thước của danh sách. Việc sao chép/di chuyển 10 phần tử là một chuyện, nhưng thực hiện tương tự với một triệu phần tử lại là một chuyện khác.

Nghĩa là, nếu các thao tác chèn/xóa trong chương trình của bạn xảy ra thường xuyên hơn ở giữa danh sách thì LinkedListthao tác này 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 to run for LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Phần kết luận:

Время работы для LinkedList (в мorсекундах) = 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 to run for ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Phần kết luận:

Время работы для ArrayList (в миллисекундах) = 181

Đột nhiên! Có vẻ như chúng tôi đang thực hiện một thao tác lẽ LinkedListra hiệu quả hơn nhiều - chèn 100 phần tử 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ử: ArrayListchúng tôi phải thay đổi vài triệu phần tử mỗi lần chèn chúng! Nguyên nhân chiến thắng của ông là gì? Đầu tiên, một phần tử được truy cập trong ArrayListmột khoảng thời gian cố định. Khi bạn chỉ ra:

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

thì trong trường hợp ArrayList[2_000_000] đây là một địa chỉ cụ thể trong bộ nhớ, vì nó có một mảng bên trong. Trong khi LinkedListmảng thì không. Nó sẽ tìm phần tử số 2_000_000 dọc theo chuỗi liên kết. Đối với anh ta, đây không phải là một địa chỉ trong bộ nhớ, mà là một liên kết vẫn cần truy cập:

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à, với mỗi lần chèn (xóa) vào giữa danh sách, ArrayListnó đã biết chính xác địa chỉ trong bộ nhớ mà nó cần truy cập nhưng LinkedListvẫn cần “tìm hiểu” đến đúng nơi. Thứ hai , vấn đề nằm ở cấu trúc của ArrayListchính nó. Việc mở rộng mảng bên trong, sao chép tất cả các phần tử và dịch chuyển các phần tử được thực hiện bởi một hàm bên trong đặc biệt - System.arrayCopy(). Nó hoạt động rất nhanh vì nó được tối ưu hóa đặc biệt cho công việc này. Nhưng trong những tình huống không cần phải “dậm chân” đến chỉ số mong muốn thì LinkedListnó thực sự thể hiện tốt hơn. Ví dụ: nếu việc chèn xảy ra ở đầ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("Result in milliseconds: " + msDelay);
       return msDelay;

   }

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

}

Phần kết luận:

Результат в миллисекундах: 43448
Результат в миллисекундах: 107

Một kết quả hoàn toàn khác! Phải mất hơn 43 giây để chèn một triệu phần tử vào đầu danh sách ArrayList, trong khi LinkedListviệc này được hoàn thành trong 0,1 giây! Thực tế chính xác là trong tình huống này, LinkedListchúng tôi không phải “chạy” qua chuỗi liên kết đến giữa danh sách mỗi lần. Anh ấy ngay lập tức tìm thấy chỉ số cần thiết ở đầu danh sách và ở đó, sự khác biệt về nguyên tắc hoạt động đã đứng về phía anh ấy :) Trên thực tế, cuộc thảo luận về “ ArrayListso với LinkedList” rất phổ biến và hiện tại chúng tôi sẽ không đi sâu vào vấn đề đó. mức độ. Điều chính bạn cần nhớ:

• Không phải tất cả các ưu điểm của một bộ sưu tập cụ thể “trên giấy” sẽ hoạt động trên thực tế (chúng tôi đã xem xét điều này bằng cách sử dụng ví dụ ở giữa danh sách)
• Bạn không nên cực đoan khi chọn một bộ sưu tập (“ ArrayListnó luôn nhanh hơn, hãy sử dụng nó và bạn sẽ không mắc sai lầm. LinkedListLâu rồi không có ai sử dụng nó”).

Mặc dù ngay cả người sáng tạo LinkedListJoshua Bloch cũng nói như vậy :) Tuy nhiên, quan điểm này không chính xác 100% và chúng tôi tin chắc về điều này. Trong ví dụ trước của chúng tôi, LinkedListnó hoạt động 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à LinkedListnó sẽ là lựa chọn tốt nhất. Nhưng chúng tồn tại và vào đúng thời điểm, LinkedListchúng có thể giúp đỡ bạn một cách nghiêm túc. Đừng quên những gì chúng ta đã nói ở đầu bài giảng: các cấu trúc dữ liệu khác nhau có hiệu quả nhất cho các nhiệm vụ khác nhau. Không thể nói chắc chắn 100% cấu trúc dữ liệu nào sẽ tốt hơn cho đến khi biết được tất cả các điều kiện của vấn đề. Sau này bạn sẽ biết nhiều hơn về những bộ sưu tập này và sẽ dễ dàng đưa ra lựa chọn hơn. Nhưng tùy chọn đơn giản và hiệu quả nhất luôn giống nhau: kiểm tra cả hai trên dữ liệu thực từ chương trình của bạn. Sau đó, bạn có thể tận mắt nhìn thấy kết quả của cả hai danh sách và bạn chắc chắn sẽ không sai :)