リスト (コンピューティング)について詳しく解説

導入

この記事は、コンピューティングにおける単語リストの使用に関するものです。単語リストのより一般的な定義については、ウィクショナリーを参照してください。

コンピューティングにおいて、リストは、自由にアクセスできるようにデータをグループ化するためのデータ構造です (それぞれ FIFO モードと LIFO モードでアクセスされるキューやスタックとは異なります)。

リストは、スタック、キュー、ツリーなどのより複雑なデータ構造の基礎となります。データ構造としてのリストの重要性は、 LISP (List Processing) プログラミング言語の基礎となっているほどです。

プリミティブ

リストを操作するために一般的に使用されるプリミティブを次に示します。リスト操作プリミティブには標準化がありません。したがって、彼らの名前は非公式に示されています。

基本的なプリミティブ:

• 「挿入」: リストに項目を追加します。対応する英語用語：「Add」。
• 「削除」: リストから項目を削除します。対応する英語用語：「Remove」。
• 「リストは空ですか？」 »: リストが空の場合は「true」を返し、それ以外の場合は「false」を返します。対応する英語用語：「Isnil」。
• 「リストの要素数」: リストの要素数を返します。対応する英語用語：「Length」。

よく見かける補助プリミティブ:

• 「First」: リスト内の最初の要素を返します。対応する英語用語：「First」。
• 「Last」: リスト内の最後の要素を返します。対応する英語用語：「Last」。
• 「次へ」: リスト内の次の項目を返します。対応する英語用語：「Next」。
• 「前」: リスト内の前の要素を返します。対応する英語用語：「Previous」。
• 「検索」: リストに特定の要素が含まれているかどうかを検索し、その位置を返します。対応する英語用語:「Find」。

リストの種類

リストは要素のコンテナであり、各要素にはdataと、リスト内のデータの取得を可能にするその他の情報が含まれます。この情報の性質 (タイプ) は、異なるタイプのリストを特徴付けます。

一般に、次の 2 種類のリストを区別できます。

• テーブル、
• リンクされたリスト。

絵画

要素へのアクセスは、構造内の要素の位置を表すインデックスを使用して行われます。

配列内に存在するデータはメモリ内で連続しています。これにより、配列サイズが固定、つまり変更されなくなります。ただし、一部の高級言語では、用途に応じてサイズが変更される配列が提供されており、これは動的サイズ配列と呼ばれます。ただし、その実装ではリンク リストの原理が使用されます (下記を参照)。

配列は、一連のインデックスで表される複数の次元を持つこともできます。この場合、 n が配列の次元である場合 ( nはゼロ以外の自然整数)、次元1 (シーケンスの^最初のインデックス) の配列の要素はそれぞれ、次の別の (サブ) 配列を指します。次元n-1 。

リンクされたリスト

単純にリンクされたリスト。それぞれ値 12、99、および 37 を持つ 3 つの要素で構成されます。

配列とは異なり、リンク リストのサイズには、使用可能なメモリ以外の制限はありません。この制限は、リンク リストのタイプに応じて、再帰的定義を使用して各要素がリストの 1 つ以上の要素を指すことができるという事実によって克服されます。したがって、リンク リストのサイズを増やすには、単に新しい要素を作成し、リスト内にすでに存在する特定の要素を新しい要素に向けるだけです。

リンク リストには主に 2 つのタイプがあります。

• 単純にリンクされたリスト: 各要素には、リスト内の次の要素 (または後続要素) へのポインタがあります。ルートは一方向のみです。
• 二重リンクリスト: 各要素には、次の要素 (または後続要素) と前の要素 (または先行要素) への 2 つのポインターがあります。この旅は、後継者から後継者へ、または前任者から前任者へという、互いに反対の 2 つの方向に行うことができます。

これに、サイクルというプロパティを追加できます。今度は、リンクされたリストがループを形成します。リストの「最後」に到達し、続行しようとするとすぐに、リストの「最初」の要素にいることに気付きます。この場合、チェーンの開始または終了という概念はもはや存在する理由がありません。