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

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

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

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

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

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

[value | next] -> [value | next] -> [value | next] -> X (nil)

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

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

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

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

В этом разделе мы сосредоточимся на трех основных аспектах каждого метода:

• Что делает метод и как он это делает.
• Какова его сложность во время выполнения (большой O).
• Исходный код метода.

Но прежде чем перейти к коду, давайте немного поговорим о нотации Big 0.

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

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

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

Теперь, если элемент, который мы ищем, окажется первым элементом в списке, фактическая стоимость времени выполнения для эта конкретная операция будет 1, но общая сложность не изменится. Сложность времени выполнения для поиска по односвязным спискам останется на уровне O(n).

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

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

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

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

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

Вставлять

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

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

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

Удалять

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

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

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

• Голова — единственный узел в списке. Мы устанавливаем голову и хвост на ноль, и все готово.
• В списке больше элементов. Узел, который находится рядом с головкой, становится новой головкой, а исходная головка выходит из области видимости и готовится к «сборке мусора».

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

(В отличие от таких языков, как C, в Ruby нам не нужно вручную освобождать выделенную память. Когда объект выходит из области видимости и на него не указывают ссылки, объект становится пригодным для сборки мусора; с этого момента до сборщик мусора, когда нужно освободить эти выделенные байты.)

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

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 
    tmp = self.head
    while tmp && tmp.next != node
      tmp = tmp.next
    end
    tmp.next = node.next if tmp 
  end 
  self.length -= 1
end

Кошка

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

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

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

чистый

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

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

Найти первым

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

В этом контексте предикат — это функция, которая принимает элемент из списка в качестве единственного аргумента и возвращает логическое значение, указывающее, удовлетворяет ли элемент условиям, выраженным в этой функции.

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

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

def find_first &predicate
  return nil unless block_given?
  
  current = self.head 
  while current 
    return current if predicate.call(current)
    current = current.next
  end
end

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

«Зачаточный» способ (то, что вы видите в большинстве книг) может быть примерно таким:

e = nil
current = list.head
while current
  if current.data == 3
    e = current.data
    break
  end
  current = current.next
end

Используя наш вспомогательный метод, мы получаем тот же результат, но с использованием идиоматического кода Ruby. (Элегантно, лаконично и по делу!)

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

Каждый

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

Если вы не знакомы с языком, это может показаться вам странным, но в Ruby методы могут принимать аргументы и блок кода. Как правило, перечислители возвращают элементы заданному блоку кода (или лямбда-выражению).

Сложность получения следующего элемента составляет O (1). Сложность получения всего списка составляет O(n).

def each
  return nil unless block_given?
  current = self.head
  while current
    yield current
    current = current.next
  end
end

Распечатать

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

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

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

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

Оккуп раз.

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

Списки дел, элементы корзины покупок и журналы только для добавления хорошо подходят для односвязных списков; тогда как карусели, оконные менеджеры и многомиллионные наборы данных — нет.

Итак, это все, что касается односвязных списков. Я надеюсь, что вам понравилось!

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

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

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