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

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

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

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

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

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

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

Можно выделить такие основные операции с односвязными списками: 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;};

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

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

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

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

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

Цикл while разрывается. И в конце мы назначаем для currentNode.nextnode, увеличиваем _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. В виде аргумента передается существующая (не первая) позиция.

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

При втором случае обрабатывается удаление первого узла в списке, который также будет 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) — удаляет узел из списка.

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

Для реализации мы создадим конструктор с именем 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;};

Заключение

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

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *