Java LinkedList

здрасти Всички последни уроци са посветени на ArrayList . Тази структура от данни е много удобна и полезна. Може да се справи с много задачи. Но Java има много други структури от данни. Защо? Преди всичко, защото наборът от задачи е огромен и най-ефективните структури от данни са различни за различните задачи. Днес ще се запознаем с нова структура: Java LinkedList , двойно свързан списък. Нека да видим How е организиран, защо се нарича двойно свързан, How се различава от ArrayList . Елементите в Java LinkedList всъщност са връзки в една верига. В допълнение към данните, всеки елемент съхранява препратки към предишния и следващия елемент. Тези препратки ви позволяват да преминавате от един елемент към друг. Ето How създавате такъв:

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);

   }
}

Резултат: [Здравей свят! Казвам се Ърл, обичам Java, живея в Канада] Ето How изглежда нашият списък: Да видим How да добавим нов елемент. Това се прави с помощта на метода add() .

earlBio.add(str2);

В точката в codeа нашият списък се състои от един елемент: String str1 . Нека да видим Howво се случва по-нататък на снимката: В резултат str2 и str1 се свързват чрез следващите и предишните връзки, съхранени в този възел на списъка: Сега трябва да разберете основната идея на двойно свързан списък. Тази верига от връзки е точно това, което прави елементите на LinkedList единичен списък. За разлика от ArrayList , LinkedList няма масив or нещо подобно на масив вътре. Всяка (е, повечето) работа с ArrayList се свежда до работа с вътрешния масив. Всяка работа с Java LinkedListсе свежда до промяна на връзките. Това може да се види много ясно чрез добавяне на елемент в средата на списъка:

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);

   }
}

Както можете да видите, претовареният метод add() ви позволява да посочите конкретен индекс за нов елемент. В този случай искаме да добавим String str2 между str1 и str3 . Ето Howво ще се случи вътрешно: След промяна на вътрешните връзки str2 беше успешно добавен към списъка: Сега всичките 3 елемента са свързани. Можете да се придвижите през следващата връзка от първия елемент на веригата до последния и обратно. И така, ние сме доста удобни с вмъкването, но Howво да кажем за премахването на елементи? Принципът е абсолютно същият. Ние просто актуализираме връзките в двата елемента "отляво и отдясно" на премахвания елемент:

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);
   }
}

Ето Howво се случва, ако изтрием елемента с индекс 1 (той е в средата на списъка): След като актуализираме връзките, получаваме желания резултат: За разлика от операцията за премахване в ArrayList , тук няма нужда да премествате елементи от масива or да правите нещо подобно. Ние просто актуализираме връзките за str1 и str3 . Сега те сочат един към друг и str2 е " изпаднал " от веригата от връзки и вече не е част от списъка.

Преглед на методите

LinkedList има много общи методи с ArrayList . Например и двата класа имат методи като add() , remove() , indexOf() , clear() , contains() (показва дали даден елемент е в списъка), set() (заменя съществуващ елемент) и размер() . Въпреки че много от тях работят по различен начин вътрешно (Howто установихме с add() и remove() ), крайният резултат е същият. LinkedList обаче има отделни методи за работа с началото и края на списъка, които ArrayList няма:

• addFirst() , addLast() : Тези методи за добавяне на елемент в началото/края на списъка

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 + '\'' +
               '}';
   }
}

Изход: [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'}] Завършваме с "Ford" в горната част на списъка, и "Фиат" накрая.

• peekFirst() , peekLast() : Методите връщат първия/последния елемент в списъка. Те връщат нула, ако списъкът е празен.

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());
}

Изход: Автомобил{model='Ferrari 360 Spider'} Автомобил{model='Lamborghini Diablo'}

• pollFirst() , pollLast() : Тези методи връщат първия/последния елемент в списъка и го премахват от списъка. Те връщат нула, ако списъкът е празен

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);
}

Изход: Автомобил{model='Ferrari 360 Spider'} Автомобил{model='Lamborghini Diablo'} Какво остава в списъка? [Автомобил{model='Bugatti Veyron'}]

• toArray() : Този метод връща масив, съдържащ елементите от списъка

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));
}

Резултат: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] Сега знаем How работи LinkedList и How неговата организация се различава от ArrayList . Какви са предимствата от използването на LinkedList ? Преди всичко ние печелим, когато работим в средата на списъка. Операциите за вмъкване и премахване в средата на LinkedList са много по-прости, отколкото в ArrayList . Ние просто актуализираме връзките на съседни елементи и нежеланият елемент "отпада" от веригата от връзки. Но в ArrayList трябва

• проверете дали има достатъчно място (при поставяне)
• ако не, тогава създаваме нов масив и копираме данните там (при вмъкване)
• премахваме/вмъкваме елемента и преместваме всички останали елементи надясно/наляво (в зависимост от вида на операцията). И сложността на този процес зависи до голяма степен от размера на списъка. Едно е да копираш/преместиш 10 елемента, а съвсем друго е да направиш същото с мorон елемента.

С други думи, ако операциите за вмъкване/премахване в средата на списъка са най-често срещани във вашата програма, LinkedList трябва да бъде по-бърз от ArrayList .

На теория

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));
   }
}

Резултат: Време, необходимо на 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 taken by ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Резултат: Време, необходимо за ArrayList (в мorсекунди) = 181 Това беше неочаквано! Извършихме операция, при която LinkedList трябва да е много по-ефективен: вмъкване на 100 елемента в средата на списък. И нашият списък е огромен: 5 000 000 елемента. ArrayList трябваше да премести няколко мorона елемента с всяко вмъкване! Как спечели? Първо, времето, необходимо на ArrayList за достъп до елементи, е фиксирано (постоянно). Когато пишете

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

тогава ArrayList [2_000_000] е специфичен address на паметта (в края на краищата списъкът има вътрешен масив). Но LinkedList няма масив. Той ще търси елемент номер 2_000_000 по веригата от връзки. За LinkedList това не е address на паметта, а връзка, която все още трябва да бъде достигната: 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……… В резултат на това при всяко вмъкване (премахване) в средата на списъка , ArrayList вече знае точния address на паметта за достъп, но LinkedList все още трябва да „стигне до там“. Второ, има структура на ArrayListсебе си. Специална вътрешна функция ( System.arrayCopy() ) разширява вътрешния масив и копира и измества всички елементи. Много е бърз, защото е оптимизиран за тази специфична работа. Но когато не е нужно да „стигате до“ определен индекс, LinkedList е победителят. Да предположим, че вмъкваме в самото начало на списъка. Нека опитаме да вмъкнем мorон елемента там:

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());
       }
   }

}

Изход: Резултатът в мorсекунди: 43448 Резултатът в мorсекунди: 107 Сега получаваме съвсем различен резултат! ArrayList прекара повече от 43 секунди, за да вмъкне мorон елемента в началото на списъка, докато LinkedList успя да го направи за 0,1 секунди! LinkedList се възползва тук, защото не трябваше да преминава през веригата от връзки до средата на списъка всеки път. Веднага намира необходимия индекс в началото на списъка, така че различният алгоритъм вече е предимство. :) Всъщност дискусията " ArrayList срещу LinkedList " е много разпространена и няма да се потапяме дълбоко в нея на сегашното ниво. Основното нещо, което трябва да запомните е следното:

• Не всички теоретични предимства на дадена конкретна колекция винаги работят в действителност (видяхме това с примера, включващ средата на списъка)
• Не заемайте крайна позиция, когато става въпрос за избор на колекция („ ArrayList винаги е по-бърз. Използвайте го и няма да сгрешите. Никой не е използвал LinkedList от дълго време“).

Въпреки че дори авторът на LinkedList , Джошуа Блок, казва, че това е така. :) Все пак тази гледна точка далеч не е 100% вярна и сами сме се убедor в това. В предишния ни пример LinkedList беше 400 (!) пъти по-бърз. Друго нещо е, че наистина има малко ситуации, в които LinkedList е най-добрият избор. Но те съществуват и в точния момент LinkedListможе да ви възнагради щедро. Не забравяйте Howво казахме в началото на урока: най-ефективните структури от данни са различни за различните задачи. Невъзможно е да сте 100% сигурни коя структура от данни ще бъде най-добра, докато не знаете всички условия на вашата задача. По-късно ще научите повече за тези колекции, което ще улесни избора. Но най-простият и най-ефективен вариант винаги е един и същ: опитайте и двете върху действителните данни, използвани във вашата програма. Тогава ще можете сами да видите How се представят и двата вида списъци и определено няма да сбъркате. :) За да затвърдите наученото, ви предлагаме да гледате видео урок от нашия курс по Java