Связный список (Linked Lists)

• Связный список
• Зачем использовать связный список
• Узел (LinkedListNode)
• Cписок (LinkedList)
  • Конструктор
  • Prepend
  • Append
  • Delete
  • Find
  • DeleteTail
  • DeleteHead
  • FromArray
  • ToArray
  • ToString
  • Reverse
• Вывод

Связный список (Linked Lists)

Связный список - это структура данных, в которой несколько значений хранятся линейно. Каждое значение содержит своё собственное значение узла, а также содержит данные вместе со ссылкой на следующий узел в списке. Ссылка - это указатель на другой объект узла или на null, если следующего узла нет. Если у каждого узла есть только один указатель на другой узел (чаще всего называется next), то этот список считается односвязный (singly linked list); тогда как если у каждого узла есть две ссылки (обычно previous и next), то он считается двусвязный (doubly linked list).

В этом посте я остановлюсь на односвязном списке.

Если ты хочешь сразу перейти к коду и пропустить объяснение - можешь посмотреть его здесь (TypeScript).

Зачем использовать связный список

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

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

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

Узел (LinkedListNode)

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

Узел имеет две части информации:

• указатель или ссылка на следующий узел в списке next (для односвязного списка);
• значение узла value.

Также, он будет содержать один метод - toString: который возвращает значение в строке.

Когда экземпляр класса LinkedListNode сформирован, вызывается функция конструктора, чтобы инициализировать объект с двумя свойствами, value - текущее значение и next - указатель на следующий узел в списке. Указатель next инициализируется со значением по умолчанию null, в случае, если никакое значение не передается в качестве аргумента.

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

  toString(callback) {
    return callback ? callback(this.value) : `${this.value}`;
  }
}

Метод toString принимает обратный вызов для того что бы, если value будет объектом, указать callback, который достанет из этого объекта нужное значение в виде строки. Если же мы передадим просто объект в шаблонные строки, то получим "[object Object]". callback может выглядеть так:

// value - это объект
const nodeStringifier = value => `${value.key}:${value.value}`;

Cписок (LinkedList)

Теперь углубимся в класс LinkedList. Наш список узлов будет содержать десять методов:

• prepend(значение): принимает значение и создаёт новый узел с этим значением, помещая его в начало связного списка;
• append(значение): принимает значение и создаёт новый узел с этим значением, помещая его в конец связного списка;
• delete(значение): принимает значение и удаляет все узлы, которые имеют указаное значение;
• find(значение): принимает значение и находит первый узел с таким же значением;
• deleteTail(): удаляет последний узел из списка;
• deleteHead(): удаляет первый узел из списка;
• fromArray(массив значений): принимает массив значений и создаёт новые узлы из каждого элемента массива, добавляя их в конец списка;
• toArray(): создаёт массив из всех узлов;
• toString(обратный вызов): принимает обратный вызов (не обязательно) и создаёт строку из всех значений узлов;
• reverse(): создаёт обратный список, меняя узлы местами.

Конструктор

Мы используем синтаксис class JavaScript, хотя также можем использовать замыкание для создания связного списка. Итак, давай настроим конструктор.

В нашем конструкторе нам понадобится два элемента информации:

• head: ссылка на узел в начале списка;
• tail: ссылка на узел в конце списка.

Первый узел в связном списке обычно называется head, последний tail.

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

Когда создаётся экземпляр класса LinkedList, вызывается функция конструктора для инициализации объекта со свойством head и tail. Указателям head и tail присваивается значение null, поскольку при первоначальном создании объекта связного списка он не содержит никаких узлов.

Prepend

Prepend метод принимает значение в качестве аргумента и создаёт новый узел с этим значением, помещая его в начало связного списка.

prepend(value) {
  // Создаём новый узел, который будет новым head,
  // при создании передаем второй аргумент, который указывает
  // что его "next" будет текущий head,
  // так как новый узел будет стоять перед текущем head.
  const newNode = new LinkedListNode(value, this.head);

  // Переназначаем head на новый узел
  this.head = newNode;

  // Если ещё нет tail, делаем новый узел tail.
  if (!this.tail) {
    this.tail = newNode;
  }

  // Возвращаем весь список.
  return this;
}

Append

Append метод принимает значение в качестве аргумента и создаёт новый узел с этим значением, помещая его в конец связного списка.

append(value) {
  // Создаём новый узел.
  const newNode = new LinkedListNode(value);

  // Если нет head или tail, делаем новым узлом head и tail.
  if (!this.head || !this.tail) {
    this.head = newNode;
    this.tail = newNode;

    return this;
  }

  // Присоединяем новый узел к концу связного списка.
  // Берём последний узел и указываем, что его next будет новым узлом.
  this.tail.next = newNode;

  // Переназначаем tail на новый узел.
  this.tail = newNode;

  return this;
}

Delete

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

delete(value) {
  // Если нет head значит список пуст.
  if (!this.head) {
    return null;
  }

  let deletedNode = null;

  // Если head должен быть удален, то делаем следующий узел новым head.
  while (this.head && this.head.value === value) {
    deletedNode = this.head;

    // Переназначаем следующий за head узел на новый head.
    this.head = this.head.next;
  }

  let currentNode = this.head;

  // Если следующий узел должен быть удален,
  // делаем узел через один, следующим для проверки.
  // Перебираем все узлы и удаляем их, если их значение равно указанному.
  if (currentNode !== null) {
    while (currentNode.next) {
      if (currentNode.next.value === value) {
        deletedNode = currentNode.next;
        // Перезаписываем, чтобы узел через один стал следующим узлом.
        currentNode.next = currentNode.next.next;
      } else {
        currentNode = currentNode.next;
      }
    }
  }

  // Проверяем, должен ли tail быть удален.
  // Так как, если в цикле мы удаляем последний узел,
  // то с предпоследнего узла убираем только ссылку на него.
  // Поэтому делаем проверку на его удаление с "tail".
  if (this.tail && this.tail.value === value) {
    // в данном случае currentNode это или предпоследний узел или head.
    this.tail = currentNode;
  }

  return deletedNode;
}

Find

Find метод принимает значение в качестве аргумента, находит первый узел с таким же значением и возвращает его.

find(value) {
  // Если нет head значит список пуст.
  if (!this.head) {
    return null;
  }

  let currentNode = this.head;

  // Перебираем все узлы в поиске значения.
  while (currentNode) {
    // Если указано значение, пробуем сравнить его по значению.
    if (value !== undefined && currentNode.value === value) {
      return currentNode;
    }

    // Перематываем на один узел вперед.
    currentNode = currentNode.next;
  }

  return null;
}

DeleteTail

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

deleteTail() {
  // Если нет tail, значит список пуст.

  if (!this.tail) {
    return null;
  }

  // Сохраняем значение последнего узла.
  const deletedTail = this.tail;

  // Если head и tail равны, значит в списке только один узел.
  if (this.head === this.tail) {
    this.head = null;
    this.tail = null;

    return deletedTail;
  }

  // Если в связном списке много узлов.
  // Перебираем все узлы и находим предпоследний узел,
  // убираем ссылку «next» на последний узел.
  let currentNode = this.head;
  while (currentNode.next) {
    // Если у следующего узла нет следующего узла,
    // значит текущий узел предпоследний.
    if (!currentNode.next.next) {
      // убираем ссылку «next» на последний узел.
      currentNode.next = null;
    } else {
      // Перематываем на один узел вперед.
      currentNode = currentNode.next;
    }
  }

  // В данном случае currentNode - это предпоследний узел или head,
  // который становится последним узлом.
  this.tail = currentNode;

  return deletedTail;
}

DeleteHead

DeleteHead - метод, который удаляет из списка первый узел и возвращает его.

deleteHead() {
  // Если нет head значит список пуст.
  if (!this.head) {
    return null;
  }

  const deletedHead = this.head;

  // Если у head есть ссылка на следующий "next" узел
  // то делаем его новым head.
  if (this.head.next) {
    this.head = this.head.next;
  } else {
    // Если у head нет ссылки на следующий "next" узел
    // то мы удаляем последний узел.
    this.head = null;
    this.tail = null;
  }

  return deletedHead;
}

FromArray

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

// Создаём новые узлы из массива и добавляем в конец списка.
fromArray(values) {
  values.forEach(value => this.append(value));

  return this;
}

ToArray

ToArray - метод, что создаёт массив из всех узлов и возвращает его.

// Создаём массив из всех узлов
toArray() {
  const nodes = [];

  let currentNode = this.head;

  // Перебираем все узлы и добавляем в массив.
  while (currentNode) {
    nodes.push(currentNode);
    currentNode = currentNode.next;
  }

  // Возвращаем массив из всех узлов.
  return nodes;
}

ToString

ToString - принимает обратный вызов в качестве аргумента (не обязательно) и создаёт строку из всех значений узлов.

Если значение value узла является объектом, нужно указать callback, который достанет из этого объекта значение в виде строки. Если же мы передадим объект в метод toString, то получим "[object Object]";

toString(callback) {
  // Сначала создаём массив из всех узлов.
  return this.toArray()
    // На каждом узле вызываем метод toString
    // что бы получить значение в виде строки.
    .map(node => node.toString(callback))
    // Вызываем метод toString на массиве строк.
    .toString();
}

callback может выглядеть так:

// value - это объект
const nodeStringifier = value => `${value.key}:${value.value}`;

Reverse

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

// Обратный список
reverse() {
  let currNode = this.head;
  let prevNode = null;
  let nextNode = null;

  // Перебираем все узлы.
  while (currNode) {
    // Сохраняем следующий узел.
    nextNode = currNode.next;

    // Меняем ссылку на следующий "next" узел текущего узла,
    // чтобы он ссылался на предыдущий узел.
    // Так как мы меняем их местами, нужно поменять и ссылки на узлы.
    // Изначально, первый узел не имеет предыдущего узла,
    // поэтому после перестановки его "next" станет "null".
    currNode.next = prevNode;

    // Перемещаем узлы prevNode и currNode на один шаг вперед.

    // Текущий узел делаем предыдущим.
    prevNode = currNode;

    // Следующий узел становится текущим.
    currNode = nextNode;
  }

  // Меняем head и tail местами.
  this.tail = this.head;

  // В данном случае prevNode это последний узел,
  // поэтому, после reverse, он становится первым.
  this.head = prevNode;

  // Возвращаем список.
  return this;
}

Вывод

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