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

А зачем вообще эти структуры данных?

Многие начинающие (да и не только начинающие) программисты могут даже не знать, что существуют структуры данных, кроме встроенных в их любимый ЯП. Проработав несколько лет сначала с использованием Ruby, а затем и JavaScript, я был в их числе. Но в какой-то момент…говоря коротка - понадобились. И если вы считаете, что вам все эти алгоритмы и структуры данных даром не нужны, то…просто добавьте эту статью в закладки, вернетесь, когда будет надо.

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

Собственно, к теме

Связный список - это базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит значение и ссылку на следующий узел. Первый элемент списка - Head, последний - Tail, он ссылается на NULL.

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

Двойной связанный список - это список, в котором узлы содержат ссылки еще и на предыдущий элемент.

Реализация

Этот раздел также делал в своих эгоистичных целях.

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

Итак…

Базовым элементом списка является узел (Node) с полями value, next и prev (последнее - для двунаправленного списка). Реализуем двунаправленный список, из которого при необходимости можно легко сделать простой, просто убрав из кода указатели prev.

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
		this.prev = null;
    }
}

У самого списка также есть начальный набор свойств:

• head - это “точка входа”, начальный элемент списка

• tail - конечный элемент списка

• length - количество элементов списка. Необязательный элемент, но иногда бывает необходим. Да и, пожалуй, одно значение много памяти не отнимет.

class DoubleLinkedList {
    constructor(value) {
        this.head = new Node(value);
        this.tail = this.head;
        this.length = 1;
    }
}

Методы

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

Базовыми “умениями” нашего списка будет добавление элементов в конец (append) и в начало (prepend) списка.

// Методы внутри класса DoubleLinkedList

// Добавление узла в конец списка
append(value) {
    const newNode = new Node(value);
    newNode.prev = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;
    return this;
}

// Добавление узла в начало списка
prepend(value) {
    const newNode = new Node(value);
    this.head.prev = newNode;
    newNode.next = this.head;
    this.head = newNode;
    this.length++;
    return this;
}

Стоит отметить, что применение связанного списка вместо массива весьма оправдано как раз в случае, когда нужно добавлять или удалять большое количество элементов в начало списка, поскольку в связанном списке нет необходимости менять индексы элементов, после удаленных, то есть временная сложность O(1) у списка против O(n) у массива (для shift/unshift).

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

// Разворот списка
reverse() {
    if (!this.head.next) {
        return this.head;
    }
    let first = this.head;
    this.tail = this.head;
    let second = first.next;
    while (second) {
        const temp = second.next;
        second.next = first;
        first = second;
        second = temp;
    }
    this.head.next = null;
    this.head = first;
    return this;
}

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

// Вывод списка в консоль - служебный метод для визуализации
_print() {
    console.log(`HEAD: ${this.head.value}`);
    let currentNode = this.head;
    while (currentNode.next) {
        console.log(currentNode.value);
        currentNode = currentNode.next;
    }
    console.log(currentNode.value);
    console.log(`TAIL: ${this.tail.value}`);
}

В итоге получаем нечто подобное:

const list = new DoubleLinkedList(2)
list.append(3)
list.prepend(5)
list.prepend(8)
list._print()
// HEAD: 8
// 8
// 5
// 2
// 3
// TAIL: 3
list.reverse()
list._print()
// HEAD: 3
// 3
// 2
// 5
// 8
// TAIL: 8

Что в итоге

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

Если вы будете судить рыбу по её способности взбираться на дерево, она проживёт всю жизнь, считая себя дурой (А. Эйнштейн)

Плюсы связанного списка:

• упорядочен

• имеет гибкий размер

• временная сложность вставки в начало (prepend) и в конец (append) - O(1)

Минусы:

• занимает много памяти

• перебор, вставка в середину и удаление произвольного элемента имеют временную сложность O(n)

Реализации связных списков (простого, двойного, сортированного, а также реализацию структуры данных "очередь", основанную на связном списке) можно взять в моем github

Резюме

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

Всем желаю успехов!