ルックアップテーブル
これは、配列の方が参照の局所性が高くプロセッサのキャッシュの恩恵を受けやすいためである。
連結リストは配列と比較してメモリを多く消費する。これは、次の要素への参照を保持しているためであるが、格納するデータ自体が小さい場合(キャラクタやブール値などの場合)はこのオーバーヘッドが原因で実用性がなくなってしまうこともある。また、新しい要素を格納する際の動的メモリ確保にネイティブアロケータを使用する場合、メモリ確保による速度の低下や使用メモリ量の無駄が発生する場合もあるが、これはメモリプールを使用すれば概ね解決できる。
2つの手法を組み合わせて両方の利点を得ようとする手法もある。Unrolled linked listでは一つの連結リストのノード中に複数の要素を格納することでキャッシュパフォーマンスを向上させるとともに、参照を保持するためのメモリのオーバーヘッドを削減している。同様の目的で使用されるCDRコーディングでは、参照元レコードの終端を伸ばし、参照を実際に参照されるデータで置き換えている。