Rubyで学ぶリンクリストの基礎と実装：配列との違いからコード例まで徹底解説

本記事は「Practical Computer Science in Ruby」シリーズの第3回です。今回はリンクリスト(連結リスト)について詳しく解説します。

リンクリストとは何か?

名前の通り、リンクリストとはデータをリスト形式で格納するためのデータ構造です。

「リンク(連結)」という言葉が示すように、データはノードと呼ばれる単位に保存され、これらのノードが順番に互いに連結される仕組みになっています。

リンクリストと配列の違い

リンクリストは配列とは異なるパフォーマンス特性を持っています。それが、用途に応じてどちらかを選ぶ理由の一つです。つまり、特定のタスクにおいては、リンクリストの方が配列より効率的な場合があるということです。

リンクリストの弱点:ランダムアクセスができない

リンクリストにはインデックス(添字)が存在せず、ランダムアクセスもできません。つまり、リストの中間にある要素に直接アクセスすることはできません。

目的のノードを見つけるには、リストの「先頭(head)」から出発し、リンクをたどって目的のノードを見つけるまで、あるいはリストの末尾まで順番に進む必要があります。

リンクリストの強み:中間への挿入・削除が高速

一方で、リンクリストの中間から要素を削除(または追加)するのは非常に高速です。必要な作業は、あるノードの「next(次)」ポインタを変更するだけだからです。

対照的に、配列の中間から要素を削除すると隙間(ギャップ)が生じます。その隙間を埋めるには、削除した要素より右側にあるすべての要素を移動させなければなりません。

この操作を頻繁に行う必要がある場合、あまり効率的とは言えませんね。同様に、配列の中間に要素を挿入する場合も、空きスペースを作るために後続のすべての要素をずらす必要があります。

配列への挿入のコード例

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

補足:Rubyには組み込みの Array#insert メソッドも存在しますが、ここではその内部動作を理解してもらうためにあえて自前で実装しています。

ベンチマークで見るパフォーマンス差

リンクリストの中間に要素を挿入すると、パフォーマンスにはどのような影響があるのでしょうか?以下がベンチマーク結果です。

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

大きな差が出ていますね。ただし、挿入前にノードを検索する必要があるため、この結果は LinkedList のサイズにも大きく依存します。

データ構造を比較するもう一つの方法として、計算量(時間複雑度)の表を見てみましょう(挿入・削除時にノード検索が不要な場合を想定)。

実際の活用例

現実世界での応用例をお探しですか?Aaron Patterson氏によるプルリクエストでは、リンクリストを使ってRubyGemsを高速化しています。

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

Rubyでのリンクリスト実装

Rubyには組み込みの LinkedList クラスが用意されていないため、自分で作成する必要があります。

以下の操作が使えるようにしましょう。

• append(リストの末尾に追加)
• append_after(指定ノードの後に追加)
• delete(指定値のノードを削除)
• find(指定値のノードを検索)

LinkedListクラスの実装例

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

この実装では末尾(tail)を保持していないため、新しい要素を追加するたびに末尾を探しに行きます。そのため、append操作は線形時間 O(n) となります。下記の動画では、先頭に要素を追加する別の実装方法をご紹介しています。

Nodeクラスの実装

続いて、ノードを表すクラスは以下のようになります。

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

これは基本的な「片方向リンクリスト(Singly-Linked List)」の実装です。

その他のリンクリストの種類

リンクリストには他にも以下のような種類があります。

• 双方向リンクリスト(Doubly-Linked List)
• 循環リンクリスト(Circular Linked List)

双方向リンクリストでは、各ノードが2つのポインタを持ちます。1つは次のノードへのポインタ、もう1つは前のノードへのポインタです。

これにより、リストの検索時により柔軟な操作が可能になりますが、リストを変更する際には追加の手間が必要になります。

循環リンクリストは双方向リンクリストと似ていますが、最後のノードが先頭のノードにつながっている点が異なります。

動画解説

まとめ

今回はリンクリストについて学びました。配列の中間で頻繁に要素の追加・削除を行うような場面では、このデータ構造を検討する価値があります。

また、コーディング面接でもリンクリストは頻出テーマの一つです。それだけのためでも学んでおく価値は十分にあるでしょう。

最後に、下のボタンからぜひこの記事をシェアしてください。より多くの人々がこの知識の恩恵を受けられます 🙂