データ構造

目次

SPL では、標準的なデータ構造を提供しています。 ここで、それらを実装ごとに分類してまとめます。

双方向リンクリスト

双方向リンクリスト (Doubly Linked List: DLL) は、双方向のノードへのリンクを持つノードのリストです。 イテレータの操作、両隣へのアクセス、ノードの追加や削除のコストは、 データ構造が DLL の場合は O(1) となります。 これは、スタックやキューを実装するのに適しています。

ヒープ

ヒープは、ツリー風の構造です。ヒープ特有の性質として、 個々のノードはその子ノードと等しいかそれより大きな値となります。 値の比較は、ヒープ全体の比較メソッドとして実装されているものを使用します。

配列

配列は、データを連続的に格納してインデックス経由でアクセスできるようにした構造です。 PHP の配列と混同しないようにしましょう。PHP の配列は、 実際のところは順序つきハッシュテーブルとして実装されています。

マップ

マップは、キー/値 のペアからなるデータ構造です。 PHP の配列は、整数値/文字列を値と対応させたマップとみなすことができます。 SPL では、オブジェクトとデータを対応させるマップを提供しています。 このマップは、オブジェクトの集合として扱うことができます。