User Professor Hans Noodles
Professor Hans Noodles
41 уровень

LinkedList

Статья из группы Java Developer
Привет! Все последние лекции были посвящены изучению списка ArrayList. Эта структура данных очень удобная и позволяет решать множество задач. Однако в Java есть множество других структур данных. LinkedList - 1Почему? Прежде всего потому, что круг существующих задач очень широк, и для разных задач наиболее эффективными являются разные структуры данных. Сегодня мы познакомимся с новой структурой — двусвязным списком LinkedList. Давай разберемся, как он устроен, почему называется двусвязным и в чем его отличия от ArrayList. В LinkedList элементы фактически представляют собой звенья одной цепи. У каждого элемента помимо тех данных, которые он хранит, имеется ссылка на предыдущий и следующий элемент. По этим ссылкам можно переходить от одного элемента к другому. Создается он так:

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

   }
}
Вывод:

[Hello World! My name is Earl, I love Java, I live in Moscow]
Вот так будет выглядеть строение нашего списка: LinkedList - 2Давай посмотрим, как производится добавление нового элемента. Это делается с помощью метода add().

earlBio.add(str2);
На момент этой строчки кода наш список состоит из одного элемента — строки str1. Посмотрим, что происходит дальше на картинке: LinkedList - 3В результате str2 и str1 становятся связанными через хранящиеся в них ссылки next и previous: LinkedList - 4Теперь тебе должна стать понятной главная идея двусвязного списка. Элементы LinkedList являются единым списком именно благодаря вот этой цепочке ссылок. Внутри LinkedList нет массива, как в ArrayList, или чего-то похожего. Вся работа с ArrayList (по большому счету) сводится к работе с внутренним массивом. Вся работа с LinkedList сводится к изменению ссылок. Это очень хорошо видно на примере добавления элемента в середину списка:

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

   }
}
Как видишь, перегруженный метод add() позволяет указать конкретный индекс для нового элемента. В данном случае мы хотим добавить строку str2 между str1 и str3. Вот что будет происходить внутри: LinkedList - 5И в результате изменения внутренних ссылок элемент str2 успешно добавлен в список: LinkedList - 6Теперь все 3 элемента связаны. От первого элемента по цепочке next можно дойти до последнего и обратно. Со вставкой мы более-менее разобрались, а что с удалением элементов? Принцип работы тот же. Мы просто переопределяем ссылки у двух элементов “по бокам” от удаляемого:

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);
   }
}
Вот что будет происходить, если мы удалим элемент с индексом 1 (он находится посередине списка): LinkedList - 7После переопределения ссылок мы получаем нужный результат: LinkedList - 8В отличие от удаления в ArrayList здесь нет никаких сдвигов элементов массива и тому подобного. Мы просто переопределяем ссылки у элементов str1 и str3. Теперь они указывают друг на друга, а объект str2 “выпал” из этой цепочки ссылок, и больше не является частью списка.

Обзор методов

У LinkedList есть много общих с ArrayList методов. Например, такие методы как add(), remove(), indexOf(), clear(), contains() (содержится ли элемент в списке), set() (вставка элемента с заменой) и size() есть в обоих классах. Хотя (как мы выяснили на примере 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'}]
В итоге “Форд” оказался в начале списка, а “Фиат” — в конце.
  • peekFirst(), peekLast(): возвращают первый/последний элемент списка. Возвращают null, если список пуст.

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());
}
Вывод:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
  • pollFirst(), pollLast(): возвращают первый/последний элемент списка и удаляют его из списка. Возвращают null, если список пуст

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("Что осталось в списке?");
   System.out.println(cars);
}
Вывод:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
Что осталось в списке?
[Car{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'}]
Теперь мы знаем, как устроен LinkedList и чем он отличается от ArrayList. В чем же заключаются выгоды от использования LinkedList? Прежде всего, в работе с серединой списка. Вставка и удаление в середину LinkedList устроены гораздо проще, чем в ArrayList. Мы просто переопределяем ссылки соседних элементов, а ненужный элемент “выпадает” из цепочки ссылок. В то время как в ArrayList мы:
  • проверяем, хватает ли места (при вставке)
  • если не хватает — создаем новый массив и копируем туда данные (при вставке)
  • удаляем/вставляем элемент, и сдвигаем все остальные элементы вправо/влево (в зависимости от типа операции). Причем сложность этого процесса сильно зависит от размера списка. Одно дело — скопировать/сдвинуть 10 элементов, и совсем другое — сделать то же самое с миллионом элементов.
То есть, если в твоей программе чаще происходят операции вставки/удаления с серединой списка, LinkedList должен быть быстрее, чем ArrayList. LinkedList - 9

Теоретически


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

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

Время работы для ArrayList (в миллисекундах) = 181
Неожиданно! Казалось бы, мы проводили операцию, где LinkedList должен быть намного эффективнее — вставку 100 элементов в середину списка. Да и список у нас огромный — 5000000 элементов: ArrayList’у приходилось сдвигать по паре миллионов элементов каждый раз при вставке! В чем же причина его победы? Во-первых, доступ к элементу осуществляется в ArrayList за фиксированное время. Когда ты указываешь:

list.add(2_000_000, new Integer(Integer.MAX_VALUE));
то в случае с ArrayList [2_000_000] это конкретный адрес в памяти, ведь у него внутри массив. В то время как у LinkedList массива нет. Он будет искать элемент номер 2_000_000 по цепочке ссылок. Для него это не адрес в памяти, а ссылка, до которой еще надо дойти:

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 уже знает точный адрес в памяти, к которому он должен обратиться, а вот LinkedList’у еще надо до нужного места “дотопать”. Во-вторых, дело в структуре самого ArrayList’a. Расширение внутреннего массива, копирование всех элементов и сдвиг элементов осуществляет специальная внутренняя функция — System.arrayCopy(). Она работает очень быстро, потому что специально оптимизирована для этой работы. А вот в ситуациях, когда “топать” до нужного индекса не нужно, LinkedList действительно показывает себя лучше. Например, если вставка происходит в начало списка. Попробуем вставить туда миллион элементов:

public class Main {

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

   public static long getTimeMsOfInsert(List list) {
       //напишите тут ваш код
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); //вычисляем разницу
       System.out.println("Результат в миллисекундах: " + msDelay);
       return msDelay;

   }

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

}
Вывод:

Результат в миллисекундах: 43448
Результат в миллисекундах: 107
Совсем другой результат! На вставку миллиона элементов в начало списка ArrayList затратил больше 43 секунд, в то время как LinkedList справился за 0,1 секунды! Сказался именно тот факт, что в этой ситуации LinkedList’у не пришлось “пробегать” каждый раз по цепочке ссылок до середины списка. Он сразу находил нужный индекс в начале списка, а там уже разница в принципах работы была на его стороне:) На самом деле, дискуссия “ArrayList против LinkedList” имеет очень широкое распространение, и сильно в нее углубляться на текущем уровне мы не будем. Главное, что тебе нужно запомнить:
  • Не все преимущества той или иной коллекции “на бумаге” будут действовать в реальности (мы разобрали это на примере с серединой списка)
  • Не стоит бросаться в крайности при выборе коллекции (“ArrayList всегда быстрее, используй его и не ошибешься. LinkedList давно никто не пользуется”).
Хотя даже создатель LinkedList Джошуа Блох так говорит:) Тем не менее, эта точка зрения верна далеко не на 100%, и мы в этом убедились. В нашем предыдущем примере LinkedList отработал в 400 (!) раз быстрее. Другое дело, что ситуаций, когда LinkedList будет лучшим выбором, действительно немного. Но они есть, и в нужный момент LinkedList может тебя серьезно выручить. Не забывай про то, о чем мы говорили в начале лекции: для разных задач наиболее эффективными являются разные структуры данных. Нельзя на 100% уверенно говорить, какая структура данных будет лучше, пока неизвестны точно все условия задачи. Позднее ты будешь больше знать об этих коллекциях, и сделать выбор будет проще. Но самый простой и действенный вариант всегда один: испытай и то, и другое на реальных данных своей программы. Тогда ты сможешь своими глазами увидеть результаты работы обоих списков и точно не ошибешься :)
Комментарии (108)
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION
Anonymous #2610525 Уровень 20 Екатеринбург
6 мая 2021
Чета ещё больше запутал автор. GavaRush в своих лекциях пишет, что ArrayList легко добавлять в начало, середину и в конец. А типа в LinkedList нет. А тут наоборот автор пишет. GavaRush пишет что быстрее и оптимальней работа как раз сдвига в ArrayList, чем проходить миллионный список в LinkedList чтобы получить нужную ссылку. А тут автор пишет, что наоборот. Короче все пишут, что и то и другое работает быстрее якобы. Не понятно кто не так описал разницу в работе LinkedList GavaRush в своих лекциях или автор в данной статье. Потому работа LinkedList смысл описан одинаково, что в лекции LinkedList у GavaRush, но при этом абсолютная противоположность в выводах.
Brain🚀 Уровень 35 Россия
27 апреля 2021
Очень доходчиво изложено! Лекцию об этом не понял от слова вообще, а тут совсем по другому, все понятно. Благодарю!
Денис Клименко Уровень 9 Минск Беларусь
19 апреля 2021
Очень интересная и познавательная статья. Спасибо!
Юра Суботинов Уровень 14 Одесса Украина
14 марта 2021
Крутая статья, спасибо :)
Barm Уровень 16 Минск
12 марта 2021
"Вся работа с ArrayList" - ссылка недействительна А статья - прекрасна.
Сергей Петров Уровень 16 Новосибирск Россия
10 марта 2021
Тут ошибка на картинке (видимо, по невнимательности): при удалении Str2 для Str3 предыдущая станет Str1
Альберт Уровень 14 Сургут Россия
15 февраля 2021
Не совсем пойму зачем нужен метод addFirst если можно воспользоваться методом add(0, str2)? Тоже самое с addLast.
new Cat("Barsik") Уровень 20 Сызрань Россия
6 февраля 2021
Может я что-то упускаю, но почему здесь используют String string = new String(" "); вместо String string = " ";
Lyudmila Zhdanok Уровень 12 Минск Белоруссия
19 декабря 2020
одного не поняла: если есть функция addLast() то куда вставляет элемент функция add()? ведь если не прописывать индекс, то элемент итак попадает в конец списка, разве нет?
Константин Уровень 23 Алматы Казахстан
17 декабря 2020
Получается так.