Rubyの実用的なリンクリスト

これは、「Rubyの実用的なコンピュータサイエンス」シリーズの3番目のエントリです。今日はリンクリストについてお話します。

では、リンクリストとは何ですか？

名前が示すように、リンクリストはデータをリスト形式で保存する方法です（ありがとう、キャプテンオブビシャス！）。

「リンクされた」部分は、データがノードに格納され、これらのノードが順番に相互にリンクされているという事実に由来します。

これはアレイとどう違うのですか？

リンクリストと配列

リンクリストには、配列とは異なるパフォーマンス特性があります。これが、どちらかを選択する理由の1つです。

これは、リンクリストが配列よりも特定のタスクに対してより効率的である可能性があることを意味します。

リンクリストにはインデックス作成やランダムアクセスはありません。つまり、リストの途中にあるアイテムにアクセスすることはできません。 。

リストの「先頭」から始めて、目的のノードが見つかるまで、またはリストの最後までリンクをたどる必要があります。

リンクリストの途中からアイテムを削除（または追加）すると、はるかに高速になります。 。

1つのノードの「次の」ポインタを変更するだけです。

ただし、配列の中央から要素を削除する場合は、ギャップを残し、そのギャップを閉じるには、削除された要素の右側にあるすべての要素を移動する必要があります。

これを頻繁に行う必要がある場合は、あまり効率的ではありません！

配列の中央に挿入する場合は、すべての配列要素を移動して空のスペースを作成する必要があります。

コード例を見てみましょう ：

a = [1,2,3,4,5,6,7,8]

def insert(arr, item, pos)
  tmp      = arr[pos]
  arr[pos] = item

  arr.replace(arr[0..pos] + [tmp] + arr[pos+1..-1])
end

insert(a, 99, 3)
p a

注 ：組み込みのArray＃insertメソッドもありますが、このメソッドがどのように機能するかをお見せしたいと思います。

リストの途中にアイテムを挿入すると、パフォーマンスにどのような影響がありますか？

ベンチマークは次のとおりです：

Comparison:
   LinkedList:  1815407.9 i/s
   Array:       18090.3 i/s - 100.35x  slower

ここでは大きな違いがありますが、LinkedListのサイズにも大きく依存します ノードを検索する必要があるためです。

2つのデータ構造を比較する別の方法は、時間計算量テーブルを調べることです（これは、挿入と削除のためにノードを検索する必要がないことを前提としています）：

実際のアプリケーションをお探しですか？

これがAaronPattersonによるプルリクエストで、リンクリストを使用してRubyGemsを高速化します。

https://github.com/rubygems/rubygems/pull/1188

リンクリストの実装

RubyにはLinkedListは含まれていません クラスなので、独自に作成する必要があります。

次の操作を利用できるようにする必要があります。

• 追加（リストの最後に）
• append_after
• 削除
• 検索

考えられる実装の1つは次のとおりです。

class LinkedList
  def initialize
    @head = nil
  end

  def append(value)
    if @head
      find_tail.next = Node.new(value)
    else
      @head = Node.new(value)
    end
  end

  def find_tail
    node = @head

    return node if !node.next
    return node if !node.next while (node = node.next)
  end

  def append_after(target, value)
    node           = find(target)

    return unless node

    old_next       = node.next
    node.next      = Node.new(value)
    node.next.next = old_next
  end

  def find(value)
    node = @head

    return false if !node.next
    return node  if node.value == value

    while (node = node.next)
      return node if node.value == value
    end
  end

  def delete(value)
    if @head.value == value
      @head = @head.next
      return
    end

    node      = find_before(value)
    node.next = node.next.next
  end

  def find_before(value)
    node = @head

    return false if !node.next
    return node  if node.next.value == value

    while (node = node.next)
      return node if node.next && node.next.value == value
    end
  end

  def print
    node = @head
    puts node

    while (node = node.next)
      puts node
    end
  end
end

この特定の実装はテールを追跡しません。新しいアイテムを追加するときにテールを見つけます。これにより、追加操作が線形時間になります（O(n) ）。以下のビデオでは、前に要素を追加する別の実装を示しています。

そして、これがノードクラスです：

class Node
  attr_accessor :next
  attr_reader   :value

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

  def to_s
    "Node with value: #{@value}"
  end
end

次のように使用できます：

list = LinkedList.new

list.append(10)
list.append(20)
list.append(30)

list.append_after(10, 15)
list.append_after(20, 25)

list.print

これは、基本的な「単一リンクリスト」の実装です。

他の種類のリンクリストもあります ：

• 二重リンクリスト
• 循環リンクリスト

二重リンクリストでは、すべてのノードに2つのポインタがあります。1つは次のノードへのポインタです。 ＆別の前のノード 。

これにより、リストを検索する際の柔軟性が高まりますが、リストに変更を加える場合にも追加の作業が必要になります。

循環リンクリストは二重リンクリストと同じですが、最後のノードがヘッドノードに接続されています。

ビデオ

概要

リンクリストについて学習しました。これは、配列の途中で要素を多数追加および削除する場合に検討できるデータ構造です。

コーディングのインタビューでも取り上げられる可能性があるので、それだけでも学ぶ価値があります。

この投稿を共有することを忘れないでください 下のボタンを使用して、より多くの人々がこの知識から利益を得ることができるようにします🙂