Связанные списки

Если вы человек, который всегда боится изучать структуры данных и понятия не имеет, с чего начать, не волнуйтесь. Я здесь, чтобы объяснить и начать со связанных списков. Связный список — это линейная структура данных, которая хранит данные в узлах. Узел — это тип объекта, который хранит данные и ссылку на следующий узел.

Узел

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

Мы можем создать такой узел в JavaScript

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

Список

Хорошо, это самая захватывающая часть этой статьи, потому что мы собираемся создать самый важный объект, называемый списком. Да, я сказал возражать! потому что это тоже будет класс. Мы собираемся перечислить все экземпляры нашего объекта узла внутри объекта List.

Итак, вот класс связанного списка.

class LinkedList {
  constructor() {
    this.length = 0;
    this.head = null;
    this.tail = null;
  }
}

Как видите, в нашем связанном списке есть три основных свойства; длина, голова и хвост. Итак, позвольте мне кратко объяснить каждый из них.

Длина - это хранение общего количества узлов
Голова указывает на начало списка (первый узел)
Хвост указывает на конец списка (последний узел)

Итак, теперь давайте добавим метод push, который добавит узел в конец списка и увеличит длину на 1.

push(data) {
  const node = new Node(data);
  if (this.length === 0) {
    this.head = node;
    this.tail = node;
  } else {
    this.tail.next = node;
    this.tail = node;
  }
  this.length++;
}

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

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

getAll() {
  let current = this.head;
  let result = [];
  while (current) {
    result.push(current.data);
    current = current.next;
  }
  return result;
}

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

Вот весь код.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
class LinkedList {
  constructor() {
    this.length = 0;
    this.head = null;
    this.tail = null;
  }

  push(data) {
    const node = new Node(data);
    if (this.length === 0) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.length++;
  }
  getAll() {
    let current = this.head;
    let list = [];
    while (current) {
      list.push(current.data);
      current = current.next;
    }
    return list;
  }
}

В заключение давайте проверим временную сложность Singly LinkedList.

Заключение

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

Связанные списки