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

Определяющим фактором циклических связанных списков является то, что они позволяют нам проходить их бесконечно. Поскольку у них не было хвоста, всякий раз, когда список достигает своего «конца», он снова и снова запускается с начала.

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

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

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

Элементы в нашем списке будут иметь два атрибута.

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

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

+--> [data|next] -> [data|next] -> [data|next] ---+| |+-------------------------------------------------+

Интерфейс циклических связанных списков

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

Я делаю это не потому, что мне нравится тратить нажатия клавиш, а потому, что есть некоторые методы из обычных связанных списков, которые не имеют смысла для круговых связанных списков. Например, для Ruby-программиста вполне естественно вызывать метод «каждый» для обхода списка. Проблема в том, что в круговых связанных списках обходы выполняются бесконечно, поэтому эти вызовы в конечном итоге взорвут стек.

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

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

В результате получился стильный C-интерфейс, в основе которого лежит элегантность Ruby.

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

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

Детали реализации

Далее следует краткое описание каждого метода, его сложности и исходного кода.

Инициализировать

Этот метод является конструктором списка. Единственное, что он делает, это создает пустой список, устанавливая заголовок в nil и длину списка в 0.

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

def initialize
  self.head = nil
  self.length = 0
end

Вставлять

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

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

def insert data
    return insert_next(nil, data)       if (self.length == 0)
    return insert_next(self.head, data) if (self.length == 1)
    
    # Finds the last node.
    self.current = head
    i = 0;
    while ((i += 1) < self.length)
        move_next
    end

    # Inserts the new node right after the last node.
    return insert_next(self.current, data)
end

Вставить следующий

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

Insert next позволяет вам вставлять элементы за постоянное время, пока вы держите указатель на узел, который будет предшествовать новому узлу. (Обычно это будет указатель на последний узел, но это не обязательно. Вы можете вставлять элементы в любое место.)

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

Если список уже содержит узлы, мы должны сделать две вещи:

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

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

И, наконец, мы должны настроить длину списка перед возвратом.

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

def insert_next prev_node, data
  new_node = Node.new data
  if self.length == 0
    self.head = new_node.next = new_node
  else
    new_node.next = prev_node.next
    prev_node.next = new_node
  end
  self.length += 1
end

Удалять

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

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

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

def remove node
    return nil unless node
    return nil unless self.length > 0
    
    # head?
    return remove_next node if (self.length == 1)
    
    # Find the precedent node to the node we 
    # want to remove.
    prev = nil
    self.current = self.head
    while ((prev = self.move_next) != node)
    end
    
    remove_next prev
end

Удалить Далее

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

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

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

Если удаляемый элемент не является единственным элементом в списке, а предыдущий узел равен нулю, мы должны:

1. «Захватите» следующий за предыдущим узел.
2. Укажите следующий указатель захваченного узла на тот, который следует за следующим указателем предыдущего узла.
3. Проверьте, является ли узел, который мы захватили ранее, главой списка. Если это так, мы должны указать голову списка на узел, который находится рядом с захваченным узлом.

(Не волнуйтесь, вам будет легко следовать, когда вы увидите код.)

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

def remove_next prev_node
  return nil unless self.length > 0
  unless prev_node
    self.head = self.head.next
  else
    if prev_node.next == prev_node
      self.head = nil
    else
      old = prev_node.next
      prev_node.next = prev_node.next&.next
      if (old == self.head)
        self.head = old.next
      end
    end
  end
  self.length -= 1
end

чистый

Этот метод удаляет все элементы из списка. Так как нам предстоит пройтись по всему списку.

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

def clear
  while self.length > 0
    remove self.head
  end
end

Перейти дальше

Указывает текущий узел на узел, следующий за ним в списке.

Поскольку у нас уже есть указатель на текущий узел, сложность этого метода O (1).

def move_next
  self.current = self.current&.next
end

Полное сканирование

Он проходит по всем элементам в списке без зацикливания.

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

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

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

def full_scan
  return nil unless block_given?
  self.current = self.head
  loop do
    yield self.current
    break if (move_next == self.head)
  end
end

Найти первым

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

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

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

Распечатать

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

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

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

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

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

Например, если вы работаете над оконным менеджером, который позволяет пользователям переключаться между окнами, нажимая Cmd+Tab, кольцевой связанный список будет отлично работать.

def on_key_press e 
  windows.move_next if (e.Super && e.Tab)
end

Если вам нужно поддерживать обратную цикличность (например, когда пользователи нажимают Cmd + Shift + Tab), вместо этого вы можете использовать двусвязные циклические списки.

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

Вот и все для круговых связанных списков. На самом деле весь список я собираюсь охватить. Надеюсь, тебе понравилось!

В следующий раз очереди. Следите за обновлениями!
Спасибо за чтение!