Очищение некоторых туманов, окружающих связанные списки

Что касается Javascript, большая часть этой информации не зависит от языка.

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

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

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

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

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

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

Память. Элементы в массивах хранятся в памяти последовательно или рядом. Связанные списки не хранятся непрерывно. Вместо этого каждый элемент в связанном списке содержит сам элемент/данные, а также указатель (или ссылку) на следующий элемент, который хранится в другом месте в памяти машины.

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

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

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

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

Работа со связанными списками

Для начала давайте рассмотрим настройку связанного списка.

class LinkedListNode {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

Мы видим, что начинаем с нашего конструктора и двух свойств; data и next. data — это, конечно, данные, содержащиеся в этом узле, а next — наш указатель на следующий узел. next изначально имеет значение null, потому что null всегда будет отмечать конец связанного списка. Это станет более ясно через несколько мгновений.

Вот один из довольно подробных способов построения списка.

// create the first node
const head = new LinkedListNode(1);

// add a second node
head.next = new LinkedListNode(2);

// add a third node
head.next.next = new LinkedListNode(3);

Стандартной практикой является называть первый узел head. Затем установите узлы, следующие за головой, путем объединения next вызовов.

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

let current = head;

while (current.next !== null) {
    current = current.next;
}
current.next = newData;

Или, если мы хотим изменить каждый узел в нашем связанном списке, мы можем написать что-то вроде кода ниже.

let current = head;

while (current !== null) {
    // perform some function
    current = current.next;
}

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

В заключении

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

Очищение некоторых туманов, окружающих связанные списки