アルゴリズムとデータ構造の要点メモ in ruby（連結リスト）

目的

技術面接のために修行を始める。
ウェブでの技術試験時にみやすいようにこのページにまとめる。
Rubyでそそくさと実装できることを目的とする。

配列 https://qiita.com/tsnb/items/983c32d83331de1e0bea

参考

• https://programming-place.net/ppp/contents/algorithm/index.html#header (分かりやすいです、書いた人あざます、この記事をRuby用にまとめてるだけです)

連結リスト（データ構造）

各要素がメモリ上で連続的に並ばず飛び飛びの位置に置かれており、それぞれを何らかの方法で「連結（リンク）」、Cであれば連結にポインタを利用する。

• 単方向で線形なリスト
• 単方向で循環なリスト
• 双方向で線形なリスト
• 双方向で循環なリスト

要点

• 事前に固定的にメモリを確保する必要がなく、必要に応じた伸縮が可能である
• 要素の追加や削除が効率的
• 要素の探索は、先頭からすべての要素をたどるしかないので効率が悪い
• 配列と比べると、nextポインタを保持するために、１要素ごとに余分にメモリを消費することになり、メモリ空間の利用効率はやや劣る

単方向で線形なリスト

• Node=要素と定義
• 要素の末尾にNode追加できる

class Node
  attr_accessor :val, :next

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

class LinkedList
  attr_reader :head

  def initialize(val)
    @head = Node.new(val)
  end

  def add_tail(val)
    node = search_tail(@head)
    node.next = Node.new(val)
  end

private
  # 引数としてNodeを渡してそのNodeの次にNodeを連結させる
  # Nodeを追加することだけが責務
  def append_list(obj, val)
    obj.next = Node.new(val)
  end

  def search_tail(node)
    return node if !node.next
    search_tail(node.next)
  end
end

l = LinkedList.new(1)
l.add_tail(2)
l.add_tail(3)

irb(main):038:0> l.head.val
=> 1
irb(main):039:0> l.head.next.val
=> 2
irb(main):040:0> l.head.next.next.val
=> 3

双方向で線形なリスト

• prevを追加
• 末尾の要素削除（prevを利用） 単方向で要素deleteするのはめんどそう
• head以外の全要素削除（@head.next = nilにして連結を切るだけ）

明示的にインスタンスを削除する方法がわからず、GCされると信じて以下の実装にした

class Node
  attr_accessor :val, :next, :prev

  def initialize(val)
    @val = val
    @next = nil
    @prev = nil
  end
end

class LinkedList
  attr_reader :head

  def initialize(val)
    @head = Node.new(val)
  end

  def add_tail(val)
    node = search_tail(@head)
    node.next = Node.new(val)
    node.next.prev = node
  end

  def del_tail
    new_tail = search_tail(@head).prev
    new_tail.next = nil if !!new_tail
  end

  def clear_list
    @head.next = nil
  end

private
  # 引数としてNodeを渡してそのNodeの次にNodeを連結させる
  # Nodeを追加することだけが責務
  def append_list(obj, val)
    obj.next = Node.new(val)
  end

  def search_tail(node)
    return node if !node.next
    search_tail(node.next)
  end
end

l = LinkedList.new(1)
l.add_tail(2)
l.add_tail(3)
l.add_tail(4)

irb(main):228:0> l.head.next.next.next.val
=> 4
irb(main):229:0> l.del_tail
=> nil
irb(main):230:0> l.head.next.next.next
=> nil
irb(main):231:0> l.clear_list
=> nil
irb(main):232:0> l.head.next
=> nil
irb(main):233:0> l.head
=> #<Node:0x00007fd2a189e628 @val=1, @next=nil, @prev=nil>

双方向で循環なリスト

• 末尾追加時に循環にするかどうかの指定をできるようにする
• 末尾削除時に循環にするかどうかの指定をできるようにする

class Node
  attr_accessor :val, :next, :prev

  def initialize(val)
    @val = val
    @next = nil
    @prev = nil
  end
end

class LinkedList
  attr_reader :head

  def initialize(val)
    @head = Node.new(val)
  end

  def add_tail(val, circulation=false)
    node = search_tail(@head)
    node.next = Node.new(val)
    node.next.prev = node

    if circulation
      node.next.next = @head
      @head.prev = node.next
    end
  end

  def del_tail(circulation=false)
    new_tail = search_tail(@head).prev
    new_tail.next = nil if !!new_tail

    if circulation
      new_tail.next = @head
      @head.prev = new_tail
    end
  end

  def clear_list
    @head.next = nil
  end

private
  # 引数としてNodeを渡してそのNodeの次にNodeを連結させる
  # Nodeを追加することだけが責務
  def append_list(obj, val)
    obj.next = Node.new(val)
  end

  def search_tail(node)
    return node if (!node.next or node.next == @head)
    search_tail(node.next)
  end
end

l = LinkedList.new(1)
l.add_tail(2)
l.add_tail(3, true)
l.del_tail(true)

irb(main):185:0> l = LinkedList.new(1)
=> #<LinkedList:0x00007fd93c8e7908 @head=#<Node:0x00007fd93c8e78b8 @val=1, @next=nil, @prev=nil>>
irb(main):186:0> l.add_tail(2)
=> nil
irb(main):187:0> l.add_tail(3, true)
...
irb(main):189:0> l.head.prev.val #headのprevの値が3で循環している
=> 3
irb(main):190:0> l.head.next.next.val
=> 3
irb(main):192:0> l.head.next.next.next.val # 3のnodeの次がheadになっている
=> 1
irb(main):193:0> l.del_tail(true)
=> #<Node:0x00007fd93c8d4bc8 @val=2, @next=#<Node:0x00007fd93c8e78b8 @val=1, @next=#<Node:0x00007fd93c8d4bc8 ...>, @prev=#<Node:0x00007fd93c8d4bc8 ...>>, @prev=#<Node:0x00007fd93c8e78b8 @val=1, @next=#<Node:0x00007fd93c8d4bc8 ...>, @prev=#<Node:0x00007fd93c8d4bc8 ...>>>
irb(main):195:0> l.head.prev.val # tail削除したのでheadのprevが2のNodeになっている
=> 2
irb(main):196:0> l.head.next.next
=> #<Node:0x00007fd93c8e78b8 @val=1, @next=#<Node:0x00007fd93c8d4bc8 @val=2, @next=#<Node:0x00007fd93c8e78b8 ...>, @prev=#<Node:0x00007fd93c8e78b8 ...>>, @prev=#<Node:0x00007fd93c8d4bc8 @val=2, @next=#<Node:0x00007fd93c8e78b8 ...>, @prev=#<Node:0x00007fd93c8e78b8 ...>>>
irb(main):197:0> l.head.next.next.val # 2の次がheadに循環している
=> 1