Структуры данных, реализованные на JavaScript
Связный список
Описание
Свя зный (или связанный, или односвязный, или однонаправленный) список (linked list) - это динамическая структура данных, представляющая собой упорядоченную коллекцию узлов (nodes). Каждый узел содержит значение и ссылку (указатель) на следующий узел.
Преимущество связного списка перед массивом заключается в его структурной гибкости: порядок элементов связного списка может не совпадать с порядком их расположения в памяти. Порядок обхода (traverse) списка задается его внутренними связями. Суть преимущества состоит в том, что во многих языках программирования создание массива требует указания его размера (для выделения необходимой памяти), а связный список позволяет обойти это ограничение.
Недостатком связного списка является то, что время доступа к его элементам линейно (соответствует количеству элементов). Быстрый (произвольный) доступ к элементу невозможен.
Сложность
Временная
Чтение | Поиск | Вставка | Удаление |
---|---|---|---|
O(n) | O(n) | O(1) | O(n) |
Пространственная
O(n)
Реализация
Начнем с реализации вспомогательной функции сравнения узлов:
// utils/comparator.js
export default class Comparator {
constructor(fn) {
this.compare = fn || Comparator.defaultCompare
}
// Дефолтная функция сравнения узлов
static defaultCompare(a, b) {
if (a === b) {
return 0
}
return a < b ? -1 : 1
}
// Проверка на равенство
equal(a, b) {
return this.compare(a, b) === 0
}
// Меньше чем
lessThan(a, b) {
return this.compare(a, b) < 0
}
// Больше чем
greaterThan(a, b) {
return this.compare(a, b) > 0
}
// Меньше или равно
lessThanOrEqual(a, b) {
return this.lessThan(a, b) || this.equal(a, b)
}
// Больше или равно
greaterThanOrEqual(a, b) {
return this.greaterThan(a, b) || this.equal(a, b)
}
// Инверсия сравнения
reverse() {
const original = this.compare
this.compare = (a, b) => original(b, a)
}
}
Эта функция позволяет создавать списки с узлами, значения которых являются не только примитивами, но и объектами.
Реализуем узел списка:
// data-structures/linked-list.js
// Узел
class Node {
constructor(value, next = null) {
// Значение
this.value = value
// Ссылка на следующий узел
this.next = next
}
// Возвращает строковое представление узла.
// Принимает кастомную функцию стрингификации
toString(cb) {
return cb ? cb(this.value) : `${this.value}`
}
}
Приступаем к реализации связного списка:
import Comparator from '../utils/comparator'
export default class LinkedList {
constructor(fn) {
// Головной (первый) узел
this.head = null
// Хвостовой (последний) узел
this.tail = null
// Функция сравнения узлов
this.compare = new Comparator(fn)
}
}
Начнем с методов добавления узла в начало и конец списка:
// Добавляет значение в начало списка
prepend(value) {
// Создаем новый головной узел со ссылкой на предыдущий головной узел
// (новый узел становится головным (первым))
this.head = new Node(value, this.head)
// Если хвостовой узел отсутствует, значит,
if (!this.tail) {
// головной узел также является хвостовым
this.tail = this.head
}
// Это обеспечивает возможность вызова методов по цепочке
return this
}
// Добавляет значение в конец списка
append(value) {
// Создаем новый узел
const node = new Node(value)
// Если головной узел отсутствует, то
if (!this.head) {
// добавляем значение в начало списка
return this.prepend(value)
}
// Добавляем ссылку на новый узел в хвостовой
this.tail.next = node
// Обновляем хвостовой узел
// (новый узел становится хвостовым (последним))
this.tail = node
return this
}
Метод добавления узла в указанную позицию (по индексу):
// Добавляет значение в список по указанному индексу
insert(value, index) {
// Если индекс равен 0, то
if (index === 0) {
// Добавляем значение в начало списка
return this.prepend(value)
}
// Создаем новый узел
const node = new Node(value)
// Текущий узел (начинаем с головного)
let current = this.head
// Счетчик
let i = 1
// Пока есть текущий узел
while (current) {
// Прерываем цикл при совпадении счетчика с индексом -
// это означает, что мы нашли нужный узел
if (i === index) {
break
}
// Переходим к следующему узлу
current = current.next
// Увеличиваем значение счетчика
i += 1
}
// Если узел найден
if (current) {
// Добавляем ссылку на следующий узел в новый
node.next = current.next
// Обновляем ссылку текущего узла на следующий
// (новый узел помещается между текущим и следующим: current и current.next)
current.next = node
} else {
// Если узел не найден,
// добавляем значение в конец списка
return this.append(value)
}
return this
}
Методы удаления головного (первого) и хвостового (последнего) узлов:
// Удаляет головной узел
removeHead() {
// Если головной узел отсутствует, значит,
if (!this.head) {
// список пуст - удалять нечего
return null
}
// Удаляемый узел - головной
const removed = this.head
// Если головной узел содержит ссылку на следующий
if (this.head.next) {
// Обновляем головной узел (заменяем на следующий)
this.head = this.head.next
} else {
// Иначе, обнуляем головной и хвостовой узлы,
// (делаем список пустым, поскольку он содержал только один узел)
this.head = null
this.tail = null
}
// Возвращаем удаленный узел
return removed
}
// Удаляет хвостовой узел
removeTail() {
// Если головной узел отсутствует, значит,
if (!this.head) {
// список пуст - удалять нечего
return null
}
// Удаляемый узел - хвостовой
let removed = this.tail
// Крайний случай: если список состоит из одного узла,
if (this.head === this.tail) {
// обнуляем головной и хвостовой узлы
// (делаем список пустым)
this.head = null
this.tail = null
// Возвращаем удаленный узел
return removed
}
// Текущий узел (начинаем с головного)
let current = this.head
// Обнуляем ссылку на следующий узел.
// Пока есть следующий узел
while (current.next) {
// Если следующий узел является последним
// (не содержит ссылки на следующий),
if (!current.next.next) {
// обнуляем ссылку текущего узла на следующий
current.next = null
} else {
// Иначе, переходим к следующему узлу
current = current.next
}
}
// Обновляем хвостовой узел (заменяем на текущий)
this.tail = current
// Возвращаем удаленный узел
return removed
}
Метод удаления узла по значению:
// Удаляет узел по значению
remove(value) {
// Если головной узел отсутствует, значит,
if (!this.head) {
// список пуст - удалять нечего
return null
}
// Последний удаленный узел
let removed = null
// Пока есть и удаляется головной узел
while (this.head && this.compare.equal(this.head.value, value)) {
// Обновляем удаляемый узел
removed = this.head
// Обновляем головной узел (заменяем на следующий)
this.head = this.head.next
}
// Текущий узел (начинаем с головного)
let current = this.head
// Если узел имеется
if (current) {
// Пока есть следующий узел
while (current.next) {
// Если значения совпадают
if (this.compare.equal(current.next.value, value)) {
// Обновляем удаляемый узел
removed = current.next
// Обновляем ссылку текущего узла (заменяем на следующий,
// чтобы закрыть образовавшуюся брешь)
current.next = current.next.next
} else {
// Иначе, переходим к следующему узлу
current = current.next
}
}
}
// Крайний случай: если удаляется хвостовой узел,
if (this.compare.equal(this.tail.value, value)) {
// обновляем его (заменяем на текущий)
this.tail = current
}
// Возвращаем удаленный узел
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
// Обновляем ссы лку текущего узла на предыдущий
current.next = prev
// Обновляем переменную для предыдущего узла
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()
)
}
Полный код связного списка
import Comparator from '../utils/comparator'
// Узел
export class Node {
constructor(value, next = null) {
// Значение
this.value = value
// Ссылка на следующий узел
this.next = next
}
// Возвращает строковое представление узла.
// Принимает кастомную функцию стрингификации
toString(cb) {
return cb ? cb(this.value) : `${this.value}`
}
}
// Связный список
export default class LinkedList {
constructor(fn) {
// Головной (первый) узел
this.head = null
// Хвостовой (последний) узел
this.tail = null
// Функция сравнения узлов
this.compare = new Comparator(fn)
}
// Добавляет значения в начало списка
prepend(value) {
// Создаем новый головной узел со ссылкой на предыдущий головной узел
// (новый узел становится головным (первым))
this.head = new Node(value, this.head)
// Если хвостовой узел отсутствует, значит,
if (!this.tail) {
// головной узел также является хвостовым
this.tail = this.head
}
// Это обеспечивает возможность вызова методов по цепочке
return this
}
// Добавляет значение в конец списка
append(value) {
// Создаем новый узел
const node = new Node(value)
// Если головной узел отсутствует, то
if (!this.head) {
// добавляем значение в начало списка
return this.prepend(value)
}
// Добавляем ссылку на новый узел в хвостовой узел
this.tail.next = node
// Обновляем хвостовой узел
// (новый узел становится хвостовым (последним))
this.tail = node
return this
}
// Добавляет значение в список по указанному индексу
insert(value, rawIndex) {
// Нормализуем индекс
const index = rawIndex < 0 ? 0 : rawIndex
// Если индекс равен 0, то
if (index === 0) {
// Добавляем значение в начало списка
return this.prepend(value)
}
// Создаем новый узел
const node = new Node(value)
// Текущий узел (начинаем с головного)
let current = this.head
// Счетчик
let i = 1
// Пока есть текущий узел
while (current) {
// Прерываем цикл при совпадении счетчика с индексом -
// это означает, что мы нашли нужный узел
if (i === index) {
break
}
// Переходим к следующему узлу
current = current.next
// Увеличиваем значение счетчика
i += 1
}
// Если узел найден
if (current) {
// Добавляем ссылку на следующий узел в новый
node.next = current.next
// Обновляем ссылку текущего узла на следующий
// (новый узел помещается между текущий и следующим: current и current.next)
current.next = node
} else {
// Если узел не найден,
// добавляем значение в конец списка
return this.append(value)
}
return this
}
// Удаляет головной узел
removeHead() {
// Если головной узел отсутствует, значит,
if (!this.head) {
// список пуст - удалять нечего
return null
}
// Удаляемый узел - головной
const removed = this.head
// Если головной узел содержит ссылку на следующий
if (this.head.next) {
// Обновляем головной узел (заменяем на следующий)
this.head = this.head.next
} else {
// Иначе, обнуляем головной и хвостовой узлы,
// (делаем список пустым, поскольку он содержал только один узел)
this.head = null
this.tail = null
}
// Возвращаем удаленный узел
return removed
}
// Удаляет хвостовой узел
removeTail() {
// Если головной узел отсутствует, значит,
if (!this.head) {
// спис ок пуст - удалять нечего
return null
}
// Удаляемый узел - хвостовой
let removed = this.tail
// Крайний случай: если список состоит из одного узла,
if (this.head === this.tail) {
// обнуляем головной и хвостовой узлы
// (делаем список пустым)
this.head = null
this.tail = null
// Возвращаем удаленный узел
return removed
}
// Текущий узел (начинаем с головного)
let current = this.head
// Обнуляем ссылку на следующий узел.
// Пока есть следующий узел
while (current.next) {
// Если следующий узел является последним
// (не содержит ссылки на следующий),
if (!current.next.next) {
// обнуляем ссылку текущего узла на следующий
current.next = null
} else {
// Иначе, переходим к следующему узлу
current = current.next
}
}
// Обновляем хвостовой узел (заменяем на текущий)
this.tail = current
// Возвращаем удаленный узел
return removed
}
// Удаляет узел по значению
remove(value) {
// Если головной узел отсутствует, значит,
if (!this.head) {
// список пуст - удалять нечего
return null
}
// Последний удаленный узел
let removed = null
// Пока есть и удаляется головной узел
while (this.head && this.compare.equal(this.head.value, value)) {
// Обновляем удаляемый узел
removed = this.head
// Обновляем головной узел (заменяем на следующий)
this.head = this.head.next
}
// Текущий узел (начинаем с головного)
let current = this.head
// Если узел имеется
if (current) {
// Пока есть следующий узел
while (current.next) {
// Если значения совпадают
if (this.compare.equal(current.next.value, value)) {
// Обновляем удаляемый узел
removed = current.next
// Обновляем ссылку текущего узла (заменяем на следующий,
// чтобы закрыть образовавшуюся брешь)
current.next = current.next.next
} else {
// Иначе, переходим к следующему узлу
current = current.next
}
}
}
// Крайний случай: если удаляется хвостовой узел,
if (this.compare.equal(this.tail.value, value)) {
// обновляем его (заменяем на текущий)
this.tail = current
}
// Возвращаем удаленный узел
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
// Обновляем ссылку текущего узла на предыдущий
current.next = prev
// Обновляем переменную для предыдущего узла
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__/linked-list.test.js
import LinkedList, { Node } from '../linked-list'
describe('LinkedListNode', () => {
it('должен создать узел с указанным значением', () => {
const node = new Node(1)
expect(node.value).toBe(1)
expect(node.next).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()
})
it('должен соединить узлы вместе', () => {
const node2 = new Node(2)
const node1 = new Node(1, node2)
expect(node1.next).toBeDefined()
expect(node2.next).toBeNull()
expect(node1.value).toBe(1)
expect(node1.next.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')
})
})
Теперь сам список
describe('LinkedList', () => {
it('должен создать пустой связный список', () => {
const linkedList = new LinkedList()
expect(linkedList.toString()).toBe('')
})
it('должен добавить узлы в конец списка', () => {
const linkedList = new LinkedList()
expect(linkedList.head).toBeNull()
expect(linkedList.tail).toBeNull()
linkedList.append(1)
linkedList.append(2)
expect(linkedList.toString()).toBe('1,2')
expect(linkedList.tail.next).toBeNull()
})
it('должен добавить узлы в начало списка', () => {
const linkedList = new LinkedList()
linkedList.prepend(2)
expect(linkedList.head.toString()).toBe('2')
expect(linkedList.tail.toString()).toBe('2')
linkedList.append(1)
linkedList.prepend(3)
expect(linkedList.toString()).toBe('3,2,1')
})
it('должен добавить узлы по указанным индексам', () => {
const linkedList = new LinkedList()
linkedList.insert(4, 3)
expect(linkedList.head.toString()).toBe('4')
expect(linkedList.tail.toString()).toBe('4')
linkedList.insert(3, 2)
linkedList.insert(2, 1)
linkedList.insert(1, -7)
linkedList.insert(10, 9)
expect(linkedList.toString()).toBe('1,4,2,3,10')
})
it('должен удалить узлы по значениям', () => {
const linkedList = new LinkedList()
expect(linkedList.remove(5)).toBeNull()
linkedList.append(1)
linkedList.append(1)
linkedList.append(2)
linkedList.append(3)
linkedList.append(3)
linkedList.append(3)
linkedList.append(4)
linkedList.append(5)
expect(linkedList.head.toString()).toBe('1')
expect(linkedList.tail.toString()).toBe('5')
const removedNode = linkedList.remove(3)
expect(removedNode.value).toBe(3)
expect(linkedList.toString()).toBe('1,1,2,4,5')
linkedList.remove(3)
expect(linkedList.toString()).toBe('1,1,2,4,5')
linkedList.remove(1)
expect(linkedList.toString()).toBe('2,4,5')
expect(linkedList.head.toString()).toBe('2')
expect(linkedList.tail.toString()).toBe('5')
linkedList.remove(5)
expect(linkedList.toString()).toBe('2,4')
expect(linkedList.head.toString()).toBe('2')
expect(linkedList.tail.toString()).toBe('4')
linkedList.remove(4)
expect(linkedList.toString()).toBe('2')
expect(linkedList.head.toString()).toBe('2')
expect(linkedList.tail.toString()).toBe('2')
linkedList.remove(2)
expect(linkedList.toString()).toBe('')
})
it('должен удалить хвостовые узлы', () => {
const linkedList = new LinkedList()
linkedList.append(1)
linkedList.append(2)
linkedList.append(3)
expect(linkedList.head.toString()).toBe('1')
expect(linkedList.tail.toString()).toBe('3')
const removedNode1 = linkedList.removeTail()
expect(removedNode1.value).toBe(3)
expect(linkedList.toString()).toBe('1,2')
expect(linkedList.head.toString()).toBe('1')
expect(linkedList.tail.toString()).toBe('2')
const removedNode2 = linkedList.removeTail()
expect(removedNode2.value).toBe(2)
expect(linkedList.toString()).toBe('1')
expect(linkedList.head.toString()).toBe('1')
expect(linkedList.tail.toString()).toBe('1')
const removedNode3 = linkedList.removeTail()
expect(removedNode3.value).toBe(1)
expect(linkedList.toString()).toBe('')
expect(linkedList.head).toBeNull()
expect(linkedList.tail).toBeNull()
})
it('должен удалить головные узлы', () => {
const linkedList = new LinkedList()
expect(linkedList.removeHead()).toBeNull()
linkedList.append(1)
linkedList.append(2)
expect(linkedList.head.toString()).toBe('1')
expect(linkedList.tail.toString()).toBe('2')
const removedNode1 = linkedList.removeHead()
expect(removedNode1.value).toBe(1)
expect(linkedList.toString()).toBe('2')
expect(linkedList.head.toString()).toBe('2')
expect(linkedList.tail.toString()).toBe('2')
const removedNode2 = linkedList.removeHead()
expect(removedNode2.value).toBe(2)
expect(linkedList.toString()).toBe('')
expect(linkedList.head).toBeNull()
expect(linkedList.tail).toBeNull()
})
it('должен добавить в список значения в виде объектов', () => {
const linkedList = new LinkedList()
const nodeValue1 = { value: 1, key: 'key1' }
const nodeValue2 = { value: 2, key: 'key2' }
linkedList.append(nodeValue1).prepend(nodeValue2)
const nodeStringifier = (value) => `${value.key}:${value.value}`
expect(linkedList.toString(nodeStringifier)).toBe('key2:2,key1:1')
})
it('должен найти узлы по значениям', () => {
const linkedList = new LinkedList()
expect(linkedList.find({ value: 5 })).toBeNull()
linkedList.append(1)
expect(linkedList.find({ value: 1 })).toBeDefined()
linkedList.append(2).append(3)
const node = linkedList.find({ value: 2 })
expect(node.value).toBe(2)
expect(linkedList.find({ value: 5 })).toBeNull()
})
it('должен найти узлы с помощью кастомной функции', () => {
const linkedList = new LinkedList()
linkedList
.append({ value: 1, key: 'test1' })
.append({ value: 2, key: 'test2' })
.append({ value: 3, key: 'test3' })
const node = linkedList.find({ cb: (value) => value.key === 'test2' })
expect(node).toBeDefined()
expect(node.value.value).toBe(2)
expect(node.value.key).toBe('test2')
expect(linkedList.find({ cb: (value) => value.key === 'test5' })).toBeNull()
})
it('должен найти узлы с помощью кастомной функции сравнения', () => {
const comparatorFunction = (a, b) => {
if (a.customValue === b.customValue) {
return 0
}
return a.customValue < b.customValue ? -1 : 1
}
const linkedList = new LinkedList(comparatorFunction)
linkedList
.append({ value: 1, customValue: 'test1' })
.append({ value: 2, customValue: 'test2' })
.append({ value: 3, customValue: 'test3' })
const node = linkedList.find({
value: { value: 2, customValue: 'test2' },
})
expect(node).toBeDefined()
expect(node.value.value).toBe(2)
expect(node.value.customValue).toBe('test2')
expect(
linkedList.find({ value: { value: 2, customValue: 'test5' } }),
).toBeNull()
})
it('должен применять функции для поиска узлов в правильном порядке (сначала применяется функция, переданная в объекте, при вызове метода `find`)', () => {
const greaterThan = (value, compareTo) => (value > compareTo ? 0 : 1)
const linkedList = new LinkedList(greaterThan)
linkedList.fromArray([1, 2, 3, 4, 5])
let node = linkedList.find({ value: 3 })
expect(node.value).toBe(4)
node = linkedList.find({ cb: (value) => value < 3 })
expect(node.value).toBe(1)
})
it('должен создать список из массива', () => {
const linkedList = new LinkedList()
linkedList.fromArray([1, 1, 2, 3, 3, 3, 4, 5])
expect(linkedList.toString()).toBe('1,1,2,3,3,3,4,5')
})
it('должен преобразовать список в массив', () => {
const linkedList = new LinkedList()
linkedList.append(1)
linkedList.append(2)
linkedList.append(3)
expect(linkedList.toArray().join(',')).toBe('1,2,3')
})
it('должен инвертировать список', () => {
const linkedList = new LinkedList()
// Добавляем тестовые значения в список
linkedList.append(1).append(2).append(3)
expect(linkedList.toString()).toBe('1,2,3')
expect(linkedList.head.value).toBe(1)
expect(linkedList.tail.value).toBe(3)
// Инвертируем список
linkedList.reverse()
expect(linkedList.toString()).toBe('3,2,1')
expect(linkedList.head.value).toBe(3)
expect(linkedList.tail.value).toBe(1)
// Инвертируем список обратно в начальное состояние
linkedList.reverse()
expect(linkedList.toString()).toBe('1,2,3')
expect(linkedList.head.value).toBe(1)
expect(linkedList.tail.value).toBe(3)
})
})
Запускаем тесты:
npm run test ./data-structures/__tests__/linked-list
Результат:
Отлично! Двигаемся дальше.
Двусвязный список
Двусвязный (или двунаправленный) список (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()
)
}
Полный код двусвязного списка
import Comparator from '../utils/comparator'
// Узел
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')
})
})
Теперь сам список
describe('DoublyLinkedList', () => {
it('должен создать пустой двусвязный список', () => {
const linkedList = new DoublyLinkedList()
expect(linkedList.toString()).toBe('')
})
it('должен добавить узлы в конец списка', () => {
const linkedList = new DoublyLinkedList()
expect(linkedList.head).toBeNull()
expect(linkedList.tail).toBeNull()
linkedList.append(1)
linkedList.append(2)
expect(linkedList.head.next.value).toBe(2)
expect(linkedList.tail.prev.value).toBe(1)
expect(linkedList.toString()).toBe('1,2')
})
it('должен добавить узлы в начало списка', () => {
const linkedList = new DoublyLinkedList()
linkedList.prepend(2)
expect(linkedList.head.toString()).toBe('2')
expect(linkedList.tail.toString()).toBe('2')
linkedList.append(1)
linkedList.prepend(3)
expect(linkedList.head.next.next.prev).toBe(linkedList.head.next)
expect(linkedList.tail.prev.next).toBe(linkedList.tail)
expect(linkedList.tail.prev.value).toBe(2)
expect(linkedList.toString()).toBe('3,2,1')
})
it('должен создать список из массива', () => {
const linkedList = new DoublyLinkedList()
linkedList.fromArray([1, 1, 2, 3, 3, 3, 4, 5])
expect(linkedList.toString()).toBe('1,1,2,3,3,3,4,5')
})
it('должен удалить узлы по значениям', () => {
const linkedList = new DoublyLinkedList()
expect(linkedList.remove(5)).toBeNull()
linkedList.append(1)
linkedList.append(1)
linkedList.append(2)
linkedList.append(3)
linkedList.append(3)
linkedList.append(3)
linkedList.append(4)
linkedList.append(5)
expect(linkedList.head.toString()).toBe('1')
expect(linkedList.tail.toString()).toBe('5')
const removedNode = linkedList.remove(3)
expect(removedNode.value).toBe(3)
expect(linkedList.tail.prev.prev.value).toBe(2)
expect(linkedList.toString()).toBe('1,1,2,4,5')
linkedList.remove(3)
expect(linkedList.toString()).toBe('1,1,2,4,5')
linkedList.remove(1)
expect(linkedList.toString()).toBe('2,4,5')
expect(linkedList.head.toString()).toBe('2')
expect(linkedList.head.next.next).toBe(linkedList.tail)
expect(linkedList.tail.prev.prev).toBe(linkedList.head)
expect(linkedList.tail.toString()).toBe('5')
linkedList.remove(5)
expect(linkedList.toString()).toBe('2,4')
expect(linkedList.head.toString()).toBe('2')
expect(linkedList.tail.toString()).toBe('4')
linkedList.remove(4)
expect(linkedList.toString()).toBe('2')
expect(linkedList.head.toString()).toBe('2')
expect(linkedList.tail.toString()).toBe('2')
expect(linkedList.head).toBe(linkedList.tail)
linkedList.remove(2)
expect(linkedList.toString()).toBe('')
})
it('должен удалить хвостовые узлы', () => {
const linkedList = new DoublyLinkedList()
expect(linkedList.removeTail()).toBeNull()
linkedList.append(1)
linkedList.append(2)
linkedList.append(3)
expect(linkedList.head.toString()).toBe('1')
expect(linkedList.tail.toString()).toBe('3')
const removedNode1 = linkedList.removeTail()
expect(removedNode1.value).toBe(3)
expect(linkedList.toString()).toBe('1,2')
expect(linkedList.head.toString()).toBe('1')
expect(linkedList.tail.toString()).toBe('2')
const removedNode2 = linkedList.removeTail()
expect(removedNode2.value).toBe(2)
expect(linkedList.toString()).toBe('1')
expect(linkedList.head.toString()).toBe('1')
expect(linkedList.tail.toString()).toBe('1')
const removedNode3 = linkedList.removeTail()
expect(removedNode3.value).toBe(1)
expect(linkedList.toString()).toBe('')
expect(linkedList.head).toBeNull()
expect(linkedList.tail).toBeNull()
})
it('должен удалить головные узлы', () => {
const linkedList = new DoublyLinkedList()
expect(linkedList.removeHead()).toBeNull()
linkedList.append(1)
linkedList.append(2)
expect(linkedList.head.toString()).toBe('1')
expect(linkedList.tail.toString()).toBe('2')
const removedNode1 = linkedList.removeHead()
expect(removedNode1.value).toBe(1)
expect(linkedList.head.prev).toBeNull()
expect(linkedList.toString()).toBe('2')
expect(linkedList.head.toString()).toBe('2')
expect(linkedList.tail.toString()).toBe('2')
const removedNode2 = linkedList.removeHead()
expect(removedNode2.value).toBe(2)
expect(linkedList.toString()).toBe('')
expect(linkedList.head).toBeNull()
expect(linkedList.tail).toBeNull()
})
it('должен добавить в список значения в виде объектов', () => {
const linkedList = new DoublyLinkedList()
const nodeValue1 = { value: 1, key: 'key1' }
const nodeValue2 = { value: 2, key: 'key2' }
linkedList.append(nodeValue1).prepend(nodeValue2)
const nodeStringifier = (value) => `${value.key}:${value.value}`
expect(linkedList.toString(nodeStringifier)).toBe('key2:2,key1:1')
})
it('должен найти узлы по значениям', () => {
const linkedList = new DoublyLinkedList()
expect(linkedList.find({ value: 5 })).toBeNull()
linkedList.append(1)
expect(linkedList.find({ value: 1 })).toBeDefined()
linkedList.append(2).append(3)
const node = linkedList.find({ value: 2 })
expect(node.value).toBe(2)
expect(linkedList.find({ value: 5 })).toBeNull()
})
it('должен найти узлы с помощью кастомной функции', () => {
const linkedList = new DoublyLinkedList()
linkedList
.append({ value: 1, key: 'test1' })
.append({ value: 2, key: 'test2' })
.append({ value: 3, key: 'test3' })
const node = linkedList.find({ cb: (value) => value.key === 'test2' })
expect(node).toBeDefined()
expect(node.value.value).toBe(2)
expect(node.value.key).toBe('test2')
expect(linkedList.find({ cb: (value) => value.key === 'test5' })).toBeNull()
})
it('должен найти узлы с помощью кастомной функции сравнения', () => {
const comparatorFunction = (a, b) => {
if (a.customValue === b.customValue) {
return 0
}
return a.customValue < b.customValue ? -1 : 1
}
const linkedList = new DoublyLinkedList(comparatorFunction)
linkedList
.append({ value: 1, customValue: 'test1' })
.append({ value: 2, customValue: 'test2' })
.append({ value: 3, customValue: 'test3' })
const node = linkedList.find({
value: { value: 2, customValue: 'test2' },
})
expect(node).toBeDefined()
expect(node.value.value).toBe(2)
expect(node.value.customValue).toBe('test2')
expect(linkedList.find({ value: 2, customValue: 'test5' })).toBeNull()
})
it('должен инвертировать список', () => {
const linkedList = new DoublyLinkedList()
// Добавляем тестовые значения в список
linkedList.append(1).append(2).append(3).append(4)
expect(linkedList.toString()).toBe('1,2,3,4')
expect(linkedList.head.value).toBe(1)
expect(linkedList.tail.value).toBe(4)
// Инвертируем список
linkedList.reverse()
expect(linkedList.toString()).toBe('4,3,2,1')
expect(linkedList.head.prev).toBeNull()
expect(linkedList.head.value).toBe(4)
expect(linkedList.head.next.value).toBe(3)
expect(linkedList.head.next.next.value).toBe(2)
expect(linkedList.head.next.next.next.value).toBe(1)
expect(linkedList.tail.next).toBeNull()
expect(linkedList.tail.value).toBe(1)
expect(linkedList.tail.prev.value).toBe(2)
expect(linkedList.tail.prev.prev.value).toBe(3)
expect(linkedList.tail.prev.prev.prev.value).toBe(4)
// Инвертируем список обратно в начальное состояние
linkedList.reverse()
expect(linkedList.toString()).toBe('1,2,3,4')
expect(linkedList.head.prev).toBeNull()
expect(linkedList.head.value).toBe(1)
expect(linkedList.head.next.value).toBe(2)
expect(linkedList.head.next.next.value).toBe(3)
expect(linkedList.head.next.next.next.value).toBe(4)
expect(linkedList.tail.next).toBeNull()
expect(linkedList.tail.value).toBe(4)
expect(linkedList.tail.prev.value).toBe(3)
expect(linkedList.tail.prev.prev.value).toBe(2)
expect(linkedList.tail.prev.prev.prev.value).toBe(1)
})
})
Запускаем тесты:
npm run test ./data-structures/__tests__/doubly-linked-list
Результат:
Очередь
Описание
Очередь (queue) - это динам ическая структура данных, в которой элементы хранятся в порядке их добавления. Она является примером линейной структуры или последовательной коллекции. Новые элементы добавляются в конец очереди (enqueue). Удаление элементов выполняется с начала очереди (dequeue). Таким образом, очередь реализует принцип "первым вошел - первым вышел" (first in - first out, FIFO). Кроме enqueue и dequeue, часто также реализуется операция чтения значения головного узла без его удаления (peek).
Иллюстрацией рассматриваемой структуры данных может служить любая очередь в обычной жизни, например, из тех, кто только спросить :D
Реализация
Для реализации очереди мы воспользуемся связным списком (см. раздел 1).
Говорить тут особо не о чем, так что привожу сразу весь код:
// data-structures/queue.js
// Импортируем конструктор связного списка
import LinkedList from './linked-list'
// Очередь
export default class Queue {
constructor() {
// Создаем связный список
this.list = new LinkedList()
}
// Проверяет, является ли очередь пустой
isEmpty() {
return !this.list.head
}
// Возвращает значение первого узла без его удаления
peek() {
if (this.isEmpty()) {
return null
}
return this.list.head.value
}
// Добавляет элемент в конец очереди
enqueue(value) {
this.list.append(value)
}
// Удаляет первый узел и возвращает его значение
dequeue() {
const removedHead = this.list.removeHead()
return removedHead?.value || null
}
// Преобразует очередь в строку.
// Принимает кастомную функцию стрингификации
toString(cb) {
return this.list.toString(cb)
}
// Преобразует очередь в массив значений
toArray() {
return this.list.toArray().map((node) => node.value)
}
}
Тестирование
Проверяем, что наша очередь работает, как ожидается:
// data-structures/__tests__/queue.test.js
import Queue from '../queue'
describe('Queue', () => {
it('должен создать пустую очередь', () => {
const queue = new Queue()
expect(queue).not.toBeNull()
expect(queue.linkedList).not.toBeNull()
})
it('должен добавить значения в очередь', () => {
const queue = new Queue()
queue.enqueue(1)
queue.enqueue(2)
expect(queue.toString()).toBe('1,2')
})
it('должен добавить/удалить объекты в/из очереди', () => {
const queue = new Queue()
queue.enqueue({ value: 'test1', key: 'key1' })
queue.enqueue({ value: 'test2', key: 'key2' })
const stringifier = (value) => `${value.key}:${value.value}`
expect(queue.toString(stringifier)).toBe('key1:test1,key2:test2')
expect(queue.dequeue().value).toBe('test1')
expect(queue.dequeue().value).toBe('test2')
})
it('должен извлечь значения из очереди без удаления и с удалением соответствующих узлов', () => {
const queue = new Queue()
expect(queue.peek()).toBeNull()
queue.enqueue(1)
queue.enqueue(2)
expect(queue.peek()).toBe(1)
expect(queue.peek()).toBe(1)
})
it('должен проверить пустоту очереди', () => {
const queue = new Queue()
expect(queue.isEmpty()).toBe(true)
queue.enqueue(1)
expect(queue.isEmpty()).toBe(false)
})
it('должен удалять элементы из очереди в порядке FIFO', () => {
const queue = new Queue()
queue.enqueue(1)
queue.enqueue(2)
expect(queue.dequeue()).toBe(1)
expect(queue.dequeue()).toBe(2)
expect(queue.dequeue()).toBeNull()
expect(queue.isEmpty()).toBe(true)
})
})
Запускаем тесты:
npm run test ./data-structures/__tests__/queue
Результат:
Стек
Описание
Стек (stack) - это динамическая структура данных, в которой элементы хранятся в порядке, обратному порядку их добавления. Она, как и очередь, является примером линейной структуры или последовательной коллекции. Новые элементы добавляются в начало стека (push). Удаление элементов также выполняется с начала стека (pop). Таким образом, стек реализует принцип "последним вошел - первым вышел" (last in - first out, LIFO). Кроме push и pop, часто также реализуется операция чтения значения головного узла без его удаления (peek).
Иллюстрацией рассматриваемой структуры данных может служить стопка книг: для того, чтобы взять вторую книгу сверху, нужно сначала снять верхнюю.
Реализация
Для реализации стека мы также воспользуемся связным списком (см. раздел 1).
Привожу сразу весь код:
// data-structures/stack.js
// Импортируем конструктор связного списка
import LinkedList from './linked-list'
// Стек
export default class Stack {
constructor() {
// Создаем связный список
this.list = new LinkedList()
}
// Проверяет, является ли стек пустым
isEmpty() {
return !this.list.head
}
// Возвращает значение первого узла без его удаления
peek() {
if (this.isEmpty()) {
return null
}
return this.list.head.value
}
// Добавляет элемент в начало стека
push(value) {
this.list.prepend(value)
}
// Удаляет первый узел и возвращает его значение
pop() {
const removedHead = this.list.removeHead()
return removedHead?.value || null
}
// Преобразует стек в строку
toString(cb) {
return this.list.toString(cb)
}
// Преобразует стек в массив значений
toArray() {
return this.list.toArray().map((node) => node.value)
}
}
Тестирование
Проверяем, что наш стек работает, как ожидается:
// data-structures/__tests__/stack.test.js
import Stack from '../stack'
describe('Stack', () => {
it('должен создать пустой стек', () => {
const stack = new Stack()
expect(stack).not.toBeNull()
expect(stack.linkedList).not.toBeNull()
})
it('должен добавить значения в стек', () => {
const stack = new Stack()
stack.push(1)
stack.push(2)
expect(stack.toString()).toBe('2,1')
})
it('должен проверить пустоту стека', () => {
const stack = new Stack()
expect(stack.isEmpty()).toBe(true)
stack.push(1)
expect(stack.isEmpty()).toBe(false)
})
it('должен извлечь значения из стека без удаления узлов', () => {
const stack = new Stack()
expect(stack.peek()).toBeNull()
stack.push(1)
stack.push(2)
expect(stack.peek()).toBe(2)
expect(stack.peek()).toBe(2)
})
it('должен извлечь значения из стека с удалением узлов', () => {
const stack = new Stack()
stack.push(1)
stack.push(2)
expect(stack.pop()).toBe(2)
expect(stack.pop()).toBe(1)
expect(stack.pop()).toBeNull()
expect(stack.isEmpty()).toBe(true)
})
it('должен добавить/удалить объекты в/из стека', () => {
const stack = new Stack()
stack.push({ value: 'test1', key: 'key1' })
stack.push({ value: 'test2', key: 'key2' })
const stringifier = (value) => `${value.key}:${value.value}`
expect(stack.toString(stringifier)).toBe('key2:test2,key1:test1')
expect(stack.pop().value).toBe('test2')
expect(stack.pop().value).toBe('test1')
})
it('должен преобразовать стек в массив', () => {
const stack = new Stack()
expect(stack.peek()).toBeNull()
stack.push(1)
stack.push(2)
stack.push(3)
expect(stack.toArray()).toEqual([3, 2, 1])
})
})
Запускаем тесты:
npm run test ./data-structures/__tests__/stack
Результат:
Хэш-таблица
Описание
Хэш-таблица (hash table) - это структура данных, которая реализует абстрактный тип данных "ассоциативный массив" и позволяет хранить пары "ключ-значение". Хэш-таблица использует так называемую хэш-функцию (hash function), которая принимает ключ и возвращает индекс массива, по которому будет храниться значение (см. хорошее видео про хэширование). Пример хэш-таблицы, в которой ключом выступает имя человека, а значением адрес его электронной почты:
В идеале хэш-функция должна генерировать уникальный индекс для каждого ключа. Однако реальные хэш-таблицы используют несовершенные хэш-функции, генерирующие одинаковые индексы для разных ключей. Такие ситуации называются коллизиями (collisions). Существует несколько способов их решения, наиболее популярными из которых являются: хэш-таблица с цепочками и хэш-таблица с открытой адресацией.
Метод цепочек подразумевает хранение значений, соответствующих одному индексу в виде связного списка (linked list) (см. часть 1, раздел 1):
Метод открытой адресации помещает значение по совпадающему индексу в первую свободную ячейку:
Реализация
Приступаем к реализации хэш-таблицы:
// data-structures/hash-table.js
// Импортируем конструктор связного списка
// (мы будем использовать метод цепочек для разрешения коллизий)
import LinkedList from './linked-list'
// Дефолтный размер таблицы
// (в реальности размер будет намного больше)
const defaultHashTableSize = 32
// Хэш-таблица
export default class HashTable {
constructor(size = defaultHashTableSize) {
// Создаем таблицу указанного размера и
// заполняем ее пустыми связными списками
this.buckets = new Array(size).fill(null).map(() => new LinkedList())
// Хранилище ключей
this.keys = {}
}
}
Реализуем простейшую хэш-функцию:
// Преобразует ключ в хэшированное значение
// (хэш-функция)
hash(key) {
// Для простоты в качестве хэша используется сумма кодов символов ключа
// https://developer.mozilla.org/ru/docs/Web/JavaScript/Reference/Global_Objects/String/charCodeAt
const hash = [...key].reduce((acc, char) => acc + char.charCodeAt(0), 0)
// Хэш (индекс) не должен превышать размера таблицы
return hash % this.buckets.length
}
Метод установки значения по ключу:
// Устанавливает значение по ключу
set(key, value) {
// Хэшируем ключ
// (получаем индекс массива)
const index = this.hash(key)
// Сохраняем хэш по ключу
this.keys[key] = index
// Извлекаем нужный список
const bucket = this.buckets[index]
// Извлекаем узел
// (значением узла является объект)
const node = bucket.find({ cb: (value) => value.key === key })
// Если узел не найден
if (!node) {
// Добавляем новый узел
bucket.append({ key, value })
} else {
// Иначе, обновляем значение узла
node.value.value = value
}
}
Метод удаления значения по ключу:
// Удаляет значение по ключу
remove(key) {
// Хэшируем ключ
const index = this.hash(key)
// Удаляем хэш по ключу
delete this.keys[key]
// Извлекаем нужный список
const bucket = this.buckets[index]
// Извлекаем узел
const node = bucket.find({ cb: (value) => value.key === key })
// Возвращаем удаленный узел или `null`,
// если узел отсутствует
return node ? bucket.remove(node.value) : null
}
Метод извлечения значения по ключу:
// Возвращает значение по ключу
get(key) {
// Хэшируем ключ
const index = this.hash(key)
// Извлекаем нужный список
const bucket = this.buckets[index]
// Извлекаем узел
const node = bucket.find({ cb: (value) => value.key === key })
// Возвращаем значение узла или `null`,
// если узел отсутствует
return node ? node.value.value : null
}
Напоследок реализуем несколько вспомогательных методов:
// Определяет наличие ключа
has(key) {
// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/hasOwn
return Object.hasOwn(this.keys, key)
}
// Возвращает все ключи
getKeys() {
return Object.keys(this.keys)
}
// Возвращает все значения
getValues() {
// Перебираем списки и возвращаем значения всех узлов
return this.buckets.reduce((acc, bucket) => {
return acc.concat(
// Метод `toArray` преобразует связный список в массив
bucket.toArray().map((node) => node.value.value),
)
}, [])
}
Полный код хэш-таблицы
// Импортируем конструктор связного списка
// (мы будем использовать метод цепочек для разрешения коллизий)
import LinkedList from './linked-list'
// Дефолтный размер таблицы
// (в реальности размер будет намного больше)
const defaultSize = 32
// Хэш-таблица
export default class HashTable {
constructor(size = defaultSize) {
// Создаем таблицу указанного размера и
// заполняем ее пустыми связными списками
this.buckets = new Array(size).fill(null).map(() => new LinkedList())
// Хранилище ключей
this.keys = {}
}
// Преобразует ключ в хэшированное значение
// (хэш-функция)
hash(key) {
// Для простоты в качестве хэша используется сумма кодов символов ключа
// https://developer.mozilla.org/ru/docs/Web/JavaScript/Reference/Global_Objects/String/charCodeAt
const hash = [...key].reduce((acc, char) => acc + char.charCodeAt(0), 0)
// Хэшированное значение не должно превышать размера таблицы
return hash % this.buckets.length
}
// Устанавливает значение по ключу
set(key, value) {
// Хэшируем ключ
// (получаем индекс массива)
const index = this.hash(key)
// Сохраняем хэш по ключу
this.keys[key] = index
// Извлекаем нужный список
const bucket = this.buckets[index]
// Извлекаем узел
// (значением узла является объект)
const node = bucket.find({ cb: (value) => value.key === key })
// Если узел не найден
if (!node) {
// Добавляем новый узел
bucket.append({ key, value })
} else {
// Иначе, обновляем значение узла
node.value.value = value
}
}
// Удаляет значение по ключу
remove(key) {
// Хэшируем ключ
const index = this.hash(key)
// Удаляем хэш по ключу
delete this.keys[key]
// Извлекаем нужный список
const bucket = this.buckets[index]
// Извлекаем узел
const node = bucket.find({ cb: (value) => value.key === key })
// Возвращаем удаленный узел или `null`,
// если узел отсутствует
return node ? bucket.remove(node.value) : null
}
// Возвращает значение по ключу
get(key) {
// Хэшируем ключ
const index = this.hash(key)
// Извлекаем нужный список
const bucket = this.buckets[index]
// Извлекаем узел
const node = bucket.find({ cb: (value) => value.key === key })
// Возвращаем значение узла или `null`,
// если узел отсутствует
return node ? node.value.value : null
}
// Определяет наличие ключа
has(key) {
// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/hasOwn
return Object.hasOwn(this.keys, key)
}
// Возвращает все ключи
getKeys() {
return Object.keys(this.keys)
}
// Возвращает все значения
getValues() {
// Перебираем списки и возвращаем значения всех узлов
return this.buckets.reduce((acc, bucket) => {
return acc.concat(
// Метод `toArray` преобразует связный список в массив
bucket.toArray().map((node) => node.value.value),
)
}, [])
}
}
Тестирование
Проверяем, что наша хэш-таблица работает, как ожидается
// data-structures/__tests__/hash-table.test.js
import HashTable from '../hash-table'
describe('HashTable', () => {
it('должен создать хэш-таблицы указанного размера', () => {
const defaultHashTable = new HashTable()
expect(defaultHashTable.buckets.length).toBe(32)
const biggerHashTable = new HashTable(64)
expect(biggerHashTable.buckets.length).toBe(64)
})
it('должен генерировать правильный хэш для ключей', () => {
const hashTable = new HashTable()
expect(hashTable.hash('a')).toBe(1)
expect(hashTable.hash('b')).toBe(2)
expect(hashTable.hash('abc')).toBe(6)
})
it('должен устанавливать, читать и удалять значения с коллизиями', () => {
const hashTable = new HashTable(3)
expect(hashTable.hash('a')).toBe(1)
expect(hashTable.hash('b')).toBe(2)
expect(hashTable.hash('c')).toBe(0)
expect(hashTable.hash('d')).toBe(1)
hashTable.set('a', 'sky-old')
hashTable.set('a', 'sky')
hashTable.set('b', 'sea')
hashTable.set('c', 'earth')
hashTable.set('d', 'ocean')
expect(hashTable.has('x')).toBe(false)
expect(hashTable.has('b')).toBe(true)
expect(hashTable.has('c')).toBe(true)
const stringifier = (value) => `${value.key}:${value.value}`
expect(hashTable.buckets[0].toString(stringifier)).toBe('c:earth')
expect(hashTable.buckets[1].toString(stringifier)).toBe('a:sky,d:ocean')
expect(hashTable.buckets[2].toString(stringifier)).toBe('b:sea')
expect(hashTable.get('a')).toBe('sky')
expect(hashTable.get('d')).toBe('ocean')
expect(hashTable.get('x')).toBeNull()
hashTable.remove('a')
expect(hashTable.remove('not-existing')).toBeNull()
expect(hashTable.get('a')).toBeNull()
expect(hashTable.get('d')).toBe('ocean')
hashTable.set('d', 'ocean-new')
expect(hashTable.get('d')).toBe('ocean-new')
})
it('должен добавить в таблицу объекты', () => {
const hashTable = new HashTable()
hashTable.set('objectKey', { prop1: 'a', prop2: 'b' })
const object = hashTable.get('objectKey')
expect(object).toBeDefined()
expect(object.prop1).toBe('a')
expect(object.prop2).toBe('b')
})
it('должен отслеживать актуальные ключи', () => {
const hashTable = new HashTable(3)
hashTable.set('a', 'sky-old')
hashTable.set('a', 'sky')
hashTable.set('b', 'sea')
hashTable.set('c', 'earth')
hashTable.set('d', 'ocean')
expect(hashTable.getKeys()).toEqual(['a', 'b', 'c', 'd'])
expect(hashTable.has('a')).toBe(true)
expect(hashTable.has('x')).toBe(false)
hashTable.remove('a')
expect(hashTable.has('a')).toBe(false)
expect(hashTable.has('b')).toBe(true)
expect(hashTable.has('x')).toBe(false)
})
it('должен вернуть все значения', () => {
const hashTable = new HashTable(3)
hashTable.set('a', 'alpha')
hashTable.set('b', 'beta')
hashTable.set('c', 'gamma')
expect(hashTable.getValues()).toEqual(['gamma', 'alpha', 'beta'])
})
it('должен вернуть все значения пустой таблицы', () => {
const hashTable = new HashTable()
expect(hashTable.getValues()).toEqual([])
})
it('должен вернуть все значения при наличии коллизий', () => {
const hashTable = new HashTable(3)
// Ключи `ab` и `ba` в текущей реализации будут иметь одинаковый хэш.
// Нужно убедиться в сериализации нескольких значений одного списка
hashTable.set('ab', 'one')
hashTable.set('ba', 'two')
hashTable.set('ac', 'three')
expect(hashTable.getValues()).toEqual(['one', 'two', 'three'])
})
})
Запускаем тесты:
npm run test ./data-structures/__tests__/hash-table
Результат:
Отлично! Двигаемся дальше.
Куча
Описание
Куча (heap) - это специализированная структура данных типа "дерево" (tree), которая удовлетворяет свойству кучи: если B
является узлом-потомком узла A
, то k(A) >= k(B)
, где k(X)
- ключ (идентификатор) узла. Из этого следует, что элемент с наибольшим значением ключа всегда является корневым узлом (root node) кучи, поэтому такие кучи называют max-кучами (max heaps):
Приведенную max-кучу можно представить в виде массива следующим образом:
Если дерево перевернуть, то корневым узлом всегда будет элемент с наименьшим значением. Такие кучи называют min-кучами:
Не существует никаких ограничений относительно того, сколько узлов-потомков имеет каждый узел кучи, хотя на практике их число обычно не более двух (такие кучи называют "двоичными" или "бинарными" (binary)). Куча является максимально эффективной реализацией абстрактного типа данных, который называется "очередью с приоритетом" (см. следующий раздел). Кучи имеют решающее значение в некоторых эффективных алгоритмах на графах, таких, как алгоритм Дейкстры на d-кучах и сортировка методом пирамиды.
Интерактивную визуализации кучи можно посмотреть здесь.
Сложность
Временная сложность кучи зависит от ее типа.
Тип кучи | find-max | delete-max | insert | increase-key | meld |
---|---|---|---|---|---|
Binary | Θ(1) | Θ(log n) | O(log n) | O(log n) | Θ(n) |
Leftist | Θ(1) | Θ(log n) | Θ(log n) | O(log n) | Θ(log n) |
Binomial | Θ(1) | Θ(log n) | Θ(1) | O(log n) | O(log n) |
Fibonacci | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) |
Pairing | Θ(1) | Θ(log n) | Θ(1) | o(log n) | Θ(1) |
Brodal | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) |
Rank-pairing | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) |
Strict Fibonacci | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) |
2-3 heap | O(log n) | O(log n) | O(log n) | Θ(1) | ? |
Где:
- find-max (или find-min): поиск максимального значения в max-куче или минимального значения в min-куче, соответственно (похоже на peek в очереди или стеке)
- delete-max (or delete-min): удаление корневого узла
- insert: добавление в кучу нового значения (похоже на push в стеке или enqueue в очереди)
- increase-key или decrease-key: обновление значения узла
- meld: объединение 2 куч в 1 с уничтожением оригиналов
Реализация
В рамках этой статьи мы рассмотрим реализацию только бинарной кучи.
Начнем с реализации родительского (или супер, или абстрактного) класса для min- и max-куч. Конструктор этого класса будет выглядеть следующим образом:
// data-structures/heap/index.js
// Импортируем конструктор функции сравнения узлов
import Comparator from '../../utils/comparator'
// Родительский класс для min- и max-куч
export default class Heap {
constructor(fn) {
// Кучи должны создаваться с помощью соответствующих подклассов
if (new.target === Heap) {
throw new TypeError('Кучу нельзя создавать напрямую!')
}
// Представление кучи в виде массива
this.heapContainer = []
// Функция сравнения элементов
this.compare = new Comparator(fn)
}
}
Реализуем несколько вспомогательных методов:
// Возвращает индекс левого потомка
getLeftChildIndex(parentIndex) {
return 2 * parentIndex + 1
}
// Возвращает индекс правого потомка
getRightChildIndex(parentIndex) {
return 2 * parentIndex + 2
}
// Возвращает индекс предка
getParentIndex(childIndex) {
return Math.floor((childIndex - 1) / 2)
}
// Проверяет наличие предка
hasParent(childIndex) {
return this.getParentIndex(childIndex) >= 0
}
// Проверяет наличие левого потомка
hasLeftChild(parentIndex) {
return this.getLeftChildIndex(parentIndex) < this.heapContainer.length
}
// Проверяет наличие правого потомка
hasRightChild(parentIndex) {
return this.getRightChildIndex(parentIndex) < this.heapContainer.length
}
// Возвращает левого потомка
leftChild(parentIndex) {
return this.heapContainer[this.getLeftChildIndex(parentIndex)]
}
// Возвращает правого потомка
rightChild(parentIndex) {
return this.heapContainer[this.getRightChildIndex(parentIndex)]
}
// Возвращает предка
parent(childIndex) {
return this.heapContainer[this.getParentIndex(childIndex)]
}
// Определяет пустоту кучи
isEmpty() {
return this.heapContainer.length === 0
}
// Возвращает строковое представление кучи
toString() {
return this.heapContainer.toString()
}
Методы получения ссылки на корневой элемент кучи и самого корневого элемента:
// Возвращает ссылку на корневой элемент кучи
// (наименьший для min-кучи, наибольший для max-кучи;
// элемент не удаляется)
peek() {
if (this.isEmpty()) {
return null
}
return this.heapContainer[0]
}
// Удаляет и возвращает корневой элемент кучи
poll() {
if (this.isEmpty()) {
return null
}
if (this.heapContainer.length === 1) {
return this.heapContainer.pop()
}
const item = this.heapContainer[0]
// Перемещаем последний элемент в начало
this.heapContainer[0] = this.heapContainer.pop()
// Просеиваем кучу вниз
this.heapifyDown()
// Возвращаем удаленный элемент
return item
}
Методы добавления и удаления элементов:
// Добавляет элемент в кучу
add(item) {
// Добавляем новый элемент в конец кучи
this.heapContainer.push(item)
// Просеиваем кучу вверх
this.heapifyUp()
return this
}
// Удаляет элемент из кучи.
// Принимает элемент и кастомную функцию сравнения элементов
remove(item, comparator = this.compare) {
// Определяем количество удаляемых элементов
const numberOfItemsToRemove = this.find(item, comparator).length
for (let i = 0; i < numberOfItemsToRemove; i += 1) {
// Определять индекс удаляемого элемента необходимо на каждой итерации,
// поскольку куча каждый раз модифицируется
const index = this.find(item, comparator).pop()
// Последний элемент просто удаляется
if (index === this.heapContainer.length - 1) {
this.heapContainer.pop()
} else {
// Иначе, перемещаем последний элемент на освободившееся место
this.heapContainer[index] = this.heapContainer.pop()
// Получаем родительский элемент
const parentItem = this.parent(index)
// Если предок отсутствует или неправильно расположен,
// просеиваем кучу вниз
if (
this.hasLeftChild(index) &&
(!parentItem ||
this.pairIsInCorrectOrder(parentItem, this.heapContainer[index]))
) {
this.heapifyDown(index)
} else {
// Иначе, просеиваем кучу вверх
this.heapifyUp(index)
}
}
}
return this
}
Метод поиска индексов элементов:
// Находит индексы всех элементов, равных `item`.
// Принимает искомый элемент и кастомную функцию сравнения элементов
find(item, comparator = this.compare) {
const indices = []
for (let i = 0; i < this.heapContainer.length; i += 1) {
if (comparator.equal(this.heapContainer[i], item)) {
indices.push(i)
}
}
return indices
}
Метод перестановки элементов:
// Меняет элементы местами
swap(indexOne, indexTwo) {
const tmp = this.heapContainer[indexOne]
this.heapContainer[indexOne] = this.heapContainer[indexTwo]
this.heapContainer[indexTwo] = tmp
}
Пришло время главных (и самых сложных для понимания) функций кучи.
Функция просеивания кучи вверх:
// Просеивает кучу вверх.
// Принимает кастомный индекс начальной позиции
heapifyUp(customStartIndex) {
// Берем последний элемент (последний в массиве или нижний левый в дереве)
// и поднимаем его наверх до тех пор, пока он не будет
// правильно расположен по отношению к предку
let currentIndex = customStartIndex || this.heapContainer.length - 1
while (
this.hasParent(currentIndex) &&
!this.pairIsInCorrectOrder(
this.parent(currentIndex),
this.heapContainer[currentIndex],
)
) {
this.swap(currentIndex, this.getParentIndex(currentIndex))
currentIndex = this.getParentIndex(currentIndex)
}
}
Функция просеивания кучи вниз:
// Просеивает кучу вниз.
// Принимает кастомный индекс начальной позиции (по умолчанию 0)
heapifyDown(customStartIndex = 0) {
// Сравниваем предка с его потомками и
// меняем местами предка с соответствующим потомком
// (наименьшим для min-кучи, наибольшим для max-кучи).
// Затем делаем тоже самое для следующего потомка
let currentIndex = customStartIndex
let nextIndex = null
// Пока есть левый потомок
while (this.hasLeftChild(currentIndex)) {
// Если есть правый потомок и
// потомки расположены в правильном порядке
if (
this.hasRightChild(currentIndex) &&
this.pairIsInCorrectOrder(
this.rightChild(currentIndex),
this.leftChild(currentIndex),
)
) {
// Следующим индексом является индекс правого потомка
nextIndex = this.getRightChildIndex(currentIndex)
} else {
// Иначе, следующим индексом является индекс левого потомка
nextIndex = this.getLeftChildIndex(currentIndex)
}
// Прерываем цикл, если элементы расположены в правильном порядке
if (
this.pairIsInCorrectOrder(
this.heapContainer[currentIndex],
this.heapContainer[nextIndex],
)
) {
break
}
// Меняем элементы местами
this.swap(currentIndex, nextIndex)
// Обновляем текущий индекс
currentIndex = nextIndex
}
}
Заглушка (или абстрактный метод, или контракт) для метода определения правильного расположения элементов:
// Проверяет, что пара элементов в куче расположена в правильном порядке.
// Для min-кучи первый элемент всегда должен быть меньше или равен второму.
// Для max-кучи первый элемент всегда должен быть больше или равен второму.
// Этот метод должен быть реализован соответствующими подклассами
// (min-кучей и max-кучей)
pairIsInCorrectOrder(firstElement, secondElement) {
throw new Error('Метод сравнения не реализован!')
}
Полный код кучи
// Импортируем конструктор функции сравнения узлов
import Comparator from '../../utils/comparator'
// Родительский класс для min- и max-куч
export default class Heap {
constructor(fn) {
// Кучи должны создаваться с помощью соответствующих подклассов
if (new.target === Heap) {
throw new TypeError('Кучу нельзя создавать напрямую!')
}
// Представление кучи в виде массива
this.heapContainer = []
// Функция сравнения элементов
this.compare = new Comparator(fn)
}
// Возвращает индекс левого потомка
getLeftChildIndex(parentIndex) {
return 2 * parentIndex + 1
}
// Возвращает индекс правого потомка
getRightChildIndex(parentIndex) {
return 2 * parentIndex + 2
}
// Возвращает индекс предка
getParentIndex(childIndex) {
return Math.floor((childIndex - 1) / 2)
}
// Проверяет наличие предка
hasParent(childIndex) {
return this.getParentIndex(childIndex) >= 0
}
// Проверяет наличие левого потомка
hasLeftChild(parentIndex) {
return this.getLeftChildIndex(parentIndex) < this.heapContainer.length
}
// Проверяет наличие правого потомка
hasRightChild(parentIndex) {
return this.getRightChildIndex(parentIndex) < this.heapContainer.length
}
// Возвращает левого потомка
leftChild(parentIndex) {
return this.heapContainer[this.getLeftChildIndex(parentIndex)]
}
// Возвращает правого потомка
rightChild(parentIndex) {
return this.heapContainer[this.getRightChildIndex(parentIndex)]
}
// Возвращает предка
parent(childIndex) {
return this.heapContainer[this.getParentIndex(childIndex)]
}
// Определяет пустоту кучи
isEmpty() {
return this.heapContainer.length === 0
}
// Возвращает строковое представление кучи
toString() {
return this.heapContainer.toString()
}
// Возвращает ссылку на корневой элемент кучи
// (наименьший для min-кучи, наибольший для max-кучи;
// элемент не удаляется)
peek() {
if (this.isEmpty()) {
return null
}
return this.heapContainer[0]
}
// Удаляет и возвращает корневой элемент кучи
poll() {
if (this.isEmpty()) {
return null
}
if (this.heapContainer.length === 1) {
return this.heapContainer.pop()
}
const item = this.heapContainer[0]
// Перемещаем последний элемент в начало
this.heapContainer[0] = this.heapContainer.pop()
// Просеиваем кучу вниз
this.heapifyDown()
// Возвращаем удаленный элемент
return item
}
// Добавляет элемент в кучу
add(item) {
// Добавляем новый элемент в конец кучи
this.heapContainer.push(item)
// Просеиваем кучу вверх
this.heapifyUp()
return this
}
// Удаляет элемент из кучи.
// Принимает элемент и кастомную функцию сравнения элементов
remove(item, comparator = this.compare) {
// Определяем количество удаляемых элементов
const numberOfItemsToRemove = this.find(item, comparator).length
for (let i = 0; i < numberOfItemsToRemove; i += 1) {
// Определять индекс удаляемого элемента необходимо на каждой итерации,
// поскольку куча каждый раз модифицируется
const index = this.find(item, comparator).pop()
// Последний элемент просто удаляется
if (index === this.heapContainer.length - 1) {
this.heapContainer.pop()
} else {
// Иначе, перемещаем последний элемент на освободившееся место
this.heapContainer[index] = this.heapContainer.pop()
// Получаем родительский элемент
const parentItem = this.parent(index)
// Если предок отсутствует или неправильно расположен,
// просеиваем кучу вниз
if (
this.hasLeftChild(index) &&
(!parentItem ||
this.pairIsInCorrectOrder(parentItem, this.heapContainer[index]))
) {
this.heapifyDown(index)
} else {
// Иначе, просеиваем кучу вверх
this.heapifyUp(index)
}
}
}
return this
}
// Находит индексы всех элементов, равных `item`.
// Принимает искомый элемент и кастомную функцию сравнения элементов
find(item, comparator = this.compare) {
const indices = []
for (let i = 0; i < this.heapContainer.length; i += 1) {
if (comparator.equal(this.heapContainer[i], item)) {
indices.push(i)
}
}
return indices
}
// Меняет элементы местами
swap(indexOne, indexTwo) {
const tmp = this.heapContainer[indexOne]
this.heapContainer[indexOne] = this.heapContainer[indexTwo]
this.heapContainer[indexTwo] = tmp
}
// Просеивает кучу вверх.
// Принимает кастомный индекс начальной позиции
heapifyUp(customStartIndex) {
// Берем последний элемент (последний в массиве или нижний левый в дереве)
// и поднимаем его наверх до тех пор, пока он не будет
// правильно расположен по отношению к предку
let currentIndex = customStartIndex || this.heapContainer.length - 1
while (
this.hasParent(currentIndex) &&
!this.pairIsInCorrectOrder(
this.parent(currentIndex),
this.heapContainer[currentIndex],
)
) {
this.swap(currentIndex, this.getParentIndex(currentIndex))
currentIndex = this.getParentIndex(currentIndex)
}
}
// Просеивает кучу вниз.
// Принимает кастомный индекс начальной позиции (по умолчанию 0)
heapifyDown(customStartIndex = 0) {
// Сравниваем предка с его потомками и
// меняем местами предка с соответствующим потомком
// (наименьшим для min-кучи и наибольшим для max-кучи).
// Затем делаем тоже самое для следующего потомка
let currentIndex = customStartIndex
let nextIndex = null
// Пока есть левый потомок
while (this.hasLeftChild(currentIndex)) {
// Если есть правый потомок и
// потомки расположены в правильном порядке
if (
this.hasRightChild(currentIndex) &&
this.pairIsInCorrectOrder(
this.rightChild(currentIndex),
this.leftChild(currentIndex),
)
) {
// Следующим индексом является индекс правого потомка
nextIndex = this.getRightChildIndex(currentIndex)
} else {
// Иначе, следующим индексом является индекс л евого потомка
nextIndex = this.getLeftChildIndex(currentIndex)
}
// Прерываем цикл, если элементы расположены в правильном порядке
if (
this.pairIsInCorrectOrder(
this.heapContainer[currentIndex],
this.heapContainer[nextIndex],
)
) {
break
}
// Меняем элементы местами
this.swap(currentIndex, nextIndex)
// Обновляем текущий индекс
currentIndex = nextIndex
}
}
// Проверяет, что пара элементов в куче расположена в правильном порядке.
// Для min-кучи первый элемент всегда должен быть меньше или равен второму.
// Для max-кучи первый элемент всегда должен быть больше или равен второму.
// Этот метод должен быть реализован соответствующими подклассами
// (min-кучей и max-кучей)
pairIsInCorrectOrder(firstElement, secondElement) {
throw new Error('Метод сравнения не реализован!')
}
}
Таким образом, реализация подклассов сводится к реализации метода pairIsInCorrectOrder
.
Реализация подкласса min-кучи:
// data-structures/heap/min-heap.js
import Heap from '.'
export default class MinHeap extends Heap {
pairIsInCorrectOrder(firstElement, secondElement) {
// Первый элемент должен быть меньше или равен второму
return this.compare.lessThanOrEqual(firstElement, secondElement)
}
}
Реализация подкласса max-кучи:
// data-structures/heap/max-heap.js
import Heap from '.'
export default class MaxHeap extends Heap {
pairIsInCorrectOrder(firstElement, secondElement) {
// Первый элемент должен быть больше или равен второму
return this.compare.greaterThanOrEqual(firstElement, secondElement)
}
}
Тестирование
Проверим, что наша куча работает, как ожидается.
Начнем с суперкласса:
// data-structures/heap/__tests__/heap.test.js
import Heap from '..'
describe('Heap', () => {
it('должен выбросить исключение при попытке создания кучи напрямую', () => {
const instantiateHeap = () => {
const heap = new Heap()
heap.add(5)
}
expect(instantiateHeap).toThrow()
})
})
Тестирование min-кучи
// data-structures/heap/__tests__/min-heap.test.js
import MinHeap from '../min-heap'
import Comparator from '../../../utils/comparator'
describe('MinHeap', () => {
it('должен создать пустую min-кучу', () => {
const minHeap = new MinHeap()
expect(minHeap).toBeDefined()
expect(minHeap.peek()).toBeNull()
expect(minHeap.isEmpty()).toBe(true)
})
it('должен добавить элементы в кучу и просеять ее вверх', () => {
const minHeap = new MinHeap()
minHeap.add(5)
expect(minHeap.isEmpty()).toBe(false)
expect(minHeap.peek()).toBe(5)
expect(minHeap.toString()).toBe('5')
minHeap.add(3)
expect(minHeap.peek()).toBe(3)
expect(minHeap.toString()).toBe('3,5')
minHeap.add(10)
expect(minHeap.peek()).toBe(3)
expect(minHeap.toString()).toBe('3,5,10')
minHeap.add(1)
expect(minHeap.peek()).toBe(1)
expect(minHeap.toString()).toBe('1,3,10,5')
minHeap.add(1)
expect(minHeap.peek()).toBe(1)
expect(minHeap.toString()).toBe('1,1,10,5,3')
expect(minHeap.poll()).toBe(1)
expect(minHeap.toString()).toBe('1,3,10,5')
expect(minHeap.poll()).toBe(1)
expect(minHeap.toString()).toBe('3,5,10')
expect(minHeap.poll()).toBe(3)
expect(minHeap.toString()).toBe('5,10')
})
it('должен извлечь элементы из кучи и просеять ее вниз', () => {
const minHeap = new MinHeap()
minHeap.add(5)
minHeap.add(3)
minHeap.add(10)
minHeap.add(11)
minHeap.add(1)
expect(minHeap.toString()).toBe('1,3,10,11,5')
expect(minHeap.poll()).toBe(1)
expect(minHeap.toString()).toBe('3,5,10,11')
expect(minHeap.poll()).toBe(3)
expect(minHeap.toString()).toBe('5,11,10')
expect(minHeap.poll()).toBe(5)
expect(minHeap.toString()).toBe('10,11')
expect(minHeap.poll()).toBe(10)
expect(minHeap.toString()).toBe('11')
expect(minHeap.poll()).toBe(11)
expect(minHeap.toString()).toBe('')
expect(minHeap.poll()).toBeNull()
expect(minHeap.toString()).toBe('')
})
it('должен просеять кучу вниз по правильной ветке', () => {
const minHeap = new MinHeap()
minHeap.add(3)
minHeap.add(12)
minHeap.add(10)
expect(minHeap.toString()).toBe('3,12,10')
minHeap.add(11)
expect(minHeap.toString()).toBe('3,11,10,12')
expect(minHeap.poll()).toBe(3)
expect(minHeap.toString()).toBe('10,11,12')
})
it('должен находить индексы элементов', () => {
const minHeap = new MinHeap()
minHeap.add(3)
minHeap.add(12)
minHeap.add(10)
minHeap.add(11)
minHeap.add(11)
expect(minHeap.toString()).toBe('3,11,10,12,11')
expect(minHeap.find(5)).toEqual([])
expect(minHeap.find(3)).toEqual([0])
expect(minHeap.find(11)).toEqual([1, 4])
})
it('должен удалять элементы из кучи с ее просеиванием вниз', () => {
const minHeap = new MinHeap()
minHeap.add(3)
minHeap.add(12)
minHeap.add(10)
minHeap.add(11)
minHeap.add(11)
expect(minHeap.toString()).toBe('3,11,10,12,11')
expect(minHeap.remove(3).toString()).toEqual('10,11,11,12')
expect(minHeap.remove(3).peek()).toEqual(10)
expect(minHeap.remove(11).toString()).toEqual('10,12')
expect(minHeap.remove(3).peek()).toEqual(10)
})
it('должен удалять элементы из кучи с ее просеиванием вверх', () => {
const minHeap = new MinHeap()
minHeap.add(3)
minHeap.add(10)
minHeap.add(5)
minHeap.add(6)
minHeap.add(7)
minHeap.add(4)
minHeap.add(6)
minHeap.add(8)
minHeap.add(2)
minHeap.add(1)
expect(minHeap.toString()).toBe('1,2,4,6,3,5,6,10,8,7')
expect(minHeap.remove(8).toString()).toEqual('1,2,4,6,3,5,6,10,7')
expect(minHeap.remove(7).toString()).toEqual('1,2,4,6,3,5,6,10')
expect(minHeap.remove(1).toString()).toEqual('2,3,4,6,10,5,6')
expect(minHeap.remove(2).toString()).toEqual('3,6,4,6,10,5')
expect(minHeap.remove(6).toString()).toEqual('3,5,4,10')
expect(minHeap.remove(10).toString()).toEqual('3,5,4')
expect(minHeap.remove(5).toString()).toEqual('3,4')
expect(minHeap.remove(3).toString()).toEqual('4')
expect(minHeap.remove(4).toString()).toEqual('')
})
it('должен удалить элементы из кучи, найденные с помощью кастомной функции сравнения', () => {
const minHeap = new MinHeap()
minHeap.add('dddd')
minHeap.add('ccc')
minHeap.add('bb')
minHeap.add('a')
expect(minHeap.toString()).toBe('a,bb,ccc,dddd')
const comparator = new Comparator((a, b) => {
if (a.length === b.length) {
return 0
}
return a.length < b.length ? -1 : 1
})
minHeap.remove('hey', comparator)
expect(minHeap.toString()).toBe('a,bb,dddd')
})
it('должен удалить элементы из кучи с правильной реструктуризацией дерева', () => {
const minHeap = new MinHeap()
minHeap.add(1)
minHeap.add(2)
minHeap.add(3)
minHeap.add(4)
minHeap.add(5)
minHeap.add(6)
minHeap.add(7)
minHeap.add(8)
minHeap.add(9)
expect(minHeap.toString()).toBe('1,2,3,4,5,6,7,8,9')
minHeap.remove(2)
expect(minHeap.toString()).toBe('1,4,3,8,5,6,7,9')
minHeap.remove(4)
expect(minHeap.toString()).toBe('1,5,3,8,9,6,7')
})
})
Тестирование max-кучи
// data-structures/heap/__tests__/max-heap.test.js
import MaxHeap from '../max-heap'
import Comparator from '../../../utils/comparator'
describe('MaxHeap', () => {
it('должен создать пустую max-кучу', () => {
const maxHeap = new MaxHeap()
expect(maxHeap).toBeDefined()
expect(maxHeap.peek()).toBeNull()
expect(maxHeap.isEmpty()).toBe(true)
})
it('должен добавить элементы в кучу и просеять ее вверх', () => {
const maxHeap = new MaxHeap()
maxHeap.add(5)
expect(maxHeap.isEmpty()).toBe(false)
expect(maxHeap.peek()).toBe(5)
expect(maxHeap.toString()).toBe('5')
maxHeap.add(3)
expect(maxHeap.peek()).toBe(5)
expect(maxHeap.toString()).toBe('5,3')
maxHeap.add(10)
expect(maxHeap.peek()).toBe(10)
expect(maxHeap.toString()).toBe('10,3,5')
maxHeap.add(1)
expect(maxHeap.peek()).toBe(10)
expect(maxHeap.toString()).toBe('10,3,5,1')
maxHeap.add(1)
expect(maxHeap.peek()).toBe(10)
expect(maxHeap.toString()).toBe('10,3,5,1,1')
expect(maxHeap.poll()).toBe(10)
expect(maxHeap.toString()).toBe('5,3,1,1')
expect(maxHeap.poll()).toBe(5)
expect(maxHeap.toString()).toBe('3,1,1')
expect(maxHeap.poll()).toBe(3)
expect(maxHeap.toString()).toBe('1,1')
})
it('должен извлечь элементы из кучи и просеять ее вниз', () => {
const maxHeap = new MaxHeap()
maxHeap.add(5)
maxHeap.add(3)
maxHeap.add(10)
maxHeap.add(11)
maxHeap.add(1)
expect(maxHeap.toString()).toBe('11,10,5,3,1')
expect(maxHeap.poll()).toBe(11)
expect(maxHeap.toString()).toBe('10,3,5,1')
expect(maxHeap.poll()).toBe(10)
expect(maxHeap.toString()).toBe('5,3,1')
expect(maxHeap.poll()).toBe(5)
expect(maxHeap.toString()).toBe('3,1')
expect(maxHeap.poll()).toBe(3)
expect(maxHeap.toString()).toBe('1')
expect(maxHeap.poll()).toBe(1)
expect(maxHeap.toString()).toBe('')
expect(maxHeap.poll()).toBeNull()
expect(maxHeap.toString()).toBe('')
})
it('должен просеять кучу вниз по правильной ветке', () => {
const maxHeap = new MaxHeap()
maxHeap.add(3)
maxHeap.add(12)
maxHeap.add(10)
expect(maxHeap.toString()).toBe('12,3,10')
maxHeap.add(11)
expect(maxHeap.toString()).toBe('12,11,10,3')
expect(maxHeap.poll()).toBe(12)
expect(maxHeap.toString()).toBe('11,3,10')
})
it('должен находить индексы элементов', () => {
const maxHeap = new MaxHeap()
maxHeap.add(3)
maxHeap.add(12)
maxHeap.add(10)
maxHeap.add(11)
maxHeap.add(11)
expect(maxHeap.toString()).toBe('12,11,10,3,11')
expect(maxHeap.find(5)).toEqual([])
expect(maxHeap.find(12)).toEqual([0])
expect(maxHeap.find(11)).toEqual([1, 4])
})
it('должен удалять элементы из кучи с ее просеиванием вниз', () => {
const maxHeap = new MaxHeap()
maxHeap.add(3)
maxHeap.add(12)
maxHeap.add(10)
maxHeap.add(11)
maxHeap.add(11)
expect(maxHeap.toString()).toBe('12,11,10,3,11')
expect(maxHeap.remove(12).toString()).toEqual('11,11,10,3')
expect(maxHeap.remove(12).peek()).toEqual(11)
expect(maxHeap.remove(11).toString()).toEqual('10,3')
expect(maxHeap.remove(10).peek()).toEqual(3)
})
it('должен удалять элементы из кучи с ее просеиванием вверх', () => {
const maxHeap = new MaxHeap()
maxHeap.add(3)
maxHeap.add(10)
maxHeap.add(5)
maxHeap.add(6)
maxHeap.add(7)
maxHeap.add(4)
maxHeap.add(6)
maxHeap.add(8)
maxHeap.add(2)
maxHeap.add(1)
expect(maxHeap.toString()).toBe('10,8,6,7,6,4,5,3,2,1')
expect(maxHeap.remove(4).toString()).toEqual('10,8,6,7,6,1,5,3,2')
expect(maxHeap.remove(3).toString()).toEqual('10,8,6,7,6,1,5,2')
expect(maxHeap.remove(5).toString()).toEqual('10,8,6,7,6,1,2')
expect(maxHeap.remove(10).toString()).toEqual('8,7,6,2,6,1')
expect(maxHeap.remove(6).toString()).toEqual('8,7,1,2')
expect(maxHeap.remove(2).toString()).toEqual('8,7,1')
expect(maxHeap.remove(1).toString()).toEqual('8,7')
expect(maxHeap.remove(7).toString()).toEqual('8')
expect(maxHeap.remove(8).toString()).toEqual('')
})
it('должен удалить элементы из кучи, найденные с помощью кастомной функции сравнения', () => {
const maxHeap = new MaxHeap()
maxHeap.add('a')
maxHeap.add('bb')
maxHeap.add('ccc')
maxHeap.add('dddd')
expect(maxHeap.toString()).toBe('dddd,ccc,bb,a')
const comparator = new Comparator((a, b) => {
if (a.length === b.length) {
return 0
}
return a.length < b.length ? -1 : 1
})
maxHeap.remove('hey', comparator)
expect(maxHeap.toString()).toBe('dddd,a,bb')
})
})
Запускаем тесты:
npm run test ./data-structures/heap
Результат: