09.07.2024 08:05
aio350 0 4900 Источник


Привет, друзья!


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


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


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


Интересно? Тогда прошу под кат.


1. Связный список


Описание



Связный (или связанный, или односвязный, или однонаправленный) список (linked list) — это динамическая структура данных, представляющая собой упорядоченную коллекцию узлов (nodes). Каждый узел содержит значение и ссылку (указатель) на следующий узел.





Преимущество связного списка перед массивом заключается в его структурной гибкости: порядок элементов связного списка может не совпадать с порядком их расположения в памяти. Порядок обхода (traverse) списка задается его внутренними связями. Суть преимущества состоит в том, что во многих языках программирования создание массива требует указания его размера (для выделения необходимой памяти), а связный список позволяет обойти это ограничение.


Недостатком связного списка является то, что время доступа к его элементам линейно (соответствует количеству элементов). Быстрый (произвольный) доступ к элементу невозможен.


Сложность


Временная


Чтение Поиск Вставка Удаление
O(n) O(n) O(1) O(n)

Пространственная


O(n)


Реализация


Начнем с реализации вспомогательной функции сравнения узлов:


// utils/comparator
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

Результат:





Отлично! Двигаемся дальше.


2. Двусвязный список



Двусвязный (или двунаправленный) список (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

Результат:





3. Очередь


Описание



Очередь (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

Результат:





4. Стек


Описание



Стек (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

Результат:





На сегодня это все, друзья. Увидимся в следующей части.



Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩

Комментарии (0)