データ構造とアルゴリズム-リンクリスト

リンクリストは、リンクを介して相互に接続された一連のデータ構造です。

リンクリストは、アイテムを含む一連のリンクです。各リンクには、別のリンクへの接続が含まれています。リンクリストは、配列に次いで2番目に使用されるデータ構造です。以下は、リンクリストの概念を理解するための重要な用語です。

  • Link −リンクリストの各リンクには、要素と呼ばれるデータを格納できます。

  • Next −リンクリストの各リンクには、Nextと呼ばれる次のリンクへのリンクが含まれています。

  • LinkedList −リンクリストには、Firstと呼ばれる最初のリンクへの接続リンクが含まれています。

リンクリスト表現

リンクリストは、すべてのノードが次のノードを指すノードのチェーンとして視覚化できます。

上図のように、考慮すべき重要な点は次のとおりです。

  • リンクリストには、firstというリンク要素が含まれています。

  • 各リンクには、データフィールドとnextと呼ばれるリンクフィールドがあります。

  • 各リンクは、次のリンクを使用して次のリンクにリンクされます。

  • 最後のリンクは、リストの終わりを示すためにnullとしてリンクを運びます。

リンクリストの種類

以下は、さまざまなタイプのリンクリストです。

  • Simple Linked List −アイテムのナビゲーションは前方のみです。

  • Doubly Linked List −アイテムは前後に移動できます。

  • Circular Linked List −最後の項目には、次のように最初の要素のリンクが含まれ、最初の要素には前のように最後の要素へのリンクがあります。

基本操作

以下は、リストでサポートされている基本的な操作です。

  • Insertion −リストの先頭に要素を追加します。

  • Deletion −リストの先頭にある要素を削除します。

  • Display −完全なリストを表示します。

  • Search −指定されたキーを使用して要素を検索します。

  • Delete −指定されたキーを使用して要素を削除します。

挿入操作

リンクリストに新しいノードを追加することは、複数のステップのアクティビティです。ここで図を使ってこれを学びます。まず、同じ構造を使用してノードを作成し、それを挿入する必要がある場所を見つけます。

ノードを挿入していると想像してください B (NewNode)、間 A (LeftNode)と C(RightNode)。次に、C-の隣のB.

NewNode.next −> RightNode;

このようになります-

これで、左側の次のノードが新しいノードを指すようになります。

LeftNode.next −> NewNode;

これにより、新しいノードが2つの中間に配置されます。新しいリストは次のようになります-

ノードがリストの先頭に挿入されている場合も、同様の手順を実行する必要があります。最後に挿入している間、リストの最後から2番目のノードは新しいノードを指し、新しいノードはNULLを指します。

削除操作

削除も複数のステップのプロセスです。絵で学びましょう。まず、検索アルゴリズムを使用して、削除するターゲットノードを見つけます。

ターゲットノードの左側(前の)ノードは、ターゲットノードの次のノードを指す必要があります-

LeftNode.next −> TargetNode.next;

これにより、ターゲットノードを指していたリンクが削除されます。ここで、次のコードを使用して、ターゲットノードが指しているものを削除します。

TargetNode.next −> NULL;

削除したノードを使用する必要があります。これをメモリに保持できます。それ以外の場合は、メモリの割り当てを解除して、ターゲットノードを完全に消去できます。

逆の操作

この操作は徹底的なものです。最後のノードがヘッドノードによってポイントされるようにし、リンクリスト全体を逆にする必要があります。

まず、リストの最後までトラバースします。NULLを指している必要があります。ここで、前のノードを指すようにします-

最後のノードが最後のノードではないことを確認する必要があります。したがって、最後のノードを指すヘッドノードのように見える一時ノードがいくつかあります。ここで、すべての左側のノードが前のノードを1つずつ指すようにします。

ヘッドノードが指すノード(最初のノード)を除いて、すべてのノードは前のノードを指し、新しい後継ノードにする必要があります。最初のノードはNULLを指します。

一時ノードを使用して、ヘッドノードが新しい最初のノードを指すようにします。

リンクリストが逆になります。Cプログラミング言語でのリンクリストの実装を確認するには、ここをクリックしてください。