Все последние уроки Code Gym были посвящены ArrayList . Эта структура данных очень удобна и полезна. Он может справиться с множеством задач. Но в Java есть множество других структур данных.
Почему? Прежде всего, потому, что спектр задач огромен, и наиболее эффективные структуры данных различны для разных задач .
Сегодня мы познакомимся с новой структурой: Связанный список
Давайте посмотрим, как он организован, почему он называется двусвязным, чем он отличается от ArrayList .
Элементы в Связанном списке на самом деле являются звеньями в одной цепочке. В дополнение к данным, каждый элемент хранит ссылки на предыдущий и следующий элементы . Эти ссылки позволяют переходить от одного элемента к другому.
Вот как вы его создаете:
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 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 Canada]
Вот как выглядит наш список:
Давайте посмотрим, как добавить новый элемент. Это делается с помощью метода add() .
earlBio.add(str2);
В этом месте кода наш список состоит из одного элемента: строки str1 .
Давайте посмотрим, что будет дальше на картинке:
В результате str2 и str1 становятся связанными через next и предыдущие ссылки, хранящиеся в этих узлах списка:
Теперь вы должны понять основную идею двусвязного списка. Эта цепочка ссылок – именно то, что делает LinkedList elements единым списком. В отличие от ArrayList , Связанный список не содержит массива или чего-либо подобного массиву внутри.
Любая (ну, большая часть) работа с ArrayList сводится к работе с внутренним массивом.
Любая работа с Связанный список сводится к смене ссылок.
Это можно очень четко увидеть, добавив элемент в середину списка:
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 earlBio = new LinkedList<>();
earlBio.add(str1);
earlBio.add(str3);
earlBio.add(1, str2);
System.out.println(earlBio);
}
}
Как вы можете видеть, перегруженный метод add() позволяет указать определенный индекс для нового элемента. В этом случае мы хотим добавить строку str2 между str1 и str3 .
Это то, что произойдет внутри:
После изменения внутренних ссылок/| str2 был успешно добавлен в список:
Теперь все 3 элемента соединены. Вы можете перемещаться по ссылке next от первого элемента цепочки к последнему и обратно.
Итак, нас вполне устраивает вставка, но как насчет удаления элементов?
Принцип точно такой же. Мы просто обновляем ссылки в двух элементах “слева и справа” от удаляемого элемента:
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 earlBio = new LinkedList<>();
earlBio.add(str1);
earlBio.add(str3);
earlBio.add(1, str2);
earlBio.remove(1);
System.out.println(earlBio);
}
}
Вот что произойдет, если мы удалим элемент с индексом 1 (он находится в середине списка).:
После обновления ссылок мы получаем желаемый результат:
В отличие от операции удаления в ArrayList , здесь нет необходимости сдвигать элементы массива или делать что-либо в этом роде. Мы просто обновляем ссылки для str1 и str3 . Теперь они указывают друг на друга, и str2 ” выпал ” из цепочки ссылок и больше не является частью списка.
Обзор методов
LinkedList имеет много общих методов с ArrayList .
Например, оба класса имеют такие методы, как add() , remove() , indexOf() , clear() , contains() (указывает, есть ли элемент в списке), set() (заменяет существующий элемент) и size() .
Хотя многие из них работают по-разному внутри (как мы обнаружили с помощью add() и remove() ), конечный результат тот же.
Однако Связанный список имеет отдельные методы для работы с началом и концом списка, которых ArrayList не имеет:
addFirst(),addLast(): Эти методы для добавления элемента в начало/конец списка
public class Car {
String model;
public Car(String model) {
this.model = model;
}
public static void main(String[] args) {
LinkedList 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 Modneo");
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 Modneo'}, 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 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 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);
}
Выход:
Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
What's left on the list?
[Car{model='Bugatti Veyron'}]
toArray(): Этот метод возвращает массив, содержащий элементы списка
public static void main(String[] args) {
LinkedList 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'}]
Теперь мы знаем, как работает Связанный список и чем его организация отличается от ArrayList . Каковы преимущества использования Связанного списка ?
Прежде всего, мы выигрываем, когда работаем в середине списка . Операции вставки и удаления в середине Связанного списка намного проще, чем в ArrayList . Мы просто обновляем ссылки соседних элементов, и ненужный элемент “выпадает” из цепочки ссылок.
Но в ArrayList , мы должен
- проверьте, достаточно ли места (при вставке)
- если нет, то мы создаем новый массив и копируем туда данные (при вставке)
- мы удаляем/вставляем элемент, а все остальные элементы перемещаем вправо/влево (в зависимости от типа операции). И сложность этого процесса в значительной степени зависит от размера списка. Одно дело скопировать/переместить 10 элементов, и совсем другое – сделать то же самое с миллионом элементов.
Другими словами, если операции вставки/удаления вашей программы в середине списка наиболее распространены в вашей программе, LinkedList должен быть быстрее, чем ArrayList .
В теории
public class Main {
public static void main(String[] args) {
List 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));
}
}
Выход:
Time taken by LinkedList (in milliseconds) = 1873
public class Main {
public static void main(String[] args) {
List 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));
}
}
Выход:
Time taken by ArrayList (in milliseconds) = 181
Это было неожиданно!
Мы выполнили операцию, в которой Связанный список должен быть намного эффективнее: вставка 100 элементов в середину списка.
И наш список огромен: 5 000 000 элементов. ArrayList приходилось сдвигать пару миллионов элементов при каждой вставке!
Как он победил?
Во-первых, время, необходимое ArrayList для доступа к элементам, является фиксированным (постоянным). Когда ты пишешь
list.add(2_000_000, new Integer(Integer.MAX_VALUE));
затем ArrayList Список массивов//[2_000_000] – это определенный адрес памяти (в конце концов, список имеет внутренний массив).
Но Связанный список не имеет массива. Он будет искать элемент с номером 2_000_000 по цепочке ссылок. Для связанного списка это не адрес памяти, а ссылка, до которой все еще необходимо добраться:
первый Element.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 уже знает точный адрес памяти для доступа, но Связанный список все еще должен “попасть туда”.
Во-вторых, существует структура самого ArrayList . Специальная внутренняя функция ( System.arrayCopy() ) расширяет внутренний массив, копирует и сдвигает все элементы. Это очень быстро, потому что оно оптимизировано для этой конкретной работы.
Но когда вам не нужно “добираться” до определенного индекса, выигрывает Связанный список . Предположим, мы вставляем в самое начало списка.
Давайте попробуем вставить туда миллион элементов:
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());
}
}
}
Выход:
The result in milliseconds: 43448 The result in milliseconds: 107
Теперь мы получаем совершенно другой результат!
ArrayList потратил более 43 секунд на вставку миллиона элементов в начало списка, в то время как LinkedList сумел сделать это за 0,1 секунды!
LinkedList выиграл здесь, потому что ему не нужно было каждый раз проходить по цепочке ссылок до середины списка. Он сразу же находит нужный индекс в начале списка, так что другой алгоритм уже является преимуществом.:)
На самом деле, обсуждение ” ArrayList против Связанного списка ” очень широко распространено, и мы не будем углубляться в него на текущем уровне. Главное, что вам нужно помнить, это следующее:
Не все теоретические преимущества какой-либо конкретной коллекции всегда работают в реальности (мы видели это на примере, включающем середину списка)
Не занимайте крайнюю позицию, когда дело доходит до выбора коллекции (”
ArrayListвсегда быстрее. Используйте его, и вы не ошибетесь. Никто не использовалСвязанный списокв течение длительного времени”).
Хотя даже автор Связанного списка , Джошуа Блох, говорит, что это так.:)
Тем не менее, эта точка зрения далека от 100% правильной, и мы убедили себя в этом. В нашем предыдущем примере/| Связанный список составлял 400 (!) в разы быстрее. Другое дело, что на самом деле существует несколько ситуаций, когда Связанный список является лучшим выбором. Но они действительно существуют, и в нужный момент Связанный список может щедро вознаградить вас. Не забывайте, что мы говорили в начале урока: наиболее эффективные структуры данных различны для разных задач .
Невозможно быть на 100% уверенным в том, какая структура данных будет наилучшей, пока вы не узнаете все условия вашей задачи.
Позже вы узнаете больше об этих коллекциях, что облегчит вам выбор. Но самый простой и эффективный вариант всегда один и тот же: попробуйте оба варианта на реальных данных, используемых в вашей программе. Тогда вы сможете сами увидеть, как работают оба типа списков, и вы определенно не ошибетесь.:)
Ранее было опубликовано в блоге CodeGym/| .
Оригинал: “https://dev.to/codegym_cc/java-linkedlist-tutorial-with-examples-3nmi”