テクノロジ
動的配列とは
読み方：どうてきはいれつ
ひとことで言うと：容量不足時に内部領域を拡張しながら要素数を増やせる配列。
意味をわかりやすく解説
動的配列は、要素の追加に応じて格納領域の容量を拡張できる配列です。利用者からはサイズが自由に増えるように見えます。
内部容量が足りなくなると、より大きい連続領域を確保して既存要素をコピーする実装が一般的です。そのため末尾追加は平均的には高速でも、拡張が発生した回はコピーコストがかかります。
具体例
容量4の動的配列に5個目を追加すると、容量8などの新領域を確保し、4要素をコピーしてから5個目を追加する実装があります。
似た用語との違い
静的配列
静的配列はサイズをあらかじめ固定します。動的配列は必要に応じて容量を拡張します。
連結リスト
動的配列は添字アクセスが高速ですが途中挿入で要素移動が必要です。連結リストはランダムアクセスが遅い代わりに、位置が分かればリンク変更で挿入できます。
覚え方
動的配列＝配列の速い添字アクセスを保ちつつ、容量不足時に大きな箱へ引っ越す。
基本情報技術者試験の試験ポイント
末尾追加の平均計算量と、途中挿入・削除で要素移動が必要になる点を押さえます。
CHECK QUESTION
動的配列で途中位置へ要素を挿入すると、なぜ後続要素の移動が必要になることがありますか。
答えを見る
要素を連続した領域に並べるため、挿入位置以降をずらして空きを作る必要があるからです。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。