Урок 26. Сравнение LinkedList и ArrayList в Java

Иерархия интерфейсов и их реализаций Java Collections Framework имеет два класса общего назначения для представления списков объектов, а именно LinkedList и ArrayList. На предыдущей статье из серии обучающих статей по Java мы рассмотрели структуру данных LinkedList. LinkedList назван так из-за того, что он внутренне основан на двусвязном списке.

LinkedList и Java.Util.LinkedList

Связные списки и Java.Util.LinkedList на самом деле представляют собой две разные концепции. В качестве аналогии подумайте о разнице между абстрактной концепцией автомобиля на бумаге и реальным BMW.



Связный список - это абстрактная концепция структуры данных, независимая от любого языка программирования или платформы, в то время как класс Java LinkedList является конкретной реализацией. Среди других интерфейсов LinkedList реализует java.util.List. У вас могут быть дубликаты в списке, и вы можете просматривать каждый элемент в том же порядке, в каком он был вставлен.

Разница между ArrayList И LinkedList

Как было описано в предыдущей статье, и ArrayList, и LinkedList реализуют java.util.Интерфейс списка, делающий их несколько похожими друг на друга, но на этом сходство заканчивается. Во-первых, ArrayList основан на необработанных массивах Java, в то время как LinkedList основан на двусвязном списке.



В отличие от ArrayList, двусвязный список LinkedList позволяет более эффективно вставлять и удалять элементы в любой позиции в списке. Поэтому мы предпочитаем LinkedList вместо ArrayList всякий раз, когда наше основное использование списка заключается в добавлении и удалении элементов в случайных позициях. В противном случае ArrayList может быть лучшим выбором, поскольку хранение элементов в массиве потребляет меньше памяти и, как правило, обеспечивает более быстрое время доступа. Помимо реализации списка, LinkedList также реализует интерфейсы очереди и двусвязной очереди. предоставляя ему некоторые дополнительные функции по сравнению с ArrayList.

В заключение следует отметить, что между ArrayList и LinkedList нет общего победителя. Ваши конкретные требования определят, какой класс использовать.

package java.util;
 
public class LinkedList implements List, Deque {

    private Node first;
    private Node last;

    public E get(int index) {…}
    public boolean add(E e) {…}
    public E remove(int index) {…}
 […]
}

В коде выше показан упрощенный фрагмент кода из класса java.util.LinkedList. Полное понимание каждой детали отрывка из кода не требуется. Все, что для этого нужно, - это показать, что LinkedList - это обычный класс Java, который мог бы написать любой, если бы у него было достаточно времени и знаний. Полный, фактический исходный код доступен в интернете. После прочтения этой статьи рекомендуется ознакомиться с ней самостоятельно.

Далее мы видим, что класс LinkedList содержит ссылку на первый и последний элементы списка. Наконец, мы также видим, что в классе есть такие функции, как получение, добавление или удаление – для доступа, вставки или удаления элементов из списка.

Как мы только что видели в коде, ссылки LinkedList на его первый и последний элементы также показаны красными стрелками:



Каждый отдельный элемент в двусвязном списке содержит ссылку на его предыдущий и следующий элементы, а также ссылку на элемент, упрощенную в виде числа в желтом поле.

public class Node {
    private E item;
    private Node previous;
    private Node next;

    public Node(E element, Node previous, Node next) {
        this.item = element;
        this.next = next;
        this.previous = previous;
    }
[...]
}

Фрагмент кода реализации узла связанного списка показан выше. У него есть закрытые члены для элемента, который он содержит, а также для предыдущего и следующего узлов в списке. Как пользователи класса коллекций LinkedList, мы никогда не получаем прямого доступа к узлам. Вместо этого мы используем открытые методы, которые предоставляет LinkedList, которые внутренне работают с членами закрытого узла.

Уже рассмотрев методы интерфейса списка в предыдущей статье, мы перейдем к методам интерфейса очереди, реализованным в LinkedList.

Очередь

С точки зрения высокого уровня интерфейс очереди состоит из трех простых операций: добавление элемента в конец очереди, извлечение элемента из передней части очереди без его удаления, а также извлечение и удаление элемента из передней части очереди.

В течение всего срока службы очереди возникают особые ситуации, такие как попытка удалить элемент из пустой очереди или попытка добавить элемент в полную очередь с ограниченной емкостью.

В зависимости от вашей конкретной реализации это может быть довольно распространенной ситуацией. В этом случае вам понадобится метод, который возвращает значение null или false. В качестве альтернативы, это может быть исключительная ситуация, которая требует, чтобы у вас был метод, который создает исключение. С этой целью интерфейс очереди предлагает каждую из своих операций в двух вариантах – один метод, который создает исключение, и другой, который возвращает специальное значение в определенных случаях, как показано на рисунке ниже.



Очередь позволяет добавлять элементы в ее конец.

В случае, когда add создает исключение, когда очередь заполнена, предложение возвращает false. LinkedList, как и большинство реализаций очередей, имеет практически неограниченную емкость, поэтому он почти никогда не будет заполнен. ArrayBlockingQueue, с другой стороны, является одной из таких реализаций очереди с ограниченной емкостью.

Далее идут element и peek. Оба они позволяют извлекать элемент из начала очереди, не удаляя его. Если очередь пуста, элемент создает исключение, а peek возвращает значение false. Наконец, вы можете извлечь и удалить элемент из передней части очереди. Если очередь пуста, remove создает исключение, а pollreturns возвращает значение false.

Теперь мы рассмотрим некоторые методы из интерфейса Deque, реализованные в LinkedList. Deque - это сокращение от “двусторонняя очередь”, что делает ее очередью, к которой можно получить доступ с любого конца. Как и очередь, deque позволяет добавлять, извлекать, извлекать и удалять элемент. Однако, поскольку к нему можно получить доступ с любого конца, методы очереди, которые мы видели ранее, теперь существуют в двух вариантах – один для первого и один для последнего элемента deque, как показано ниже:



Опять же, давайте рассмотрим это более подробно. Вы можете добавить элементы на оба конца деки. Точно так же, как метод add интерфейса очереди, addFirst и addLast выдадут исключение, когда очередь заполнится. offerFirst и offerLast вернут значение false вместо того, чтобы создавать исключение. Имейте в виду, что LinkedList имеет неограниченную емкость, поэтому он никогда не будет заполнен. С другой стороны, LinkedBlockingDeque - это реализация Deque, которая может иметь ограниченные возможности.

Вы можете извлекать элементы с обоих концов Deque, не удаляя их.

"getFirst” и “getLast” выдадут исключение, когда очередь пуста, в то время как “peekFirst” и “peekLast” в этом случае вернут значение false. Наконец, вы можете извлекать и удалять элементы с обоих концов деки. "removeFirst” и “removeLast” вызовут исключение, когда очередь пуста, в то время как pollFirst и pollLast в этом случае вернут значение false.

Интерфейс Deque также поддерживает методы структуры данных стека, а именно push, peek и pop. Это позволяет нам использовать java.util.LinkedList в виде стека.

Стек - это очень простая структура данных, доступ к которой возможен только сверху. В качестве аналогии подумайте о стопке книг: push добавляет элемент в верхнюю часть стека, что эквивалентно методу addFirst. peek извлекает, но не удаляет элемент из верхней части стека, как и метод peekFirst. pop извлекает и удаляет элемент из верхней части стека, то же самое с методом removeFirst.

Deque<string> deque = new LinkedList<>();
deque.add("1");
deque.add("2");

Queue<string> queue = new LinkedList<>();
queue.add("1");
queue.add("2");
queue.add("3"); // queue: [1, 2, 3]

Deque<string> deque = new LinkedList<>();
deque.addLast("1");
deque.addLast("2");
deque.addLast("3"); // deque: [1, 2, 3]

Во-первых, это ссылочная переменная Deque, deque. Обратите внимание на использование оператора diamond<>, введенного в Java 7. Оператор избавляет нас от необходимости снова писать строку справа от LinkedList. Также обратите внимание на использование интерфейса Deque в строке 1. Это делает так, что мы можем использовать только методы LinkedList, которые реализуют Deque. Поскольку LinkedList реализует другие интерфейсы, такие как интерфейсы коллекции и списка, вы также можете просмотреть ArrayList, который также реализует их, перейдя к нашей предыдущей статье об этом. Возвращаясь к нашему примеру, вызов deque.add в строках “1”, “2” и “3” дает нам Deque, содержащий элементы [1, 2, 3] в таком порядке.

Замена deque переменной ссылки на очередь, queue, дает нам тот же результат. Превратив нашу очередь обратно в Deque, мы можем использовать addLast для добавления элементов в конец deque. Конечно же, мы получаем тот же результат, что и в двух предыдущих примерах.

Deque<string> deque = new LinkedList<>();
deque.addFirst("1");
deque.addFirst("2");
deque.addFirst("3"); // deque: [3, 2, 1]

Deque<string> deque = new LinkedList<>();
deque.add("1");
deque.addLast("2");
deque.addFirst("3"); // deque: [3, 1, 2]

Начиная с пустого deque, мы можем использовать addFirst для добавления элементов в обратном порядке в addLast, что даст нам 3, 2, 1. Мы можем перепутать это, используя как addFirst, так и addLast в одном месте, но это может привести к большой путанице, поэтому мы должны стараться избегать этого.

Offer, OfferFirst и OfferLast

Deque<string> deque = new LinkedBlockingQueue(2);
deque.offer("1"); 
deque.offerFirst("2");
boolean wasAdded = deque.offerLast("3"); // wasAdded: false
// deque: [1, 2]

Аналогично трем методам добавления, у нас есть три метода предложения, которые не так сильно отличаются от первого, когда дело доходит до списков ссылок. Однако с LinkedBlockingDeque, поскольку мы можем ограничить максимальное количество элементов в очереди, добавив один по максимуму, мы ожидаем, что что-то произойдет. Как оказалось, группа методов предложения просто вернет логическое значение, указывающее, был ли элемент принят или нет. В случае, если мы добавим еще один элемент в полный список, наши методы предложения вернут значение false.

Deque<string> deque = new LinkedBlockingQueue(2);
deque.offer("1");
deque.offerFirst("2");
 
deque.add("3"); // вызывает исключение IllegalStateException

Что произойдет, если вместо этого мы используем метод добавления в полном LinkedBlockingDeque? Наша программа фактически выдаст исключение IllegalStateException. В обычных обстоятельствах одно и то же исключение не генерируется с помощью списка ссылок, поскольку это практически неограниченная реализация очереди и Deque.

В заключение отметим, что еще одно различие между методами add и offer заключается в том, что add возвращает значение void, в то время как предложение возвращает логическое значение. Это, вероятно, незначительная разница, потому что это будет иметь значение только в том случае, если реализация очереди или Deque имеет ограниченную емкость.

Чтение Deques и Queues

Элемент

Deque<string> deque = new LinkedList<>();
deque.add("1");
deque.add("2");
deque.add("3");
  
String element = deque.element(); // element: 1
// deque: [1, 2, 3]

Функция общего назначения для чтения из дескрипторов и очередей является элементом. Как показывает наш фрагмент, мы всегда извлекаем крайний левый элемент, и никакие элементы впоследствии не удаляются из deque.

Что касается явного извлечения элемента из передней или задней части нашего дека, мы фактически используем getFirst и getLast. Чтобы явно извлечь элемент из передней части deque, мы используем getFirst. В нашем случае он работает точно так же, как элемент из нашего последнего примера.

getFirst и getLast Чтобы явно извлечь элемент из передней части deque, мы используем getFirst. В нашем случае он работает точно так же, как элемент из нашего последнего примера.

Чтобы явно извлечь элемент из передней части deque, мы используем getFirst. В нашем случае он работает точно так же, как элемент из нашего последнего примера.

Deque<string> deque = new LinkedList<>();
deque.add("1");
deque.add("2");
deque.add("3");
  
String first = deque.getFirst(); // first: 1
 
// deque: [1, 2, 3]

И наоборот, мы используем getLast для явного извлечения элемента из задней части deque.

Deque<string> deque = new LinkedList<>();
deque.add("1");
deque.add("2");
deque.add("3");
 
String last = deque.getLast(); // last = 3
 
// deque: [1, 2, 3]

PeekFirst и PeekLast

Как и в случае с add и offer, методы чтения из deque очень похожи. Разница проявляется при пустой deque или queue.

Deque<string> deque = new LinkedList<>();
String first = deque.peekFirst(); // first = null
// deque: []


Deque<string> deque = new LinkedList<>();
String last = deque.peekLast(); // last = null
// deque: []

С element, getFirst и getLast пустой дескриптор вызывает исключение NoSuchElementException.

Deque deque = new LinkedList<>();
String element = deque.element()

Deque<string> deque = new LinkedList<>();
String element = deque.getFirst(); // throws NoSuchElementException<

Deque<string> deque = new LinkedList<>();
String element = deque.getLast();  // throws NoSuchElementException

Теперь возникает вопрос, какие методы использовать в каких случаях. Всякий раз, когда мы ожидаем, что зачитаем пустой счет, мы, вероятно, воспользуемся методами peek. Для ограниченных заявок и очередей мы, вероятно, будем использовать методы offer. И наоборот, когда мы считаем невозможность добавления в запросы или очереди исключительным случаем, мы будем использовать методы add. Интерфейс очереди и Deque довольно гибкий, предоставляя нам различные типы поведения.

Стек

Наконец, мы рассмотрим стеки и то, как они связаны с предыдущими темами. Методы, определяющие поведение стека, на самом деле также являются частью интерфейса Deque. На самом деле, интерфейса стека не существует. Существует класс стека, который расширяет вектор, но, согласно предыдущей статье, следует избегать класса Vector, что означает, что стека тоже следует избегать - производительность tuj довольно неоптимальна. Конечно, мы можем использовать что-то столь же простое, как массив или список массивов, но вместо этого мы рассмотрим методы стека Deque.

Deque stack = new LinkedList<>();
stack.push("redBook");
stack.push("brownBook"); // stack: [brownBook, redBook]
String top = stack.peek(); // top: brownBook, stack: [brownBook, redBook]
top = stack.pop(); // top = brownBook, stack: [redBook]
top = stack.pop(); // top = redBook, stack: []
stack.pop(); // throws NoSuchElementException

Чтобы добавить элемент в стек, мы вызываем метод push. Поскольку стеки являются первыми и последними структурами данных, когда мы добавляем, скажем, “красную книгу”, а затем “коричневую книгу” в наш стек, мы можем думать, что коричневая книга находится поверх красной.

Если мы хотим просто извлечь или удалить книгу, коричневая книга будет взята, потому что мы можем делать вещи только на вершине стопки. В нашем случае “Коричневая книга” - это то, что stack.peek() возвращает в качестве верхнего элемента. Обратите внимание, что в списке ссылок хранятся элементы, начинающиеся сверху вниз, таким образом, чтобы при распечатке они отображались слева направо.

После этого мы вынимаем элементы из стека один за другим и видим, что “Коричневая книга” вынимается первой, уменьшая размер стека до одного, а затем “Красная книга”, делая стек пустым. Наконец, повторное удаление, на этот раз из пустого стека, приведет к тому, что наш код вызовет исключение NoSuchElementException.

Deque stack = new LinkedList<>();
String top = stack.peek(); // top = null, stack: []

Наконец, если бы мы вместо этого вызвали peek в пустом стеке, нам вернули бы нулевое значение для top без исключения. Стопка все равно остается пустой.