Алгоритмы и структуры данных

Структура данных: связный список

В данной статье мы рассмотрим еще одну популярную реализацию списка — связный список.

Связный список — это коллекция элементов, порядок которых не зависит от положения в памяти. В ней каждый элемент — так называемая нода — имеет указатель на следующий.

Связные списки наравне с массивами являются базовыми структурами данными, которые позволяют нам реализовать более сложные структуры данных.

Идея

Элементы связного списка называются «нодами». Идея связного списка заключается в том, чтобы хранить данные в нодах, а каждая нода указывает на следующую. Указатель на следующий элемент называется «next pointer». Первый элемент списка называется «головой» (head), а последний элемент списка — «хвостом». Мы знаем, что элемент последний по тому признаку, что такой элемент содержит null в качестве указателя на следующую ноду.

Односвязные и двусвязные списки

Выше мы обсуждали односвязные списки: в элементах такого списка имеется только одна связь — на следующий элемент. Однако, мы также можем хранить указатель на предыдущий элемент («previous pointer») — такой список называется двусвязным.

Двусвязный список позволяет нам дополнительно:

  • Итерироваться по списку в обратном порядке, так как мы имеем указатель на предыдущий элемент
  • Эффективно производить удаление ноды, зная только ее адрес. Чтобы сделать то же самое в односвязном списке, нам пришлось бы итерироваться с начала списка для нахождения предыдущего элемента, что из константного времени превращается в O(n). В том числе это помогает производить удаление последнего элемента списка

Реализация

Итак, для односвязного списка мы определим следующие операции:

  • Вставка элемента в начало списка
  • Вставка элемента в конец списка
  • Вставка элемента после определенной ноды
  • Удаление элемента с начала списка
  • Удаление элемента после определенной ноды

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

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

Определим структуру ноды:

    public static class Node {
        E data;
        Node next;

        Node(E data) {
            this.data = Objects.requireNonNull(data, "Data must not be null!");
            next = null;
        }

        @Override
        public String toString() {
            return "Node{" +
                "data=" + data +
                '}';
        }
    }

Создадим класс для односвязного списка и структуру ноды:

public class SinglyLinkedList {

    private Node head; // голова списка
    private Node tail; // хвост списка
    private int size; // количество элементов в списке

    public SinglyLinkedList() {
        head = tail = null;
    }
}

Реализуем вставку в начало списка:

    public Node insertFirst(E e) {
        Node newNode = new Node<>(e);
        Node head = this.head;
        if (head != null) {
            newNode.next = head;
            this.head = newNode; // смещаем голову списка
        } else {
            this.head = this.tail = newNode; // пустой список
        }
        ++size;
        return newNode;
    }

Вставка после определенного элемента выглядит следующим образом:

CPT-LinkedLists-addingnode.svg

В ноде, за которой надо вставить новый элемент, мы выставляем указатель на новый элемент, а новый элемент должен указывать на ранее следовавшую впереди ноду:

    public Node insertAfter(Node node, E e) {
        Node newNode = new Node<>(e);
        newNode.next = node.next;
        node.next = newNode;
        if (node == tail) { // вставка в конец списка
            tail = newNode; // смещаем хвост
        }
        ++size;
        return newNode;
    }

Вставка в конец списка предпологает выставление ссылки на новую ноду в хвосте с последующим смещением хвоста:

    public Node insertLast(E e) {
        Node node = new Node<>(e);
        Node tail = this.tail;
        if (tail != null) {
            tail.next = node;
            this.tail = node;
        } else {
            this.head = this.tail = node;
        }
        ++size;
        return node;
    }

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

    public Node removeFirst() {
        Node head = this.head;
        if (head == null) { // empty list
            return null;
        }
        if (head == tail) { // list composed of 1 element
            this.head = this.tail = null;
            return head;
        }

        // replace head with successor
        Node headSucc = head.next;
        this.head = headSucc;
        return head;
    }

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

Схема удаления:

CPT-LinkedLists-deletingnode.svg

и реализация:

    public boolean removeAfter(Node node) {
        Node obsoleteNode = node.next;
        // no node to delete (end of the list)
        if (obsoleteNode == null) {
            return true;
        }
        node.next = obsoleteNode.next;
        if (obsoleteNode == tail) { // если удаляемая нода - хвост списка, смещаем хвост на предыдущую ноду
            tail = node;
        }
        --size;
        return true;
    }

Реализация двусвязного списка

Двусвязный список дополняется следующими операциями:

  • Вставка элемента перед указанной нодой
  • Удаление ноды по ее адресу — больше нет необходимости в указании ноды, перед или после которой необходимо удалить элемент
  • Удаление последнего элемента

В двусвязном списке указатель prev в голове списка указывает на null, также как и указаатель next в хвосте списка. В остальном реализация остается почти такой же, кроме того что теперь нам необходимо обслуживать указатели на предыдущие элементы:

public class DoublyLinkedList {
    private Node head;
    private Node tail;
    private int size;

    public DoublyLinkedList() {
        head = tail = null;
    }

    public Node addLast(E e) {
        Node node = new Node<>(e);
        Node tail = this.tail;
        if (tail != null) {
            tail.next = node;
            node.prev = tail;
            this.tail = node;
        } else {
            this.head = this.tail = node;
        }
        size++;
        return node;
    }

    public Node addBefore(Node node, E e) {
        Node newNode = new Node<>(e);
        newNode.prev = node.prev;
        newNode.next = node;
        if (node.prev == null) { // если переданная нода является головой, то сместить голову на новый элемент
            this.head = newNode;
        }
        node.prev = newNode;
        size++;
        return newNode;
    }

    public Node addAfter(Node node, E e) {
        Node newNode = new Node<>(e);
        newNode.next = node.next;
        newNode.prev = node;
        if (node.next == null) { // если переданная нода является хвостом, то сместить хвост на новый элемент
            this.tail = newNode;
        }
        node.next = newNode;
        ++size;
        return newNode;
    }

    public boolean remove(Node node) {
        if (node.prev != null) {
            node.prev.next = node.next; // предыдущий элемент теперь указывает ноду, следующую за удаляемой
        } else {
            this.head = node.next; // если переданная нода является головой, то смещаем голову
        }
        if (node.next != null) {
            node.next.prev = node.prev; // следующий элемент теперь указывает на ноду, предшествующую удаляемой
        } else {
            this.tail = node.prev; // если переданная нода является хвостом, то смещаем хвост
        }
        ++size;
        return true;
    }

    public Node removeFirst() {
        Node head = this.head;
        if (head == null) { // пустой список
            return null;
        }
        if (head == tail) { // список состоит из 1 элемента
            this.head = this.tail = null;
            return head;
        }

        // заменить голову следующим элементом
        Node headSucc = head.next;
        headSucc.prev = null;
        this.head = headSucc;
        return head;
    }

    public Node removeLast() {
        Node tail = this.tail;
        if (tail == null) { // пустой список
            return null;
        }
        if (tail == this.head) { // список состоит из 1 элемента
            this.head = this.tail = null;
            return tail;
        }

        // заменить хвост предшествующим элементом
        Node tailPred = tail.prev;
        tailPred.next = null;
        this.tail = tailPred;
        return tail;
    }

    public static class Node {
        E key;
        Node prev, next;

        Node(E key) {
            this.key = key;
            prev = next = null;
        }

        @Override
        public String toString() {
            return "Node{" +
                "key=" + key +
                '}';
        }
    }
}

Сравнение связных список с массивами

Давайте сравним временную сложность операций в массивах и связных списках:

Операция/
Структура данных
Singly-Linked ListDoubly-Linked ListArrayDynamic Array
ИндексацияO(n)O(n)O(1)O(1)
Вставка/удаление с началаO(1)O(1)O(n)
Вставка/удаление в серединеO(1), если известен элемент после которого необходимо вставить/удалить, иначе — O(n)O(1), если известен элемент после которого необходимо вставить/удалить, иначе — O(n)O(n)
Вставка/удаление в концеВставка — O(1)
Удаление — O(n)
O(1)O(1)
Сравнение временных сложностей операций массива и связного списка

Преимущества

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

Недостатки

  • Связные списки реализуют только последовательный доступ (Sequential Access), не предоставляя произвольного доступа (Random Access)
  • Индексация производится за линейное время (линейный поиск)
  • Вставка и удаление по индексу, соответственно, тоже стоит O(n)
  • Связные списки используют очень много памяти, так как имеют много overhead, ведь нам приходится хранить указатели на следующие ноды, а указатели занимают достаточно памяти — 4 байта для 32-битной и 8 байт для 64-битной системы. Если связный список используется для таких типов данных, как boolean или char, то полезное занятое пространство оказывается даже меньше, чем пространство, занятое overhead
  • Плохой locality of reference и, соответственно, плохая утилизация кэша из-за того что элементы разрознены в памяти, то есть не расположены последовательно

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

В Java же даже сам создатель связных список задается вопросом, использует ли их вообще кто-то?

Добавить комментарий

Ваш адрес email не будет опубликован.