Двусвязный список
Двусвязный (двунаправленный) список (doubly linked list) похож на односвязный (см. предыдущий раздел), но узлы такого списка, помимо ссылок на следующие узлы, содержат также ссылки на предыдущие узлы, что, собственно, и делает список двусвязным.
Две ссылки позволяют обходить (traverse) список в обоих направлениях. Несмотря на то, что добавление и удаление узлов в двусвязном списке требует изменения бОльшего количества ссылок, сами эти операции проще и потенциально более эффективны (для некорневых узлов), поскольку при обходе списка нам не нужно следить за предыдущим узлом или повторно обходить список в поиске предыдущего узла.
Сложность
Временная
| Чтение | Поиск | Вставка | Удаление |
|---|---|---|---|
| O(n) | O(n) | O(1) | O(n) |
Пространственная
O(n)
Реализация
Начнем с узла:
// data-structures/doubly-linked-list.js
// Узел
export class Node {
constructor(value, next = null, prev = null) {
// Значение
this.value = value
// Ссылка на следующий узел
this.next = next
// Ссылка на предыдущий узел
this.prev = prev
}
// Возвращает строковое представление узла.
// Принимает кастомную функцию стрингификации
toString(cb) {
return cb ? cb(this.value) : `${this.value}`
}
}
Приступаем к реализации двусвязного списка:
// Двусвязный список
export default class DoublyLinkedList {
constructor(fn) {
// Головной (первый) узел
this.head = null
// Хвостовой (последний) узел
this.tail = null
// Функция сравнения узлов
this.compare = new Comparator(fn)
}
}
Начнем с методов добавления узла в начало и конец списка:
// Добавляет значение в начало списка
prepend(value) {
// Создаем новый узел
const node = new Node(value, this.head)
// Если головной узел имеется,
if (this.head) {
// обновляем его ссылку на предыдущий узел
this.head.prev = node
}
// Обновляем головной узел (заменяем на новый)
this.head = node
// Если хвостовой узел отсутствует, значит,
if (!this.tail) {
// головной узел также является хвостовым
// (список был пустым)
this.tail = node
}
// Это обеспечивает возможность вызова методов по цепочке
return this
}
// Добавляет значение в конец списка
append(value) {
// Если головной узел отсутствует,
if (!this.head) {
// добавляем значение в начало списка
return this.prepend(value)
}
// Создаем новый узел
const node = new Node(value)
// Добавляем ссылку на следующий (новый) узел в хвостовой
this.tail.next = node
// Добавляем ссылку на предыдущий (хвостовой) узел в новый
node.prev = this.tail
// Обновляем хвостовой узел
this.tail = node
return this
}
Методы удаления головного (первого) и хвостового (последнего) узлов:
// Удаляет головной узел
removeHead() {
// Если головной узел отсутствует, значит,
if (!this.head) {
// список пуст - удалять нечего
return null
}
// Удаляемый узел - головной
const removed = this.head
// Если головной узел содержит ссылку на следующий
if (this.head.next) {
// Обновляем головной узел (заменяем на следующий)
this.head = this.head.next
// Обнуляем ссылку головного узла на предыдущий
this.head.prev = null
} else {
// Иначе, обнуляем головной и хвостовой узлы
// (делаем список пустым, поскольку он содержал только один узел)
this.head = null
this.tail = null
}
// Возвращаем удаленный узел
return removed
}
// Удаляет хвостовой узел
removeTail() {
// Если хвостовой узел отсутствует, значит,
if (!this.tail) {
// список пуст -удалять нечего
return null
}
// Удаляемый узел - хвостовой
const removed = this.tail
// Крайний случай: если список состоит из одного узла
if (this.head === this.tail) {
// Обнуляем головной и хвостовой узлы
// (делаем список пустым)
this.head = null
this.tail = null
// Возвращаем удаленный узел
return removed
}
// Обновляем хвостовой узел (заменяем на предыдущий)
this.tail = this.tail.prev
// Обнуляем ссылку хвостового узла на следующий
this.tail.next = null
// Возвращаем удаленный узел
return removed
}
Метод удаления узла по значению:
// Удаляет узел по значению
remove(value) {
// Если головной узел отсутствует, значит,
if (!this.head) {
// список пуст - удалять нечего
return null
}
// Удаляемый узел
let removed = null
// Текущий узел (начинаем с головного)
let current = this.head
// Пока есть текущий узел
while (current) {
// Если значения совпадают
if (this.compare.equal(current.value, value)) {
// Обновляем удаляемый узел
removed = current
// Если удаляется головной узел,
if (removed === this.head) {
// обновляем головной узел
this.head = removed.next
// Если новый головной узел имеется,
if (this.head) {
// обнуляем его ссылку на предыдущий узел
this.head.prev = null
}
// Если также удаляется хвостовой узел
// (список содержит только один узел),
if (removed === this.tail) {
// обнуляем хвостовой узел
// (делаем список пустым)
this.tail = null
}
// Иначе, если удаляется хвостовой узел,
} else if (removed === this.tail) {
// обновляем хвостовой узел
this.tail = removed.prev
// Обнуляем ссылку хвостового узла на следующий
this.tail.next = null
} else {
// Предыдущий узел
const prev = removed.prev
// Следующий узел
const next = removed.next
// Обновляем ссылку предыдущего узла на следующий
prev.next = next
// Обновляем ссылку следующего узла на предыдущий
// (закрываем образовавшуюся брешь)
next.prev = prev
}
}
// Переходим к следующему узлу
current = current.next
}
// Возвращаем удаленный узел
return removed
}
Метод поиска узла по значению:
// Ищет узел по значению.
// Принимает искомое значение и функцию поиска
// в виде объекта
find({ value, cb }) {
// Если головной узел отсутствует, значит,
if (!this.head) {
// список пуст - искать нечего
return null
}
// Текущий узел (начинаем с головного)
let current = this.head
// Пока есть текущий узел
while (current) {
// Если передана функция, и она удовлетворяется,
if (cb && cb(current.value)) {
// возвращаем текущий узел
return current
}
// Если передано значение, и значения совпадают,
if (value && this.compare.equal(current.value, value)) {
// возвращаем текущий узел
return current
}
// Переходим к следующему узлу
current = current.next
}
// Ничего не найдено
return null
}
Метод инвертирования списка:
// Инвертирует список
reverse() {
// Текущий узел (начинаем с головного)
let current = this.head
// Предыдущий узел
let prev = null
// Следующий узел
let next = null
// Пока есть текущий узел
while (current) {
// Обновляем переменную для следующего узла
next = current.next
// Обновляем переменную для предыдущего узла
prev = current.prev
// Обновляем ссылки текущего узла
current.next = prev
current.prev = next
// Обновляем переменную для предыдущего узла
prev = current
// Переходим к следующему узлу
current = next
}
// Меняем местами головной и хвостовой узлы
this.tail = this.head
// Обновляем головной узел
// (заменяем последним предыдущим - хвостовым)
this.head = prev
return this
}
Напоследок реализуем несколько вспомогательных методов:
// Создает список из массива
fromArray(arr) {
// Перебираем элементы массива и добавляем каждый в конец списка
arr.forEach((value) => this.append(value))
return this
}
// Преобразует список в массив
toArray() {
// Массив узлов
const arr = []
// Текущий узел (начинаем с головного)
let current = this.head
// Пока есть текущий узел
while (current) {
// Добавляем узел в массив
arr.push(current)
// Переходим к следующему узлу
current = current.next
}
// Возвращаем массив
return arr
}
// Возвращает строковое представление списка.
// Принимает кастомную функцию стрингификации
toString(cb) {
// Преобразуем список в массив
return (
this.toArray()
// Перебираем узлы и преобразуем каждый в строку
.map((node) => node.toString(cb))
// Преобразуем массив в строку
.toString()
)
}
Полный код двусвязного списка
Тестирование
Проверим, что наш двусвязный список работает, как ожидается.
Начнем с узла:
// data-structures/__tests__/doubly-linked-list.test.js
import DoublyLinkedList, { Node } from '../doubly-linked-list'
describe('DoublyLinkedListNode', () => {
it('должен создать узел с указанным значением', () => {
const node = new Node(1)
expect(node.value).toBe(1)
expect(node.next).toBeNull()
expect(node.prev).toBeNull()
})
it('должен создать узел с объектом в качестве значения', () => {
const nodeValue = { value: 1, key: 'test' }
const node = new Node(nodeValue)
expect(node.value.value).toBe(1)
expect(node.value.key).toBe('test')
expect(node.next).toBeNull()
expect(node.prev).toBeNull()
})
it('должен соединить узлы вместе', () => {
const node2 = new Node(2)
const node1 = new Node(1, node2)
const node3 = new Node(10, node1, node2)
expect(node1.next).toBeDefined()
expect(node1.prev).toBeNull()
expect(node2.next).toBeNull()
expect(node2.prev).toBeNull()
expect(node3.next).toBeDefined()
expect(node3.prev).toBeDefined()
expect(node1.value).toBe(1)
expect(node1.next.value).toBe(2)
expect(node3.next.value).toBe(1)
expect(node3.prev.value).toBe(2)
})
it('должен преобразовать узел в строку', () => {
const node = new Node(1)
expect(node.toString()).toBe('1')
node.value = 'string value'
expect(node.toString()).toBe('string value')
})
it('должен преобразовать узел в строку с помощью кастомной функции', () => {
const nodeValue = { value: 1, key: 'test' }
const node = new Node(nodeValue)
const toStringCallback = (value) =>
`value: ${value.value}, key: ${value.key}`
expect(node.toString(toStringCallback)).toBe('value: 1, key: test')
})
})
Теперь сам список
Запускаем тесты:
npm run test ./data-structures/__tests__/doubly-linked-list
