はじめに
この記事では動的配列について解説を始めます。
動的配列は静的配列を少し便利にしたようなものになっています。
また動的配列を説明するにあたってリストについても説明します。
リストは抽象データ構造の一つで、プログラマの方には
インターフェースという言葉で説明すると伝わりやすいかもしれません。
この記事からデータ構造らしさが増してくるので面白くなってくると思います。
目次
- 動的配列とは
- プログラムでの動的配列
- 抽象データ構造とは
- リストとは
- さいごに
動的配列とは
静的配列の不便なところである「配列長が変更できない」という
デメリットを補ったデータ構造です。
プログラマーから見るとリストに見えるため便利ですが、
内部的には静的配列を使用しています。
プログラミングを経験した人が最も使ったことがあるであろうデータ構造です。
プログラムでの動的配列
- 各プログラミング言語における動的配列
- 動的配列ではないもの
抽象データ構造とは
抽象データ構造とは、データ構造が実装するべき操作をまとめたもの。 例えばリストという抽象データ構造を実装したデータ構造として、 動的配列と連結リストという2つのデータ構造が挙げられる。
オブジェクト指向のプログラミング言語では、
interface と呼ばれる仕組みとほとんど同じである。
同じ操作でも、データ構造によって計算量が異なることに注意。
リストとは
リストは抽象データ構造の一種である。
想定される操作は以下の通り。
| 想定される操作名 | 疑似コード表記 | 説明 |
|---|---|---|
| 参照 | get(i) |
リスト l の i 番目の要素を参照 |
| 挿入 | insert(e, i) |
リスト l の i 番目に新しい要素 e を挿入 |
| 削除 | delete(i) |
リスト l の i 番目の要素を削除 |
リストを実装した具体的で有名なデータ構造が2つある。
この動画で紹介する動的配列と連結リストである。
動的配列と連結リストにはそれぞれ得手不得手がある。
使用するデータ構造を選ぶ際に、事前に確認できると良い。
| リストの想定される操作 | 動的配列 | 連結リスト |
|---|---|---|
参照 get(i) |
O(1) |
O(n) |
挿入 insert(e, i) |
O(n) |
O(n) / O(1) |
削除 delete(i) |
O(n) |
O(n) / O(1) |
参照が多い処理では動的配列が適している。
挿入や削除が O(1) でできる処理が多い場合は連結リスト。
さいごに
この記事では動的配列とリストについて解説しました。
まだ動的配列のアイデアや中身について話していないので、
次の記事では動的配列についてより詳しく解説していこうと思います。
