Как реализовать связный список?ruby-27

Связный список (Linked List) — это структура данных, состоящая из узлов (nodes), где каждый узел содержит данные и ссылку на следующий узел. В отличие от массивов, элементы связного списка не хранятся в contiguous memory, а связаны через указатели.

Базовый узел

Каждый узел содержит:

  • value — хранимые данные,
  • next — ссылка на следующий узел (или nil, если это последний элемент).
class Node
  attr_accessor :value, :next

  def initialize(value)
    @value = value
    @next = nil
  end
end

Класс связного списка

Реализуем основные операции:

  1. Добавление в конец (#append)
  2. Добавление в начало (#prepend)
  3. Поиск (#find)
  4. Удаление (#delete)
class LinkedList
  attr_reader :head

  def initialize
    @head = nil
  end

  # Добавление в конец (O(n))
  def append(value)
    new_node = Node.new(value)
    if @head.nil?
      @head = new_node
    else
      current = @head
      current = current.next while current.next
      current.next = new_node
    end
  end

  # Добавление в начало (O(1))
  def prepend(value)
    new_node = Node.new(value)
    new_node.next = @head
    @head = new_node
  end

  # Поиск по значению (O(n))
  def find(value)
    current = @head
    while current
      return current if current.value == value
      current = current.next
    end
    nil
  end

  # Удаление узла (O(n))
  def delete(value)
    return if @head.nil?

    if @head.value == value
      @head = @head.next
      return
    end

    current = @head
    while current.next
      if current.next.value == value
        current.next = current.next.next
        return
      end
      current = current.next
    end
  end

  # Вывод списка (для отладки)
  def to_s
    elements = []
    current = @head
    while current
      elements << current.value
      current = current.next
    end
    elements.join(" -> ")
  end
end

Пример использования:

list = LinkedList.new
list.append(10)
list.append(20)
list.prepend(5)
puts list.to_s  #=> "5 -> 10 -> 20"
list.delete(10)
puts list.to_s  #=> "5 -> 20"

Оптимизации

  1. Хвост (Tail): Можно добавить ссылку на последний узел, чтобы append работал за O(1).
  2. Двусвязный список: Если добавить ссылку prev, получится двунаправленный список (удобно для удаления элементов).

Сравнение с массивом

ОперацияСвязный списокМассив
Вставка в началоO(1)O(n)
Вставка в конецO(n) (O(1) с tail)O(1)*
Удаление элементаO(n)O(n)
Доступ по индексуO(n)O(1)

*В Ruby массивы динамические, амортизированная сложность O(1).

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

Вопросы

Собеседования