Короткий и точный код Js для создания двусвязного списка

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

Все:

1. Толкай и хлопай

2. Unshift и Shift

3. Получить и установить

4. Вставить и удалить

Создание узла: он содержит значение и два указателя next, prev.

Двусвязный список:три важные вещи: начало, хвост, длина

Push:добавление узла в конец двусвязного списка

  1. Эта функция примет значение. Создайте новый узел со значением, переданным функции.
  2. Если свойство head равно null, то установите голову и хвост в качестве нового узла.
  3. Если нет, установите следующее свойство в хвосте DLL для этого узла.
  4. Установите предыдущее свойство на новом узле как хвост.
  5. Установите хвост как вновь созданный узел.
  6. Увеличьте длину DLL на единицу.
  7. Вернуть DLL.

Pop:удаление узла из конца библиотеки DLL.

  1. Если головы нет, вернуть undefined.
  2. Сохраните текущий хвост в переменной, чтобы вернуться позже.
  3. Если длина равна единице, установите для головы и хвоста значение null;
  4. Обновите хвост, чтобы он был предыдущим узлом.
  5. Установите следующее значение нового хвоста равным нулю.
  6. Уменьшить длину на единицу.
  7. Вернуть удаленное значение.

Unshift:добавление нового узла в начало библиотеки DLL.

  1. Эта функция должна принять значение и создать новый узел, используя это значение.
  2. Если длина DLL равна нулю, установите начало и конец в качестве нового узла.
  3. В противном случае,
  • Задайте для свойства prev в начале списка новый узел.
  • Задайте для следующего свойства нового узла текущую головку.
  • Обновите заголовок библиотеки DLL, чтобы он стал вновь созданным узлом.

4. Увеличьте длину на единицу.

5. Вернуть список.

Shift:удаление узла из начала библиотеки DLL.

  1. Если длина равна нулю, вернуть undefined.
  2. Сохраните значение головы в переменной.
  3. Если длина равна единице, установите для головы и хвоста значение null.
  4. Обновите голову, чтобы она была следующей старой головы.
  5. Установите для предыдущего свойства головы значение null.
  6. Установите старые головки рядом с нулевым значением.
  7. Уменьшить длину на единицу.
  8. Верните старую голову.

Get:доступ к узлу в DLL.

  1. Эта функция примет индекс. Если индекс меньше 0 (ноль) или ≥ (gte) длины, вернуть null.
  2. Если индекс ≤ (lte) половины длины списка.
  • Прокрутите список, начиная с головы, и двигайтесь к середине.
  • Верните узел, как только он будет найден.

3. Если индекс ≥ (gte) половины длины списка.

  • Прокрутите список, начиная с хвоста, и двигайтесь к середине.
  • Верните узел, как только он будет найден.

Set:замена значения узла индексом в DLL.

  1. Создайте переменную, которая является результатом метода get по индексу, переданному функции.
  • Если метод get возвращает допустимый узел, установите значение этого узла как значение, переданное функции.
  • Вернуть истину.

2. В противном случае вернуть false.

Вставка:добавление узла в DLL в определенной позиции.

  1. Если индекс меньше нуля или ≥ (gte), длина возвращает false.
  2. Если индекс равен нулю, отмените сдвиг.
  3. Если индекс совпадает с длиной, отправьте.
  4. Используйте метод get для доступа к файлу index-1.
  5. Задайте свойства next и prev для правильных узлов, чтобы связать все вместе.
  6. Увеличьте длину на единицу.
  7. вернуть истину.

Удалить:удаление узла в DLL из определенной позиции.

  1. Если индекс меньше 0 или ≥ (gte), возвращается значение undefined.
  2. Если индекс равен нулю, сдвиг.
  3. Если индекс совпадает с length-1, всплывает.
  4. Используйте метод get, чтобы получить элемент, который нужно удалить.
  5. Обновите следующее и предыдущее свойства, чтобы удалить найденный узел из списка.
  6. Установите для следующего и предыдущего значения null на найденном узле.
  7. Уменьшить длину на единицу.
  8. Вернуть удаленный узел.

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

  • Доступ:O(N)
  • Поиск:O(N)
  • Вставка:O(1)
  • Удаление:O(1)

Обзор:

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