Короткий и точный код Js для создания двусвязного списка
Почти идентичен односвязным спискам, за исключением того, что каждый узел имеет еще один указатель на предыдущий узел. Он обеспечивает большую гибкость по сравнению с односвязными списками.
Все:
1. Толкай и хлопай
2. Unshift и Shift
3. Получить и установить
4. Вставить и удалить
Создание узла: он содержит значение и два указателя next, prev.
Двусвязный список:три важные вещи: начало, хвост, длина
Push:добавление узла в конец двусвязного списка
- Эта функция примет значение. Создайте новый узел со значением, переданным функции.
- Если свойство head равно null, то установите голову и хвост в качестве нового узла.
- Если нет, установите следующее свойство в хвосте DLL для этого узла.
- Установите предыдущее свойство на новом узле как хвост.
- Установите хвост как вновь созданный узел.
- Увеличьте длину DLL на единицу.
- Вернуть DLL.
Pop:удаление узла из конца библиотеки DLL.
- Если головы нет, вернуть undefined.
- Сохраните текущий хвост в переменной, чтобы вернуться позже.
- Если длина равна единице, установите для головы и хвоста значение null;
- Обновите хвост, чтобы он был предыдущим узлом.
- Установите следующее значение нового хвоста равным нулю.
- Уменьшить длину на единицу.
- Вернуть удаленное значение.
Unshift:добавление нового узла в начало библиотеки DLL.
- Эта функция должна принять значение и создать новый узел, используя это значение.
- Если длина DLL равна нулю, установите начало и конец в качестве нового узла.
- В противном случае,
- Задайте для свойства prev в начале списка новый узел.
- Задайте для следующего свойства нового узла текущую головку.
- Обновите заголовок библиотеки DLL, чтобы он стал вновь созданным узлом.
4. Увеличьте длину на единицу.
5. Вернуть список.
Shift:удаление узла из начала библиотеки DLL.
- Если длина равна нулю, вернуть undefined.
- Сохраните значение головы в переменной.
- Если длина равна единице, установите для головы и хвоста значение null.
- Обновите голову, чтобы она была следующей старой головы.
- Установите для предыдущего свойства головы значение null.
- Установите старые головки рядом с нулевым значением.
- Уменьшить длину на единицу.
- Верните старую голову.
Get:доступ к узлу в DLL.
- Эта функция примет индекс. Если индекс меньше 0 (ноль) или ≥ (gte) длины, вернуть null.
- Если индекс ≤ (lte) половины длины списка.
- Прокрутите список, начиная с головы, и двигайтесь к середине.
- Верните узел, как только он будет найден.
3. Если индекс ≥ (gte) половины длины списка.
- Прокрутите список, начиная с хвоста, и двигайтесь к середине.
- Верните узел, как только он будет найден.
Set:замена значения узла индексом в DLL.
- Создайте переменную, которая является результатом метода get по индексу, переданному функции.
- Если метод get возвращает допустимый узел, установите значение этого узла как значение, переданное функции.
- Вернуть истину.
2. В противном случае вернуть false.
Вставка:добавление узла в DLL в определенной позиции.
- Если индекс меньше нуля или ≥ (gte), длина возвращает false.
- Если индекс равен нулю, отмените сдвиг.
- Если индекс совпадает с длиной, отправьте.
- Используйте метод get для доступа к файлу index-1.
- Задайте свойства next и prev для правильных узлов, чтобы связать все вместе.
- Увеличьте длину на единицу.
- вернуть истину.
Удалить:удаление узла в DLL из определенной позиции.
- Если индекс меньше 0 или ≥ (gte), возвращается значение undefined.
- Если индекс равен нулю, сдвиг.
- Если индекс совпадает с length-1, всплывает.
- Используйте метод get, чтобы получить элемент, который нужно удалить.
- Обновите следующее и предыдущее свойства, чтобы удалить найденный узел из списка.
- Установите для следующего и предыдущего значения null на найденном узле.
- Уменьшить длину на единицу.
- Вернуть удаленный узел.
Временная сложность двусвязного списка:
- Доступ:O(N)
- Поиск:O(N)
- Вставка:O(1)
- Удаление:O(1)
Обзор:
- Почти идентичен SLL, за исключением того, что есть дополнительный указатель на предыдущий узел.
- Лучше находит узлы и может делать это вдвое быстрее, чем SLL.
- Им нужно больше памяти, учитывая дополнительный указатель.