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

12 января 2018

Две из наиболее часто используемых структур данных в информатике - это односвязный список и двусвязный список.

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

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

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

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

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

Теперь, когда у нас есть концептуальная модель односвязного списка, давайте рассмотрим действия односвязного списка.

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

Поскольку односвязный список содержит узлы, которые могут быть отдельным конструктором из односвязного списка, мы описываем операции обоих конструкторов: Node и SinglyList.

Узел

данные сохраняют значение. следующий указывает на следующий узел в списке.

SinglyList

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

Внедрение односвязного списка

Для нашей реализации мы сначала определим конструктор с именем Node, а затем конструктор с именем SinglyList.

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

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

Затем нам нужно определить SinglyList:

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

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

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

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

1 из 3: добавить (значение)

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

SinglyList.prototype.add = function(value) {
    var node = new Node(value),
        currentNode = this.head;
    // 1st use-case: an empty list
    if (!currentNode) {
        this.head = node;
        this._length++;
        return node;
    }
    // 2nd use-case: a non-empty list
    while (currentNode.next) {
        currentNode = currentNode.next;
    }
    currentNode.next = node;
    this._length++;
    return node;
};

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

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

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

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

Если ответ отрицательный, мы назначаем узел currentNode.next и возвращаемый узел.

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

Временной цикл прерывается. Наконец, мы назначаем node currentNode.next, мы увеличиваем _length на единицу, а затем возвращаем узел.

2 из 3: searchNodeAt (позиция)

Теперь мы можем добавлять узлы в наш список, но мы не можем искать узлы в определенных позициях в нашем списке. Давайте добавим эту функциональность и создадим метод с именем 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.'};
    // 1st use-case: an invalid position
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
    // 2nd use-case: a valid position
    while (count < position) {
        currentNode = currentNode.next;
        count++;
    }
    return currentNode;
};

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

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

Когда цикл окончательно разрывается, возвращается currentNode.

3 из 3: 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;
    // 1st use-case: an invalid positio
    if (position < 0 || position > length) {
        throw new Error(message.failure);
    }
    // 2nd use-case: the first node is removed
    if (position === 1) {
        this.head = currentNode.next;
        deletedNode = currentNode;
        currentNode = null;
        this._length--;
        return deletedNode;
    }
    // 3rd use-case: any other node is removed
    while (count < position) {
        beforeNodeToDelete = currentNode;
        nodeToDelete = currentNode.next;
        count++;
    }
    beforeNodeToDelete.next = nodeToDelete.next;
    deletedNode = nodeToDelete;
    nodeToDelete = null;
    this._length--;
    return deletedNode;
};

Наша реализация remove (position) включает три варианта использования:

    Недопустимая позиция передается в качестве аргумента. Позиция одного (глава списка) передается в качестве аргумента. В качестве аргумента передается существующее положение (не первая позиция).

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

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

    head переназначается в currentNode.next. deletedNode указывает на currentNode. currentNode присваивается значение null. Уменьшение длины нашего списка на единицу. deletedNode возвращается.

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

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

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

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

Полная реализация нашего списка находится здесь:

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;
    // 1st use-case: an empty list
    if (!currentNode) {
        this.head = node;
        this._length++;
        return node;
    }
    // 2nd use-case: a non-empty list
    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.'};
    // 1st use-case: an invalid positio
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
    // 2nd use-case: a valid positio
    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;
    // 1st use-case: an invalid positio
    if (position < 0 || position > length) {
        throw new Error(message.failure);
    }
    // 2nd use-case: the first node is removed
    if (position === 1) {
        this.head = currentNode.next;
        deletedNode = currentNode;
        currentNode = null;
        this._length--;
        return deletedNode;
    }
    // 3rd use-case: any other node is removed
    while (count < position) {
        beforeNodeToDelete = currentNode;
        nodeToDelete = currentNode.next;
        count++;
    }
    beforeNodeToDelete.next = nodeToDelete.next;
    deletedNode = nodeToDelete;
    nodeToDelete = null;
    this._length--;
    return deletedNode;
};

От Singly to Doubly

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

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

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

Doubly-Linked List

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

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

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

Наш список будет включать два конструктора: Node и DoublyList. Опишите их операции.

Узел

данные сохраняют значение. следующий указывает на следующий узел в списке. предыдущие указывает на предыдущий узел в списке.

DoublyList

_length возвращает количество узлов в списке. head назначает узел в качестве главы списка. tail назначает узел как хвост списка. add (value) добавляет узел в список. searchNodeAt (позиция) ищет узел в n-позиции в нашем списке. remove (position) удаляет узел из списка.

Выполнение двусвязного списка

Пусть написано код!

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

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

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

Затем нам нужно реализовать DoublyList и добавить три свойства: _length, head и tail. В отличие от односвязного списка, двусвязный список имеет ссылку как на начало списка, так и на конец списка. Поскольку каждый экземпляр DoublyList создается без узлов, значения по умолчанию head и tail устанавливаются в нуль.

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

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

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

1 из 3: добавить (значение)

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;
};

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

2 из 3: searchNodeAt (позиция)

Реализация searchNodeAt (позиция) идентична односвязному списку. Если вы забыли, как его реализовать, я включил его ниже:

DoublyList.prototype.searchNodeAt = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: 'Failure: non-existent node in this list.'};
    // 1st use-case: an invalid position
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
    // 2nd use-case: a valid position
    while (count < position) {
        currentNode = currentNode.next;
        count++;
    }
    return currentNode;
};

3 из 3: удалить (положение)

Этот метод будет наиболее сложным для понимания. Я покажу код, а потом объясню.

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;
    // 1st use-case: an invalid positio
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
    // 2nd use-case: the first node is removed
    if (position === 1) {
        this.head = currentNode.next;
        // 2nd use-case: there is a second node
        if (!this.head) {
            this.head.previous = null;
        // 2nd use-case: there is no second node
        } else {
            this.tail = null;
        }
    // 3rd use-case: the last node is removed
    } else if (position === this._length) {
        this.tail = this.tail.previous;
        this.tail.next = null;
    // 4th use-case: a middle node is removed
    } 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) обрабатывает четыре варианта использования:

    Позиция, передаваемая как аргумент remove (position), не существует. В этом случае мы выдаем ошибку. Позиция, передаваемая в качестве аргумента remove (position), является первым узлом (заголовком) списка. Если это так, мы назначим deleteNode на голову, а затем переназначим голову на следующий узел в списке. В настоящий момент мы должны рассмотреть, имеет ли наш список более одного узла. Если ответ отрицательный, голова будет назначена нулевому значению, и мы войдем в if-часть инструкции if. В теле if, мы также должны установить хвост в нуль - другими словами, мы возвращаемся к исходному состоянию пустого двусвязного списка. Если мы удаляем первый узел в списке и у нас есть более одного узла в нашем списке, мы вводим раздел else нашего оператора if-else. В этом случае мы должны правильно установить предыдущее свойство головы в значение null - нет узлов перед заголовком списка. Позиция, передаваемая как аргумент remove (position), является хвостом списка. Во-первых, deletedNode присваивается хвосту. Во-вторых, хвост переназначается на узел, предшествующий хвосту. В-третьих, новый хвост не имеет узла после него и требует, чтобы его значение было установлено равным нулю. Многое происходит здесь, поэтому я сосредоточусь на логике больше, чем на каждой строке кода. Мы прерываем цикл while, когда currentNode указывает на узел в позиции, передаваемой как аргумент для удаления (позиции). В этот момент мы переназначаем значение beforeNodeToDelete.next к узлу после nodeToDelete и, наоборот, переназначаем значение afterNodeToDelete.previous для узла до nodeToDelete. Другими словами, мы удаляем указатели на удаленный узел и переназначаем их на правильные узлы. Затем мы назначаем deletedNode nodeToDelete. Наконец, мы присваиваем 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.'};
    // 1st use-case: an invalid positio
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
    // 2nd use-case: a valid positio
    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;
    // 1st use-case: an invalid positio
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
    // 2nd use-case: the first node is removed
    if (position === 1) {
        this.head = currentNode.next;
        // 2nd use-case: there is a second node
        if (!this.head) {
            this.head.previous = null;
        // 2nd use-case: there is no second node
        } else {
            this.tail = null;
        }
    // 3rd use-case: the last node is removed
    } else if (position === this._length) {
        this.tail = this.tail.previous;
        this.tail.next = null;
    // 4th use-case: a middle node is removed
    } 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;
};

Заключение

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