Освоение структур данных в Ruby — двусвязные списки

Основное различие между односвязными и двусвязными списками заключается в том, что в последнем каждый элемент содержит указатель на предшествующий ему элемент. Это позволяет нам пройтись по списку от хвоста к голове а также удалять элементы за постоянное время.

Если вы не читали мой предыдущий пост об односвязных спискахЯ рекомендую вам это сделать, потому что на этот раз мы собираемся работать над тем, что мы построили в прошлый раз.

В двусвязных списках элементы представлены узлами, содержащими три атрибута:

  • Значение, которое содержит элемент.
  • Указатель на следующий узел в списке.
  • Указатель на предыдущий узел в списке.

Как и в односвязных списках, первый элемент списка называется «головой», а последний — «хвостом».

Границы двусвязных списков разграничиваются предыдущим указателем первого элемента и следующим указателем последнего. Оба указателя должны быть установлены в ноль.

X <-[prev|data|next] <-> [prev|data|next] <-> [prev|data|next] -> X

Что касается сложности операций, то односвязные и двусвязные списки работают практически одинаково, единственная разница заключается в методе удаления. Поскольку в двусвязном списке каждый узел содержит указатель на предыдущий узел, удаления составляют O (1).

* Примечание. Если вы не знакомы с нотацией Big O или не знаете наверняка, что означает «сложность операций», вы можете проверить мой предыдущий пост где я замалчивал эти понятия.

Интерфейс двусвязных списков

Если вы посмотрите на таблицу ниже, то заметите, что определение интерфейса для двусвязных списков почти такое же, как и для односвязных списков. Это хорошая новость для нас, потому что, поскольку мы собираемся создать двусвязный список, расширяющий односвязныебольшая часть кода уже написана 😉

(Методы, которые мы должны добавить или переопределить, выделены в жирный текст ).

Чтобы не повторяться (и не тратить при этом ваше время), я не буду включать подробности о методах, унаследованных от односвязного списка, потому что вы можете увидеть их в предыдущем посте. Я сосредоточусь только на двусвязных списках.

Вставлять

Создает новый узел для вставки значения в список. Если в списке нет узлов, новый узел становится главой списка; в противном случае он добавляется в конце списка.

Поскольку список содержит указатели на начало и конец, сложность этого метода составляет O(1).

Обратите внимание, что когда список содержит элементы, мы должны установить предыдущий указатель узла, который мы собираемся вставить, так, чтобы он указывал на конец списка.

def insert data
  node = Node.new data
  unless head 
    self.head = node
  else
    node.prev = self.tail
    self.tail.next = node 
  end
  self.tail = node
  self.length += 1
end

Удалять

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

Если узел, который мы должны удалить, является головным в списке, нам нужно охватить две ситуации:

  1. Голова — единственный узел в списке. Мы устанавливаем голову и хвост на ноль, и все готово.
  2. Голова — не единственный узел в списке. Узел, который находится рядом с головкой, становится новой головкой, а исходная головка выходит за пределы области действия.

Если узел, который мы должны удалить, не находится во главе списка, нам нужно только настроить указатели, чтобы оставить целевой узел вне области действия. Во-первых, мы должны установить следующий указатель узла, который предшествует целевому узлу, чтобы он указывал на узел, следующий за целевым. Во-вторых, мы должны установить предыдущий указатель узла, который находится рядом с целевым узлом, чтобы он указывал на узел, который ему предшествует.

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

def remove node
  return nil unless node
  if node == head
    if head.next.nil?
      self.head = self.tail = nil
    else
      self.head = self.head.next
    end
  else
    p = node.prev
    n = node.next 
    p&.next = n
    n&.prev = p
  end
  self.length -= 1
end

Если вы не заметили, на этот раз нам не нужно было просматривать список, чтобы найти узел, который предшествует элементу, который мы хотим удалить, и, следовательно, эта операция O (1).

Кошка

Этот метод позволяет нам объединить два списка вместе и разделен на 4 этапа:

  1. Укажите предыдущий указатель головы списка, который мы добавляем к хвосту текущего списка.
  2. Наведите следующий указатель хвоста текущего списка на начало списка, который мы добавляем.
  3. Установите хвост текущего списка в конец списка, который мы добавляем.
  4. Отрегулируйте текущую длину списка.

Сложность этого метода составляет O(1).

def cat list
  return nil unless list
  
  list.head.prev = self.tail
  self.tail.next = list.head
  self.tail      = list.tail
  self.length += list.length
end

Найти последний

Этот метод позволяет получить последний элемент списка, удовлетворяющий заданному предикату. (Или первое вхождение, начинающееся с хвоста.)

Способ, которым мы находим последний элемент, заключается в обходе списка от конца к началу, применяя предикат к каждому элементу, пока результат этой операции не станет истинным или список не будет исчерпан.

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

def find_last &predicate
  return nil unless block_given?
  current = self.tail
  while current
    return current if predicate.call(current)
    current = current.prev
  end
end

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

Как и в случае с односвязными списками, давайте сначала попробуем «зачаточный» способ:

e = nil
current = list.tail
while current
  if current.data == 3
    e = current.data
    break
  end
  current = current.prev
end

Теперь элегантный и рубиновый «идиоматический» способ:

e = list.find_last { |item| item.data == 3; }

Перевернуть каждый

Этот метод проходит по списку от конца к началу, выдавая по одному элементу за раз, пока не достигнет конца списка.

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

  • Сложность получения предыдущего элемента составляет O (1).
  • Сложность получения всего списка составляет O(n).
def reverse_each
  return nil unless block_given?
  current = self.tail
  while current
    yield current
    current = current.prev
  end
end

Обратная печать

Этот метод печатает содержимое текущего списка в обратном порядке.

def reverse_print
  if self.length == 0
    puts "empty"
  else
    self.reverse_each { |item| puts item.data }
  end
end

Когда использовать двусвязные списки

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

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

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

Итак, это все о двусвязных списках. Я надеюсь, что вам понравилось!
В следующий раз, Круговые связанные списки. Оставайтесь на связи!

Спасибо за чтение!

Похожие записи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *