Розуміння зв'язаних списків у Ruby

Зв'язані списки є однією з основних структур даних, які використовуються в програмуванні. Вони дозволяють зберігати колекції елементів, де кожен елемент (вузол) містить посилання на наступний. У цій статті ми розглянемо, що таке зв'язані списки, як їх реалізувати в Ruby, а також їх переваги та недоліки.

Що таке зв'язаний список?

Зв'язаний список — це структура даних, що складається з вузлів, де кожен вузол містить дані та посилання на наступний вузол у списку. Це дозволяє легко додавати та видаляти елементи, оскільки не потрібно переміщати інші елементи, як у масивах.

Типи зв'язаних списків

Однозв'язаний список: Кожен вузол містить посилання лише на наступний вузол.
Двозв'язаний список: Кожен вузол містить посилання на наступний та попередній вузол.
Циклічний список: Останній вузол вказує на перший, утворюючи цикл.

Реалізація однозв'язаного списку в Ruby

Давайте розглянемо, як реалізувати однозв'язаний список у Ruby. Для цього ми створимо клас для вузла та клас для самого списку.

Клас вузла

Клас вузла буде містити дані та посилання на наступний вузол.

class Node
  attr_accessor :data, :next_node

  def initialize(data)
    @data = data
    @next_node = nil
  end
end

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

Тепер створимо клас для зв'язаного списку, який буде містити методи для додавання, видалення та виведення елементів.

class LinkedList
  attr_accessor :head

  def initialize
    @head = nil
  end

  def append(data)
    new_node = Node.new(data)
    if @head.nil?
      @head = new_node
    else
      current = @head
      current = current.next_node while current.next_node
      current.next_node = new_node
    end
  end

  def display
    current = @head
    while current
      print "#{current.data} -> "
      current = current.next_node
    end
    puts "nil"
  end

  def delete(data)
    return if @head.nil?

    if @head.data == data
      @head = @head.next_node
      return
    end

    current = @head
    while current.next_node && current.next_node.data != data
      current = current.next_node
    end

    if current.next_node
      current.next_node = current.next_node.next_node
    end
  end
end

Використання зв'язаного списку

Тепер, коли ми реалізували наш зв'язаний список, давайте подивимося, як його використовувати.

list = LinkedList.new
list.append(1)
list.append(2)
list.append(3)

puts "Список після додавання елементів:"
list.display

list.delete(2)
puts "Список після видалення елемента 2:"
list.display

Переваги та недоліки зв'язаних списків

Як і будь-яка структура даних, зв'язані списки мають свої переваги та недоліки.

Переваги

Динамічний розмір: Зв'язані списки можуть змінювати свій розмір під час виконання програми, що робить їх гнучкими.
Легкість у вставці та видаленні: Додавання та видалення елементів не вимагає переміщення інших елементів, як у масивах.

Недоліки

Витрати пам'яті: Кожен вузол потребує додаткової пам'яті для зберігання посилання на наступний вузол.
Повільніший доступ: Доступ до елементів у зв'язаному списку повільніший, ніж у масивах, оскільки потрібно проходити через вузли.

Висновок

Зв'язані списки є потужним інструментом для зберігання та маніпуляції даними. Вони пропонують гнучкість у додаванні та видаленні елементів, але можуть бути менш ефективними в плані пам'яті та швидкості доступу. Розуміння цієї структури даних є важливим кроком у розвитку ваших навичок програмування на Ruby.

Сподіваємося, що ця стаття допомогла вам краще зрозуміти зв'язані списки та їх реалізацію в Ruby. Якщо у вас є питання або ви хочете дізнатися більше, не соромтеся звертатися!