Skip to main content

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

Прямой обход​

Описание

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

Например, для такого связного списка:


Порядок обхода будет следующим:

12 → 99 → 37

Сложность

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

Реализация

Реализация алгоритма до неприличия проста:

// algorithms/linked-lists/traverse.js
// Функция принимает связный список и обработчик посещения узла
export default function traverse(list, cb) {
  // Берем головной узел
  let node = list.head

  // Пока есть узлы
  while (node) {
    // Обрабатываем узел
    cb(node.value)
    // Берем следующий
    node = node.next
  }
}

Тестирование

// algorithms/linked-lists/__tests__/traverse.js
import LinkedList from '../../../data-structures/linked-list'
import traverse from '../traverse'

describe('traverse', () => {
  it('должен обойти связный список в прямом порядке', () => {
    const linkedList = new LinkedList()

    linkedList.append(1).append(2).append(3)

    const nodeValues = []
    const traversalCallback = (nodeValue) => {
      nodeValues.push(nodeValue)
    }

    traverse(linkedList, traversalCallback)

    expect(nodeValues).toEqual([1, 2, 3])
  })
})

Обратный обход​

Описание

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

Например, для такого связного списка:


Порядок обхода будет следующим:

37 → 99 → 12

Сложность

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

Реализация

Для обхода списка в обратном порядке достаточно применить рекурсию:

// algorithms/linked-lists/reversal-traverse.js
// Функция принимает узел и обработчик его посещения
function reversalTraverseRecursive(node, cb) {
  // Пока есть узел
  if (node) {
    // Вызываем функцию со следующим узлом
    reversalTraverseRecursive(node.next, cb)
    // Обрабатываем узел
    cb(node.value)
  }
}

// Функция принимает связный список и обработчик посещения узла
export default function reversalTraverse(list, cb) {
  // Для того, чтобы понять рекурсию, надо сначала понять рекурсию :)
  reversalTraverseRecursive(list.head, cb)
}

Тестирование

// algorithms/linked-lists/__tests__/reversal-traverse.js
import LinkedList from '../../../data-structures/linked-list'
import reversalTraverse from '../reversal-traverse'

describe('reversalTraverse', () => {
  it('должен обойти связный список в обратном порядке', () => {
    const linkedList = new LinkedList()

    linkedList.append(1).append(2).append(3)

    const nodeValues = []
    const traversalCallback = (nodeValue) => {
      nodeValues.push(nodeValue)
    }

    reversalTraverse(linkedList, traversalCallback)

    expect(nodeValues).toEqual([3, 2, 1])
  })
})

Запускаем тесты:

npm run test ./algorithms/linked-lists/__tests__