skillup

技術ブログ

プログラミング全般

データ構造の基礎知識 前編 メモリとポインタ、配列と連結リスト

投稿日:

WEB+DB(vol91)で使えそうな連載記事がありますのでブログにメモリます。

テーマはデータ構造です。

データ構造とは?

主にハッシュと配列。

  • 配列:データを順番に入れる
  • ハッシュ:ラベルにより検索できるがデータの順番は通常保持されない

計算量

コンピューターが行わなければいけない計算の量

プログラムとメモリ

通常プログラムではデータをメモリ(データを置く場所)におく。

ポインタはメモリの番地を指し示すもの(参照なのでデータ自体は入っていない)が入っている。

配列について

配列の宣言

  • 要素分のアドレスが連続した領域に確保される
  • その領域の先頭のアドレスが変数に保存される

メリット

要素が連続して並んでいることと、変数のサイズがわかっていれば、アドレスがわかればその場所をすぐに特定できるため、計算量が少ない

デメリット

逆に要素数の増減に弱い。要素数5→6にしようと思ったときにすぐに増やせない(5番目のメモリの隣がすでに使われていることがあるため、確保できない。)6個分の値がコピーできる領域を探して、一度コピーする必要がある

配列の欠点を補うべくして連結リストが生まれた。

連結リストについて

配列と同じデータ群だが、4つのアドレスが連続している必要はなく、自分自身の値と、次の値の参照だけをもつ

メリット

次の値の参照を持っているので、値の増減が楽。

デメリット

任意のアドレスに飛ぶ場合、各アドレスがばらばらに配置されているため、リストの要素に応じた時間がかかってしまう(100個あった場合、98番目を探したりするのが大変)

ここらへんはWEB+DBの図を見るのがわかりやすいかも.

オーダー記法

アルゴリズムの計算量を測る方法

  • O(1) データ量が増えても変わらない
  • O(logn) データが増えても計算量はゆっくりとしか増えない。数学のlog
  • O(n) データ量に正比例して増える
  • O(n^2) データ量の2乗になる

JavaでいうとArrayListは配列の要素があるのでアクセスに強い

中央部のデータの増減に関してはO(n)になる一方、検索に対してはO(1)

逆にLinkedListは参照なのでデータの増減に対してはO(1)になる一方、検索はO(n)になる。

下記のリンクがわかりやすい

http://d.hatena.ne.jp/syttru/20080406/1207499238

-プログラミング全般

執筆者:


comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

関連記事

no image

バッチスクリプトで気をつけたい点

実務でバッチ処理を作る際に気をつけるべきと思ったこと。 基本的にエラーをいかに捉えていかにログに吐くかを最初に考える。まずはエラーありき。失敗するもの、想定した値がこない、あるいは値がないを前提として …

no image

小〜中規模程度のWEBアプリ作成で気をつけるべきこと

初見の処理系(ライブラリ操作)などは休日などで最小パターンを確認しておくこと。実務で何時間も悩むと非常にストレスがたまる テーブル設計命。あとで終えるようにトレースができるような値を入れておくこと。 …

no image

プログラミングを習得するときに必要な2つの大事なこと

元々私は塾で仕事をしていましたが、いろいろ紆余曲折ありましていまではWEBエンジニアとして仕事をしております。 エンジニアとしてのキャリアは3年ぐらいなので正直あまりないのですが、開発者と平行してプロ …

no image

webの仕組み その2 リクエストとレスポンス

クライアント(ブラウザ)はサーバーとの接続を確立した後、各種リクエストを送信します。サーバーはそれにこたえテキストや画像などのリソースをクライアントに転送します(これがレスポンスです。) Firefo …

no image

コードの分割

今回はリーダブルコードの8章。コードの分割について。 ポイントとしては1行に情報を詰め込みすぎているような場合は分割して、意味がわかりやすい区切りにまとめよう、といったことでしょうか。つまりは「困難は …