感謝のプログラミング 10000時間

たどり着いた結果(さき)は、感謝でした。

アルゴリズムとデータ構造の「リスト」について

スポンサーリンク

今日はデータ構造について。

配列にデータを突っ込んで、データを見ていくという方法を見てきた。
しかしarray[]みたいな配列に数値を入れていくとすると、「配列の大きさが固定されてしまう」という問題が生じる。
で、ユーザーの都合によって、配列の大きさを拡大したり、縮小したりすることが容易にはできなくなってしまう。

データの数は一体何個あるのか、最初にはわからないのだ。

配列のサイズを拡張するにはけっこう作業効率の悪いことをやらなければならない。

配列を拡張する時は、元の配列を拡張用の配列にコピーして、それから元の配列を解放する、みたいな処理をする。
言わずもがな、これには大量のメモリを消費する。
図にするとこんな感じ。

そこで登場するのが、「リスト」というデータ構造だ。
前のノードへのポインタ、次のノートへのポインタ、データを持つオブジェクトを用意して、ポインタをつなげて位置を把握する。
そうすると、ノードを追加したり削除したり、挿入するときの処理が、「位置情報を示すポインタ」の値を書き換えるだけでできるようになる。
配列の場合は、データが大きくなればなるほど、データを追加する時のコピーの処理で大量のメモリを消費してしまう。

しかし、リストを使ってポインタを書き換える処理を行えば、コピーはしないで位置情報を入れ替えるだけなので、データの大きさに関わらず、データの追加にかかる所要時間は変わらない。
配列はO(N)の所要時間がかかるのに対し、リストはO(1)とされる。
これは、リストはデータの個数が増えても所要時間は変わらない、という意味である。
図にするとこんな感じ。

最後に、リストを実装したRubyのサンプルが以下。

# -*- coding: utf-8 -*-

class ListNodeForList
  def initialize(data)
    @data = data
  end

  attr_accessor :prev, :next ,:data

end

first_node = nil
last_node = nil


begin
  puts "整数を入力してください(0を入力すると終了します)"
  buf = gets.to_i
  new_node = ListNodeForList.new(buf)
  new_node.next = nil
  if (last_node != nil)
    last_node.next = new_node
    new_node.prev = last_node
    last_node = new_node
  else
    first_node  = last_node = new_node
    new_node.prev = nil
  end
end until buf == 0

sum = 0
puts "あなたは以下の数値を入力しましたね?"
this_node = first_node
begin
  puts this_node.data
  sum += this_node.data
  this_node = this_node.next
end until this_node == nil

puts "で、合計は・・・以下の通り!"
puts sum

実行結果はこうなる。

整数を入力してください(0を入力すると終了します)
3
整数を入力してください(0を入力すると終了します)
12
整数を入力してください(0を入力すると終了します)
43
整数を入力してください(0を入力すると終了します)
22
整数を入力してください(0を入力すると終了します)
75
整数を入力してください(0を入力すると終了します)
0
あなたは以下の数値を入力しましたね?
3
12
43
22
75
0
で、合計は・・・以下の通り!
155

アルゴリズムとデータ構造を学ぶときのバイブル

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

プログラミングの宝箱 アルゴリズムとデータ構造 第2版


この本は本当にわかりやすい。
基本情報とかでつまづいてる人も読んだらいいんじゃないかな。

感謝のプログラミング

今回で感謝のプログラミングは【602時間目】
10000時間まで、あと【9398時間】