Поиск...
  1. Журнал
  2. Решения и советы
  3. Веб-программирование
  4. Javascript
0 ∞ 5

Как реализовать связный список на JavaScript

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

Вы разберете обе реализации на JavaScript, проверите их через console.log и сравните с массивом по сложности операций.

Сергей БензенкоОбновлено 4 мин чтения ∞ 5
Содержание

Как выбрать структуру данных

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

Позиции в примерах считаются с 1, поэтому они отличаются от индексов массивов JavaScript, которые начинаются с 0.

ОперацияОдносвязный список без tailДвусвязный список с tailArray
Вставка в началоO(1)O(1)O(n)
Вставка в конецO(n)O(1)O(1) в среднем
Доступ по позицииO(n)O(n)O(1)
Удаление головыO(1)O(1)O(n)
Удаление хвостаO(n)O(1)O(1) в среднем
Удаление серединыO(n)O(n) для поиска узлаO(n)

Здесь n – число элементов. Оценки для Array описывают обычный плотный массив и типичные реализации движков. Удаление середины списка включает поиск узла по позиции.

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

Научитесь создавать 3D-персонажей и погрузитесь в мир 3D-графики на курсах по созданию 3D-персонажей!

Односвязный список на JavaScript

Односвязный список состоит из узлов с данными и ссылкой next. Объект SinglyList хранит голову head и число узлов _length. В каждом методе используйте одну схему нумерации: первая позиция имеет номер 1.

Узел и контейнер списка

Класс SinglyNode хранит значение и ссылку на следующий узел. Пустой SinglyList получает head со значением null и длину 0.

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

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

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

Метод prepend(value) для вставки в начало

Метод prepend связывает новый узел с прежней головой списка. Затем он обновляет head и увеличивает длину на 1.

prepend(value) {
  const node = new SinglyNode(value);
  node.next = this.head;
  this.head = node;
  this._length += 1;
  return node;
}

Метод не обходит список, поэтому вставка в начало занимает O(1). Для пустого списка node.next остается равным null.

Метод add(value)

Метод создает узел и ставит его в конец списка. Для пустого списка новый узел становится head.

add(value) {
  const node = new SinglyNode(value);

  if (!this.head) {
    this.head = node;
    this._length += 1;
    return node;
  }

  let currentNode = this.head;
  while (currentNode.next) {
    currentNode = currentNode.next;
  }

  currentNode.next = node;
  this._length += 1;
  return node;
}
Как реализовать шаблон MVC на JavaScript

Цикл проходит весь список до последнего узла, поэтому add работает за O(n).

Если добавление в конец происходит часто, храните отдельную ссылку tail и меняйте ее за O(1).

Метод searchNodeAt(position)

Метод начинает обход с head и делает position – 1 переходов. Нулевая, дробная и слишком большая позиция вызывают ошибку.

searchNodeAt(position) {
  if (!Number.isInteger(position) || position < 1 || position > this._length) {
    throw new Error('Failure: non-existent node in this list.');
  }

  let currentNode = this.head;
  let count = 1;

  while (count < position) {
    currentNode = currentNode.next;
    count += 1;
  }

  return currentNode;
}

Метод remove(position)

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

remove(position) {
  if (!Number.isInteger(position) || position < 1 || position > this._length) {
    throw new Error('Failure: non-existent node in this list.');
  }

  if (position === 1) {
    const deletedNode = this.head;
    this.head = deletedNode.next;
    deletedNode.next = null;
    this._length -= 1;
    return deletedNode;
  }

  let beforeNodeToDelete = this.head;
  let count = 1;

  while (count < position - 1) {
    beforeNodeToDelete = beforeNodeToDelete.next;
    count += 1;
  }

  const deletedNode = beforeNodeToDelete.next;
  beforeNodeToDelete.next = deletedNode.next;
  deletedNode.next = null;
  this._length -= 1;

  return deletedNode;
}
Как выбрать или снять все флажки на JavaScript

Цикл меняет beforeNodeToDelete на каждом переходе. Поэтому remove(2), remove(3) и последующие вызовы удаляют нужные узлы, а remove(0) сразу завершается ошибкой.

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

Соберите класс целиком и выполните несколько операций. После remove(2) второй узел исчезает, а searchNodeAt(2) возвращает прежний третий узел.

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

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

  prepend(value) {
    const node = new SinglyNode(value);
    node.next = this.head;
    this.head = node;
    this._length += 1;
    return node;
  }

  add(value) {
    const node = new SinglyNode(value);

    if (!this.head) {
      this.head = node;
      this._length += 1;
      return node;
    }

    let currentNode = this.head;
    while (currentNode.next) {
      currentNode = currentNode.next;
    }
    currentNode.next = node;
    this._length += 1;
    return node;
  }

  searchNodeAt(position) {
    if (!Number.isInteger(position) || position < 1 || position > this._length) {
      throw new Error('Failure: non-existent node in this list.');
    }

    let currentNode = this.head;
    let count = 1;
    while (count < position) {
      currentNode = currentNode.next;
      count += 1;
    }
    return currentNode;
  }

  remove(position) {
    if (!Number.isInteger(position) || position < 1 || position > this._length) {
      throw new Error('Failure: non-existent node in this list.');
    }

    if (position === 1) {
      const deletedNode = this.head;
      this.head = deletedNode.next;
      deletedNode.next = null;
      this._length -= 1;
      return deletedNode;
    }

    let beforeNodeToDelete = this.head;
    let count = 1;
    while (count < position - 1) {
      beforeNodeToDelete = beforeNodeToDelete.next;
      count += 1;
    }

    const deletedNode = beforeNodeToDelete.next;
    beforeNodeToDelete.next = deletedNode.next;
    deletedNode.next = null;
    this._length -= 1;
    return deletedNode;
  }
}

const singlyList = new SinglyList();
singlyList.add('HTML');
singlyList.add('CSS');
singlyList.add('JavaScript');
console.log(singlyList.searchNodeAt(2).data); // CSS
console.log(singlyList.remove(2).data); // CSS
console.log(singlyList.searchNodeAt(2).data); // JavaScript
singlyList.prepend('Web');
console.log(singlyList.head.data); // Web
console.log(singlyList._length); // 3
Как сделать простое слайд‑шоу на JavaScript

Двусвязный список на JavaScript

Двусвязный узел хранит ссылки next и previous. Контейнер добавляет tail, поэтому вставка в конец и удаление последнего узла выполняются за O(1).

Узел, head и tail

Для пустого списка head и tail равны null.

У первого узла previous равен null, у последнего next равен null.

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

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

Методы из отдельных листингов размещайте внутри класса DoublyList после конструктора. Полную реализацию запускайте отдельно от этих фрагментов.

Метод add(value)

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

add(value) {
  const node = new DoublyNode(value);

  if (!this.tail) {
    this.head = node;
    this.tail = node;
  } else {
    node.previous = this.tail;
    this.tail.next = node;
    this.tail = node;
  }

  this._length += 1;
  return node;
}

Метод searchNodeAt(position)

Метод выбирает направление обхода по позиции. Для второй половины списка он начинает с tail и движется через previous.

searchNodeAt(position) {
  if (!Number.isInteger(position) || position < 1 || position > this._length) {
    throw new Error('Failure: non-existent node in this list.');
  }

  if (position <= this._length / 2) {
    let currentNode = this.head;
    let count = 1;
    while (count < position) {
      currentNode = currentNode.next;
      count += 1;
    }
    return currentNode;
  }

  let currentNode = this.tail;
  let count = this._length;
  while (count > position) {
    currentNode = currentNode.previous;
    count -= 1;
  }
  return currentNode;
}

Метод remove(position)

Сначала метод получает удаляемый узел.

Для головы он обновляет head, для хвоста – tail, для середины соединяет соседние узлы напрямую.

remove(position) {
  if (!Number.isInteger(position) || position < 1 || position > this._length) {
    throw new Error('Failure: non-existent node in this list.');
  }

  const deletedNode = this.searchNodeAt(position);

  if (deletedNode.previous) {
    deletedNode.previous.next = deletedNode.next;
  } else {
    this.head = deletedNode.next;
  }

  if (deletedNode.next) {
    deletedNode.next.previous = deletedNode.previous;
  } else {
    this.tail = deletedNode.previous;
  }

  deletedNode.previous = null;
  deletedNode.next = null;
  this._length -= 1;

  return deletedNode;
}

При удалении единственного узла обе ссылки становятся null. При удалении головы новый head получает previous со значением null. Метод возвращает удаленный узел во всех трех ветках.

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

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

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

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

  add(value) {
    const node = new DoublyNode(value);

    if (!this.tail) {
      this.head = node;
      this.tail = node;
    } else {
      node.previous = this.tail;
      this.tail.next = node;
      this.tail = node;
    }

    this._length += 1;
    return node;
  }

  searchNodeAt(position) {
    if (!Number.isInteger(position) || position < 1 || position > this._length) {
      throw new Error('Failure: non-existent node in this list.');
    }

    if (position <= this._length / 2) {
      let currentNode = this.head;
      let count = 1;
      while (count < position) {
        currentNode = currentNode.next;
        count += 1;
      }
      return currentNode;
    }

    let currentNode = this.tail;
    let count = this._length;
    while (count > position) {
      currentNode = currentNode.previous;
      count -= 1;
    }
    return currentNode;
  }

  remove(position) {
    if (!Number.isInteger(position) || position < 1 || position > this._length) {
      throw new Error('Failure: non-existent node in this list.');
    }

    const deletedNode = this.searchNodeAt(position);

    if (deletedNode.previous) {
      deletedNode.previous.next = deletedNode.next;
    } else {
      this.head = deletedNode.next;
    }

    if (deletedNode.next) {
      deletedNode.next.previous = deletedNode.previous;
    } else {
      this.tail = deletedNode.previous;
    }

    deletedNode.previous = null;
    deletedNode.next = null;
    this._length -= 1;
    return deletedNode;
  }
}

const doublyList = new DoublyList();
doublyList.add('HTML');
doublyList.add('CSS');
doublyList.add('JavaScript');
doublyList.add('PHP');
console.log(doublyList.searchNodeAt(4).data); // PHP
console.log(doublyList.remove(4).data); // PHP
console.log(doublyList.tail.data); // JavaScript
console.log(doublyList.remove(1).data); // HTML
console.log(doublyList.head.data); // CSS

Какой список выбрать под задачу

Для стека с добавлением и удалением головы подойдет SinglyList с prepend и remove(1). Для очереди с добавлением в конец используйте DoublyList с add и remove(1). Если задача требует частого доступа по индексу, выбирайте Array.

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

Сергей Бензенкоавтор-переводчик источника

Комментарии

Оставьте свой комментарий
А
Артём

не if (!this.head), а if (this.head)
и пропущено объявление переменной afterNodeToDelete

Ответить
НГ
Нелли Г.

Жаль не приведен метод копирования связных списков. Такой метод возможен вообще?

Ответить
K
Karen

пожалуйста обьясните подчеркнутое

Ответить
MD
Markin D.

Видимо, неверно и то, что

return message.success;

комментируется как "В конце мы уменьшаем длину списка и возвращаем deletedNode." Соответственно, не реализована в коде и логика присвоения значения переменной deletedNode

Ответить
ПП
Петр П.

У вас ошибка в коде, условие противоположно:
if (!this.head) {
this.head.previous = null;
// 2-ой случай: второго узла не существует
} else {
this.tail = null;
}

Ответить

Популярное за неделю

  1. Как создать сайт самому в 2026: 4 способа + пошаговая инструкция 34 мин чтения
  2. Лучшие конструкторы для создания сайтов — плюсы, минусы и сравнения 22 мин чтения
  3. Скрипт сокращения URL на PHP с INI 3 мин чтения
  4. jquery select onchange в jQuery: как получить значение select 6 мин чтения
  5. Как создать фотогалерею для сайта 5 мин чтения
  6. Валидация формы js для регистрации с проверкой полей 5 мин чтения

Ещё в рубрике «Javascript»

15 JavaScript‑библиотек для анимации SVG
Доступное модальное окно на HTML, CSS и JavaScript
Что такое всплывающее окно и как создать его самостоятельно
Как сделать адаптивное меню на JavaScript
OAuth 2.0: обзор потоков и вопросов безопасности
Проверка формы на JavaScript
Как получить GET-параметры из URL в JavaScript
15 плагинов календарей и событий для сайта
Лучшие бесплатные библиотеки JavaScript для графиков