Структурирование данных с помощью JavaScript: Односвязные и двусвязные списки

0 ∞ 5

Одними из основных структур данных, рассматриваемых в информатике, являются односвязные и двусвязные списки.

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

Содержание

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

В информатике односвязный список представляет собой структуру данных, которая содержит последовательность связанных узлов. Каждый узел содержит данные и указатель, который может указывать на другой узел.

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

Операции с односвязными списками

Можно выделить такие основные операции с односвязными списками: Node и SinglyList.

Node

  • data - здесь хранятся значения;
  • next - указывает на следующий узел в списке.

SinglyList

  • _length - извлекает количество узлов в списке;.
  • head - определяет узел, как головной элемент списка;
  • add(value) - добавляет в список узел;
  • searchNodeAt(position) - ищет в списке узел на n-ной позиции;
  • remove(position) - удаляет узел из списка.

Реализация односвязных списков

Для конкретного примера реализации мы сначала определим конструктор с именем Node, а затем конструктор с именем SinglyList. Каждый экземпляр узла должен «уметь» хранить данные и указывать на другой узел. Чтобы добавить эти функции, мы создадим два свойства: data и next, соответственно:

function Node(data) {
    this.data = data;
    this.next = null;
}

Далее, мы должны определить SinglyList:

function SinglyList() {
    this._length = 0;
    this.head = null;
}

Каждый экземпляр SinglyList будет иметь два свойства: _length и head. Первое устанавливает число узлов в списке; второй - указывает на головной элемент списка (узел в начале списка). Так как каждый новый экземпляр SinglyList не содержит узла, то значение по умолчанию для head и для _length будет null.

Методы односвязных списков

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

Метод add(value)

Теперь реализуем функционал для добавления узлов в список:

SinglyList.prototype.add = function(value) {
    var node = new Node(value),
        currentNode = this.head;

    // 1-ый случай: пустой список
    if (!currentNode) {
        this.head = node;
        this._length++;

        return node;
    }

    // 2-ой случай: не пустой список
    while (currentNode.next) {
        currentNode = currentNode.next;
    }

    currentNode.next = node;

    this._length++;

    return node;
};
Структурирование данных с помощью JavaScript: Что такое структура данных?

Добавление узла в список включает в себя множество этапов. Мы используем аргумент для add(value), чтобы создать новый экземпляр Node, который присваивается переменной с именем node. Мы также объявляем переменную с именем currentNode и инициализируем ее в _head нашего списка. Если в списке нет узлов, тогда значение head будет null.

После этого мы обрабатываем в коде два возможных случая. В первом случае рассматривается добавление узла в пустой список. Если head не указывают на узел, тогда node назначается головным элементом списка, длина списка увеличивается на один узел, и возвращается node.

Во втором случае рассматривается добавление узла в непустой список. Мы входим в цикл while, и во время каждой итерации проверяем, указывает ли currentNode.next на другой узел. Во время первой итерации currentNode всегда указывает на головной элемент списка.

Если нет, мы назначаем для currentNode.next - node и возвращаем node.

Если ответ да, мы входим в тело цикла while. В теле цикла мы переопределяем currentNode как currentNode.next до тех пор, пока currentNode.next не перестанет указывать на другой узел. Другими словами, currentNode указывает на последний узел списка.

Цикл while разрывается. И в конце мы назначаем для currentNode.next - node, увеличиваем _length на один элемент, а затем возвращаем node.

Метод searchNodeAt(position)

Теперь мы можем добавлять узлы в список, но не можем производить поиск узлов на определенной позиции в списке. Для этого создадим метод с именем searchNodeAt(position), который принимает аргумент с именем position. Этот аргумент должен быть целым числом, которое указывает на узел на n-ной позиции в списке:

SinglyList.prototype.searchNodeAt = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: 'Failure: non-existent node in this list.'};

    // 1-ый случай: неверная позиция 
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }

    // 2-ой случай: верная позиция 
    while (count < position) {
        currentNode = currentNode.next;
        count++;
    }

    return currentNode;
};

Оператор if проверяет на соответствие первому случаю: в качестве аргумента передается неверная позиция.

Если индекс, переданный в searchNodeAt(position), верен, тогда мы переходим ко второму случаю - циклу while. Во время каждой итерации цикла while, currentNode, который сначала всегда указывает на head, переназначается, как следующий узел в списке до тех пор, пока количество итераций не станет равно индексу позиции. Тогда цикл разрывается, и возвращается currentNode.

Метод remove(position)

Последний метод, который мы создадим, называется remove(position):

SinglyList.prototype.remove = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 0,
        message = {failure: 'Failure: non-existent node in this list.'},
        beforeNodeToDelete = null,
        nodeToDelete = null,
        deletedNode = null;

    // 1-ый случай: неверная позиция
    if (position < 0 || position > length) {
        throw new Error(message.failure);
    }

    // 2-ой случай: первый узел удален
    if (position === 1) {
        this.head = currentNode.next;
        deletedNode = currentNode;
        currentNode = null;
        this._length--;

        return deletedNode;
    }

    // 3-ий: все прочие узлы удалены
    while (count < position) {
        beforeNodeToDelete = currentNode;
        nodeToDelete = currentNode.next;
        count++;
    }

    beforeNodeToDelete.next = nodeToDelete.next;
    deletedNode = nodeToDelete;
    nodeToDelete = null;
    this._length--;

    return deletedNode;
};

Реализация remove(position) включает в себя три возможных варианта:

  1. В качестве аргумента передается неверная позиция;
  2. В качестве аргумента передается первая позиция (head списка);
  3. В качестве аргумента передается существующая (не первая) позиция.
Структурирование данных с помощью JavaScript: Дерево

Первый и второй варианты являются самыми простыми. По первому сценарию, если список пуст или была передана несуществующая позиция, выдается ошибка.

При втором случае обрабатывается удаление первого узла в списке, который также является head. Если это так, то применяется следующая логика:

  1. head устанавливается в currentNode.next;
  2. deletedNode указывает на currentNode;
  3. currentNode устанавливается в null;
  4. _length списка уменьшается на один;
  5. Возвращается deletedNode.

Третий сценарий самый трудный для понимания. Эта сложность возникает из-за необходимости отслеживания двух узлов во время каждой итерации цикла while. Во время каждой итерации цикла мы отслеживаем элемент, находящийся перед узлом, который должен быть удален, и элемент, который должен быть удален. Когда While достигает позиции узла, который мы хотим удалить, цикл завершается.

К этому моменту мы учитываем ссылки на три узла: beforeNodeToDelete, nodeToDelete и deletedNode. Перед тем как удалить nodeToDelete, мы должны установить его значение next следующему значению beforeNodeToDelete. Если вы не до конца понимаете, в чем цель этого действия, вспомните, что у нас есть список связанных узлов; удаление любого узла разрушает связь, которая должна быть непрерывной от первого узла в списке до последнего.

Далее мы присваиваем значение deletedNode в nodeToDelete. Затем мы устанавливаем значение nodeToDelete на null, уменьшаем длину списка на один элемент и возвращаем deletedNode.

Полная реализация односвязного списка

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

function Node(data) {
    this.data = data;
    this.next = null;
}

function SinglyList() {
    this._length = 0;
    this.head = null;
}

SinglyList.prototype.add = function(value) {
    var node = new Node(value),
        currentNode = this.head;

    // 1-ый случай: пустой список
    if (!currentNode) {
        this.head = node;
        this._length++;

        return node;
    }

    // 2-ой случай: непустой список
    while (currentNode.next) {
        currentNode = currentNode.next;
    }

    currentNode.next = node;

    this._length++;

    return node;
};

SinglyList.prototype.searchNodeAt = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: 'Failure: non-existent node in this list.'};

    // 1-ый случай: неверная позиция
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }

    // 2-ой случай: верная позиция
    while (count < position) {
        currentNode = currentNode.next;
        count++;
    }

    return currentNode;
};

SinglyList.prototype.remove = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 0,
        message = {failure: 'Failure: non-existent node in this list.'},
        beforeNodeToDelete = null,
        nodeToDelete = null,
        deletedNode = null;

    // 1-ый случай: неверная позиция
    if (position < 0 || position > length) {
        throw new Error(message.failure);
    }

    // 2-ой случай: первый узел удален
    if (position === 1) {
        this.head = currentNode.next;
        deletedNode = currentNode;
        currentNode = null;
        this._length--;

        return deletedNode;
    }

    // 3-ий случай: все другие узлы удалены
    while (count < position) {
        beforeNodeToDelete = currentNode;
        nodeToDelete = currentNode.next;
        count++;
    }

    beforeNodeToDelete.next = nodeToDelete.next;
    deletedNode = nodeToDelete;
    nodeToDelete = null;
    this._length--;

    return deletedNode;
};

От односвязных к двусвязным

Мы завершили реализацию односвязного списка. Теперь мы можем использовать структуру данных, которая добавляет, удаляет и ищет в списке узлы, которые располагаются не на смежных позициях.

Сейчас все наши операции стартуют с начала списка и продвигаются дальше к концу. Другими словами, они являются однонаправленными.

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

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

Операции двусвязных списков

Наш список будет включать в себя два конструктора: Node и DoublyList. Возможные операции:

Node

  • data - здесь хранятся значения;
  • next - указывает на следующий узел в списке;
  • previous - указывает на предыдущий узел в списке.

DoublyList

  • _length - извлекает количество узлов в списке;
  • head - назначает узел в качестве головного элемента списка;
  • tail - назначает узел в качестве конечного элемента списка;
  • add(value) - добавляет узел в список;
  • searchNodeAt(position) - ищет узел на n-ной позиции в списке;
  • remove(position) - удаляет узел из списка.
Структурирование данных с помощью JavaScript: Стек и очередь

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

Для реализации мы создадим конструктор с именем Node:

function Node(value) {
    this.data = value;
    this.previous = null;
    this.next = null;
}

Для создания двунаправленной обработки двусвязного списка нам нужны свойства, которые указывают в двух направлениях. Эти свойства мы назовем previous и next.

Далее нам необходимо реализовать DoublyList и добавить три свойства: _length, head и tail. В отличие от односвязного, двусвязный список содержит ссылку, как на начало, так и на конец списка. Так как каждый экземпляр DoublyList изначально создается без узлов, то значения по умолчанию для head и tail будут установлены на null:[/HTML]

function DoublyList() {
    this._length = 0;
    this.head = null;
    this.tail = null;
}https://www.internet-technologies.ru/engine/admin_panel/js_lib/external/bueditor/icons/b.png

Методы двусвязного списка

Рассмотрим следующие методы: add(value), remove(position) и searchNodeAt(position). Все эти методы мы использовали для односвязного списка, но теперь их нужно переписать для двунаправленной обработки.

Метод add(value)

DoublyList.prototype.add = function(value) {
    var node = new Node(value);

    if (this._length) {
        this.tail.next = node;
        node.previous = this.tail;
        this.tail = node;
    } else {
        this.head = node;
        this.tail = node;
    }

    this._length++;

    return node;
};

В этом методе у нас реализованы два сценария. Во-первых, если список пуст, тогда в качестве head и tail мы назначаем добавляемый узел. Во-вторых, если список содержит узлы, тогда мы находим конечный элемент и устанавливаем добавляемый узел в качестве tail.next. Также нам нужно задать для нового конечного элемента двунаправленную обработку. Другими словами, нам необходимо установить первоначальный конечный элемент в качестве tail.previous.

Метод searchNodeAt(position)

Реализация searchNodeAt(position) идентична односвязному списку:

DoublyList.prototype.searchNodeAt = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: 'Failure: non-existent node in this list.'};

    // 1-ый случай: неверная позиция 
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }

    // 2-ой случай: верная позиция 
    while (count < position) {
        currentNode = currentNode.next;
        count++;
    }

    return currentNode;
};

Метод remove(position)

Этот метод наиболее сложный для понимания. Я сначала приведу код, а затем поясню его:

DoublyList.prototype.remove = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: 'Failure: non-existent node in this list.'},
        beforeNodeToDelete = null,
        nodeToDelete = null,
        deletedNode = null;

    // 1-ый случай: неверная позиция
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }

    // 2-ой случай: первый узел удален
    if (position === 1) {
        this.head = currentNode.next;

        // 2-ой случай: существует второй узел
        if (!this.head) {
            this.head.previous = null;
        // 2-ой случай: второго узла не существует
        } else {
            this.tail = null;
        }

    // 3-ий случай: последний узел удален
    } else if (position === this._length) {
        this.tail = this.tail.previous;
        this.tail.next = null;
    // 4-ый случай: средний узел удален
    } else {
        while (count < position) {
            currentNode = currentNode.next;
            count++;
        }

        beforeNodeToDelete = currentNode.previous;
        nodeToDelete = currentNode;
        afterNodeToDelete = currentNode.next;

        beforeNodeToDelete.next = afterNodeToDelete;
        afterNodeToDelete.previous = beforeNodeToDelete;
        deletedNode = nodeToDelete;
        nodeToDelete = null;
    }

    this._length--;

    return message.success;
};

remove(position) обрабатывает четыре возможных случая:

  1. Позиция, передаваемая в качестве аргумента remove(position), не существует. В этом случае, мы выдаем ошибку;
  2. Позиция, передаваемая в качестве аргумента remove(position), является первым узлом (head) списка. Если это так, то мы устанавливаем head в качестве deletedNode, а затем в качестве head назначаем следующий узел в списке. Далее мы должны проверить, содержит ли наш список более одного узла. Если нет, то head будет установлен на null и мы переходим к части if оператора if-else. В теле if мы также должны установить tail на null. Таким образом, мы возвращаем список в исходное состояние пустого двусвязного списка. Если мы удаляем первый узел в списке и у нас остается более одного узла, то мы входим в раздел else оператора if-else. В этом случае мы устанавливаем свойство previous для head на null, потому что у нас нет узлов перед головным элементом списка;
  3. Позиция, передаваемая в качестве аргумента remove(position), является конечным элементом списка. Во-первых, tail устанавливается в качестве deletedNode. Во-вторых, в качестве tail переустанавливается узел, расположенный перед конечным элементом списка. В-третьих, после нового конечного элемента не будет узлов, расположенных после него, и его свойство next должно быть равно null;
  4. Мы разрываем цикл while, как только currentNode указывает на узел, расположенный в позиции, передаваемой в качестве аргумента remove(position). После этого мы переназначаем значение beforeNodeToDelete.next на узел, расположенный после nodeToDelete и, наоборот, мы переназначаем значение afterNodeToDelete.previous на узел, расположенный перед nodeToDelete. Другими словами, мы убираем ссылки на удаленный узел и переназначаем их на правильные узлы. Далее мы устанавливаем nodeToDelete в качестве значения deletedNode. Затем мы устанавливаем значение nodeToDelete на null.

В конце мы уменьшаем длину списка и возвращаем deletedNode.

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

Вот полная реализация:

Function Node(value) {
    this.data = value;
    this.previous = null;
    this.next = null;
}

function DoublyList() {
    this._length = 0;
    this.head = null;
    this.tail = null;
}

DoublyList.prototype.add = function(value) {
    var node = new Node(value);

    if (this._length) {
        this.tail.next = node;
        node.previous = this.tail;
        this.tail = node;
    } else {
        this.head = node;
        this.tail = node;
    }

    this._length++;

    return node;
};

DoublyList.prototype.searchNodeAt = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: 'Failure: non-existent node in this list.'};

    // 1-ый случай: неверная позиция
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }

    // 2-ой случай: верная позиция
    while (count < position) {
        currentNode = currentNode.next;
        count++;
    }

    return currentNode;
};

DoublyList.prototype.remove = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: 'Failure: non-existent node in this list.'},
        beforeNodeToDelete = null,
        nodeToDelete = null,
        deletedNode = null;

    // 1-ый случай: неверная позиция
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }

    // 2-ой случай: первый узел удален
    if (position === 1) {
        this.head = currentNode.next;

        // 2-ой случай: существует второй узел
        if (!this.head) {
            this.head.previous = null;
        // 2-ой случай: второго узла не существует
        } else {
            this.tail = null;
        }

    // 3-ий случай: последний узел удален
    } else if (position === this._length) {
        this.tail = this.tail.previous;
        this.tail.next = null;
    // 4-ый случай: средний узел удален
    } else {
        while (count < position) {
            currentNode = currentNode.next;
            count++;
        }

        beforeNodeToDelete = currentNode.previous;
        nodeToDelete = currentNode;
        afterNodeToDelete = currentNode.next;

        beforeNodeToDelete.next = afterNodeToDelete;
        afterNodeToDelete.previous = beforeNodeToDelete;
        deletedNode = nodeToDelete;
        nodeToDelete = null;
    }

    this._length--;

    return message.success;
};

Заключение

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

Сергей Бензенкоавтор-переводчик статьи «Data Structures With JavaScript: Singly-Linked List and Doubly-Linked List»