単方向リストは、データ（値）と次の要素への参照（ポインタ）を持つ「ノード」が連なってできたデータ構造で、先頭（ヘッド）から末尾（テール）へ一方向にしかたどれないのが特徴です。電車のように連結されていて、前の要素に戻ることはできませんが、メモリ効率が良く、先頭や末尾へのデータの追加・削除が高速に行える利点があります。
画像参照：https://tellingbook.com/20220425-sample-q3/
特徴
- 構造: 各ノードが「データ」と「次のノードのアドレス（ポインタ）」を持つ。
- 方向性: 次のノードへしか進めず、逆方向（前へ）はたどれない（一方向）。
- メモリ: 配列と異なり、ノードはメモリ上で離れた場所に配置され、ポインタで連結される。
- 利点:
- 先頭への追加・削除が高速（O(1)）。
- メモリが効率的で柔軟。
- 欠点:
- 任意の位置へのアクセス（検索）は先頭から順にたどる必要があり遅い（O(n)）。
- 逆方向には移動できない。
仕組み
- ノード: データと次のノードへのポインタで構成される。
- ヘッド: リストの先頭を示すポインタ。
- テール: リストの末尾（次のノードがない状態を示すNULL値を持つ）。
- 操作: ポインタの指す先を変更することで、データの挿入や削除を行う。
他のリストとの比較
- 双方向リスト: 前後の両方のノードへのポインタを持ち、双方向にたどれる。
- 配列: 連続したメモリ領域に格納され、ランダムアクセスは高速だが、要素の挿入・削除は遅い場合がある（単方向リストとは異なる概念）。
単方向リストは、スタックやキューといった他のデータ構造を実装する際の基礎にもなる重要なデータ構造です。
コメント