takahiro_itazuriの公倍数的ブログ

本やWebを通して学習したことをまとめるブログです。最大公約数(つまり、共通部分)的なという表現と対比して、「なるべく包括的にカバーしつつ、更に+αの要素も加えられたらいいな」という意味で公倍数的ブログと名付けました。

配列

データ構造の第2回目です。
データ構造とアルゴリズムの目次ページはこちら

配列

配列とは「線形に並んだ要素の並びをインデックスで管理するもの」です。
配列には静的配列と動的配列が存在します。

静的配列

静的配列とは「配列の長さを予め決めてしまい、後から変更できないもの」です。
つまり配列を宣言する時に配列の長さ一度決めてしまったら、後から短くしたり長くしたりはできないということです。
C++のコンテナクラスでいうと「std::array」になります。

f:id:takahiro_itazuri:20170707080955p:plain:w500

アクセス(Access

配列は連続するメモリ領域に値を格納しておくため、配列の先頭のアドレスから欲しい要素までのメモリ分を移動したところにアクセスすれば任意の要素にアクセス(ランダムアクセス)することができます。
つまり、どのような長さの配列であっても \mathcal O (1)のオーダーでアクセスすることができます。

挿入(Insert)・削除(Delete)

静的配列は配列の長さを変えない配列であるため、挿入することは出来ません。
そのような用途の場合は他のデータ構造を利用すると良いでしょう。

挿入と同様に配列の長さを変える操作である削除も出来ませんし、そのような場合は他のデータ構造を利用すると良いでしょう。

f:id:takahiro_itazuri:20170709140956p:plain:w500

探索には配列の先頭から順番に調べていく必要があります。
この方法を線形探索(Linear Search)と呼びます。

動的配列

動的配列とは「配列の長さを後から適宜変更することができるもの」です。
C++のコンテナクラスでいうと「std::vector」になります。

f:id:takahiro_itazuri:20170707081636p:plain:w500

アクセス(Access

静的配列と同様に連続するメモリ領域に値を格納しているため、どんな長さの配列であっても \mathcal O (1)のオーダーでアクセスすることができます。

f:id:takahiro_itazuri:20170709140627p:plain:w500

挿入(Insert)・削除(Delete)

動的配列では予め大きめにメモリ領域を確保しておいたりします。
データの最後尾に要素を追加する場合には二つの方法があります。
一つ目は、余分に取っていたメモリ領域を使って要素を追加する方法です。この方法は簡単に理解できるでしょう。

f:id:takahiro_itazuri:20170709140956p:plain:w500

二つ目は、余分に取っていたメモリを使いきっていた場合、新しくさらに大きなメモリ領域を確保し、そこにコピーしてから、要素を追加する方法です。

f:id:takahiro_itazuri:20170709141716p:plain

削除する場合には、基本的にメモリ領域が不足することはないので、削除した要素以降の要素を一つずつ前にずらす必要があります。

このように動的配列は静的配列と異なり、要素の数を増やしたり減らしたりすることが可能です。しかし、メモリ領域が足りなくなる度に新しいメモリを確保したり、要素を一つずつずらす操作には時間がかかるため、頻繁に要素の長さを変更する場合には向いていません。その場合には次に紹介します「リスト」を用いると良いでしょう。

探索(Find, Search)

配列における探索は一番先頭の要素から順番に一つずつ探索していきます。これを「線形探索」と呼びます。