配列と連結リストは、データを並べる最も基本的な構造。それぞれの長所・短所と使い分けを理解しましょう。
日野 こむぎ
プログラムでデータを並べるって、どうやるの?
藤森 さやか 先生
基本となるのは配列と連結リストよ。
青木 澪
配列はメモリ上に連続して並べる。
インデックスで一発アクセスできるので O(1) の高速アクセスが可能だけど、サイズが固定で要素挿入・削除が遅いの。
桃井 すみれ
連結リストは違うんですかぁ?
青木 澪
連結リストは各要素が「次の要素のアドレス」を持つ形ね。
サイズは可変で挿入・削除は速い (O(1)) けど、特定の要素にアクセスするには先頭から辿る必要があるから O(n) になるの。
日野 こむぎ
なるほど、トレードオフなんだね。
要は用途で使い分けるってことかぁ!
藤森 さやか 先生
そうそう、用途で使い分けるのよ。
アクセス頻度が高ければ配列、要素の挿入・削除が頻繁なら連結リスト。
ちなみにPythonの list は内部的には配列に近いのよ。
青木 澪
補足すると、発展形に双方向リストや循環リストもあるわ。
桃井 すみれ
わぁ、色々あるんですねぇ♪
確認クイズ
配列と連結リストの特徴比較として正しいものはどれか。
- 配列はランダムアクセスがO(n)、連結リストはO(1)
- 配列はランダムアクセスがO(1)、連結リストはO(n)
- 両方ともO(1)
- 両方ともO(n)
こたえを見る
正解: 2. 配列はランダムアクセスがO(1)、連結リストはO(n)
配列はインデックスで直接アドレス計算できるためO(1)。連結リストは先頭から辿る必要があるためO(n)です。一方、要素の挿入削除は配列がO(n)、連結リストがO(1)になります。