[配列 array] 連続空間の保存 と [リンクリスト linked list] 離散空間の保存 は、2 つの基本的なデータ構造であり、それぞれデータのコンピュータメモリ内での保存方法を表しています。両者の特徴は相補的な特性を示しています。
配列 array#
[配列 array] は、同じ型の要素を連続したメモリ空間に保存する一種の線形データ構造です。配列の長さは不変です。
挿入と削除の欠点：時間のかかる計算量 O (n)、要素の損失、メモリの浪費。
典型的な応用：ランダムアクセス、ソートと検索、ルックアップテーブル、機械学習、データ構造の実装。
リンクリスト linked list#
[リンクリスト linked list] は、各要素がノードオブジェクトであり、ノード間は「参照」によって接続されている一種の線形データ構造です。
参照は次のノードのメモリアドレスを記録しています。リンクリストの設計により、各ノードはメモリ内のさまざまな場所に分散して保存されることができます。
ヘッドノード、テールノード、テールノードは「空」を指しています。
リンクリストは参照を保存するため、配列よりも多くのメモリスペースを占有します。
// **単方向**リンクリスト(singly linked list)
// **典型的な応用：スタックとキュー、ハッシュテーブル、グラフ**
class ListNode {
int val;
ListNode? next;
ListNode(int x) => val = x;
}
// **双方向**リンクリスト(doubly linked list)
// **典型的な応用（前/後の要素の高速検索）：高度なデータ構造、ブラウザの履歴、LRUアルゴリズム。**
class ListNode {
int val;
ListNode? next;
ListNode? prev;
ListNode(int x) => val = x;
}
// **循環**リンクリスト(circular linked list)
// 双方向リンクリストと同様ですが、先頭と末尾が接続されています
// **典型的な応用（周期的な操作）：タイムスライスラウンドロビンスケジューリングアルゴリズム、データバッファ。**
class ListNode {
int val;
ListNode next;
ListNode prev;
ListNode(int x) => val = x;
}