Урок 25. Связный список Java

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

Терминология

Прежде всего, давайте взглянем на термин “Связный список”. Почему он так называется? Для термина ссылка – в качестве аналогии – подумайте о гиперссылке на веб-странице, которая может перенести вас с одной страницы на другую. Список - это набор связанных объектов. Подумайте о списке покупок: в нем содержится каждый товар, который вы планируете купить. Связный список (англ Linked List) - это набор связанных объектов, где ссылка переносит нас от одного элемента к другому.


односвязный список

Технически элемент в нашем связном списке или просто запись в списке хранится в узле. В нашем простом примере на рисунке выше этой записью является число 23. Каждый узел имеет ссылку или указатель на следующий элемент списка – следующий узел. Для каждого элемента, который мы хотим добавить в список, мы создаем узел и сохраняем элемент в нем. Первый элемент списка обычно называется головой, в то время как последний элемент называется хвостом.

Связный список - это динамическая структура данных, которая может содержать любое количество элементов, если доступно достаточно памяти. После создания списка навигация по списку выполняется путем вызова функции, подобной next(), которая использует ссылку для перехода от одного элемента к следующему. Этот тип связного списка называется односвязным списком, потому что ссылки идут только в одном направлении, т. е. от начала списка к концу. Это делает так, что при переходе к предыдущему элементу, например от элемента 42 до элемента 9, как показано на рисунке выше, нам придется вернуться к началу списка и вызывать функцию next() для каждого отдельного элемента, пока мы не достигнем 9. Если список содержит много элементов, это может занять некоторое время.

Вставка элемента после текущего относительно проста при использовании односвязного списка. Допустим, мы начинаем с 9 в качестве нашего текущего элемента.


Простой связный список

Мы создаем новый узел, содержащий новый элемент


Связный список с новым узлом

Мы добавляем ссылку, указывающую от нового элемента “17” к существующему элементу “42”.


ссылка на новый элемент

Мы добавляем ссылку, указывающую от нового элемента “17” к существующему элементу “42”.


ссылка на новый элемент

При этом элемент теперь вставлен.


вставлен новый элемент

Вставка одного и того же элемента перед текущим возможна в односвязном списке, но обычно не очень эффективна. Это потребует от нас перехода к предыдущему элементу, начиная с начала списка, как показано ранее. Удаление элемента из односвязного списка имеет ту же проблему-это возможно, но, как правило, неэффективно.

Эти операции становятся намного проще, когда мы добавляем вторую ссылку к каждому узлу, указывающую на предыдущий. Это позволяет нам перемещаться по обоим направлениям списка, вперед и назад. Однако дополнительная ссылка обходится за счет дополнительной памяти, а также дополнительного времени для создания более сложной структуры. Оправданы ли накладные расходы, во многом зависит от варианта использования. Если производительность является проблемой, рекомендуется протестировать различные варианты.

Двусвязный список

Связный список, содержащий узлы, которые предоставляют ссылку на следующий и предыдущий узлы, называется двусвязным списком. Для каждого элемента, добавленного в двусвязный список, нам нужно создать две ссылки, что делает двусвязные списки несколько сложнее, чем их односвязные аналоги. Перемещаться в обоих направлениях по двусвязному списку проще, но это достигается за счет более сложной структуры. Благодаря двусторонней структуре ссылок добавление или удаление элемента до или после текущего элемента относительно легко. Чтобы продемонстрировать это, мы добавляем элемент "17" перед текущим элементом "9".



Обратная ссылка с “9” на “3” удаляется и заменяется обратной ссылкой на новый элемент “17”.


новый элемент 17

Из узла с “17” мы делаем прямую ссылку на “9”.


новая прямая ссылка

Затем мы помещаем обратную ссылку с "17" на "3".


обратная ссылка на 3

Старая ссылка с “3” на “9” заменяется ссылкой с “3” на “17”.


заменена старая ссылка

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

public class Node<E> {
    private final E item;
    private final Node<E> previous;
    private final Node<E> next;

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

    public E item() {
        return item;
    }

    public Node<E> previous() {
        return previous;
    }

    public Node<E> next() {
        return next;
    }
[...]
}

Класс Linked List

public class LinkedList<E> {
    private Node<E> currentNode;
    private Node<E> head;

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

Давайте рассмотрим выдержки из кода в списках 2-3 узла односвязного списка и его использование в классе LinkedList. У нас есть метод извлечения элемента, содержащегося в узле в item() и способ перехода к следующему узлу с помощью next(). Узел двусвязного списка очень похож, но немного сложнее в том, что он имеет ссылку на предыдущий узел. Связанный список обычно содержит ссылку на начало списка. Методы класса Node используются для навигации по списку.

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

Дополнительная информация

Класс LinkedList реализует и формирует основу многих других структур данных, некоторые из которых включают список, очередь, Стек и двойные очереди, также известные как Deque.

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

Списки обычно требуют произвольного доступа к своим элементам, поэтому список с двойной связью является лучшим выбором. В очереди “первый вход-первый выход” (FIFO) новые элементы вставляются в хвост и удаляются из головы очереди, и произвольный доступ не требуется. Для очередей лучшим выбором являются односвязные списки.

Стек обеспечивает порядок операций “последний вход-первый выход” (LIFO). Элементы добавляются и удаляются из верхней части стека, что делает его еще проще, чем очередь. Поэтому односвязные списки лучше подходят для стеков. Двусторонняя очередь или deque - это очень динамичная структура данных. Он обеспечивает доступ, добавление и удаление с обоих концов. Это делает список с двойной связью идеальным выбором.