README.uk-UA.md

Двобічно зв'язаний список

Двобічно зв'язаний список — зв'язкова структура даних в інформатиці, що складається з набору послідовно пов'язаних записів, званих вузлами. Кожен вузол містить два поля, званих посиланнями, які вказують на попередній і наступний елементи послідовність вузлів. Посилання на попередній елемент кореневого вузла та посилання на Наступний елемент останнього вузла вказують на деякого роду переривник, зазвичай сторожовий вузол або null для полегшення обходу списку. Якщо у списку лише один сторожовий вузол, тоді перелік циклічно пов'язаний через нього. Двобічно зв'язаний список можна уявити, як два зв'язкові списки, які утворені з одних і тих самих даних, але розташованих у протилежному порядку.

Made with okso.app

Два посилання дозволяють обходити список в обох напрямках. Додавання та видалення вузла у двозв'язному списку вимагає зміни більшої кількості посилань, ніж аналогічні операції у зв'язковому списку. Однак дані операції простіше та потенційно більш ефективні (для некореневих вузлів) – при обході не потрібно стежити за попереднім вузлом або повторно обходити список у пошуку попереднього вузла, плюс його посилання може бути змінено.

Псевдокод основних операцій

Вставка

Add(value)
  Pre: value - значення, що додається
  Post: value поміщено в кінець списку
  n ← node(value)
  if head = ø
    head ← n
    tail ← n
  else
    n.previous ← tail
    tail.next ← n
    tail ← n
  end if
end Add

Видалення

Remove(head, value)
  Pre: head - перший вузол у списку
       value - значення, яке слід видалити
  Post: true - value видалено зі списку, інакше false
  if head = ø
    return false
  end if
  if value = head.value
    if head = tail
      head ← ø
      tail ← ø
    else
      head ← head.next
      head.previous ← ø
    end if
    return true
  end if
  n ← head.next
  while n = ø and value = n.value
    n ← n.next
  end while
  if n = tail
    tail ← tail.previous
    tail.next ← ø
    return true
  else if n = ø
    n.previous.next ← n.next
    n.next.previous ← n.previous
    return true
  end if
  return false
end Remove

Зворотний обхід

ReverseTraversal(tail)
  Pre: tail - кінцевий елемент обхідного списку
  Post: елементи списку пройдено у зворотному порядку
  n ← tail
  while n = ø
    yield n.value
    n ← n.previous
  end while
end Reverse Traversal

Складність

Часова складність

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

Просторова складність

O(n)

Посилання

• Wikipedia