データ構造-二重リンクリスト

二重リンクリストは、リンクリストのバリエーションであり、単一リンクリストと比較して、前方向と後方向のどちらでも簡単にナビゲーションが可能です。以下は、二重リンクリストの概念を理解するための重要な用語です。

リンク-リンクリストの各リンクは、要素と呼ばれるデータを保存できます。
Next -リンクリストの各リンクには、Nextという次のリンクへのリンクが含まれています。
Prev -リンクリストの各リンクには、Prevと呼ばれる前のリンクへのリンクが含まれています。
LinkedList -リンクリストには、Firstという最初のリンクとLastという最後のリンクへの接続リンクが含まれています。

二重リンクリスト表現

二重リンクリスト

上記の図に従って、考慮すべき重要な点を次に示します。

二重リンクリストには、firstおよびlastというリンク要素が含まれています。
各リンクには、データフィールドと、nextおよびprevと呼ばれる2つのリンクフィールドがあります。
各リンクは、次のリンクを使用して次のリンクにリンクされます。
各リンクは、前のリンクを使用して前のリンクにリンクされます。
最後のリンクは、リストの終わりを示すためにリンクをヌルとして運びます。

基本操作

リストでサポートされる基本的な操作は次のとおりです。

挿入-リストの先頭に要素を追加します。
削除-リストの先頭にある要素を削除します。
最後に挿入-リストの最後に要素を追加します。
Delete Last -リストの最後から要素を削除します。
挿入後-リストの項目の後に要素を追加します。
削除-キーを使用してリストから要素を削除します。
前方表示-完全なリストを前方に表示します。
後方に表示-完全なリストを後方に表示します。

挿入操作

次のコードは、二重リンクリストの先頭での挿入操作を示しています。

例

//insert link at the first location
void insertFirst(int key, int data) {

  //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;

   if(isEmpty()) {
     //make it the last link
      last = link;
   } else {
     //update first prev link
      head->prev = link;
   }

  //point it to old first link
   link->next = head;

  //point first to new first link
   head = link;
}

削除操作

次のコードは、二重リンクリストの先頭にある削除操作を示しています。

例

//delete first item
struct node *deleteFirst() {

  //save reference to first link
   struct node* tempLink = head;

  //if only one link
   if(head->next == NULL) {
      last = NULL;
   } else {
      head->next->prev = NULL;
   }

   head = head->next;

  //return the deleted link
   return tempLink;
}

操作の終了時の挿入

次のコードは、二重リンクリストの最後の位置での挿入操作を示しています。

例

//insert link at the last location
void insertLast(int key, int data) {

  //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;

   if(isEmpty()) {
     //make it the last link
      last = link;
   } else {
     //make link a new last link
      last->next = link;

     //mark old last node as prev of new link
      link->prev = last;
   }

  //point last to new last node
   last = link;
}

Cプログラミング言語での実装を確認するには、リンクしてください：/data_structures_algorithms/doubly_linked_list_program_in_c [ここをクリック]。

Data-structures-algorithms-doubly-linked-list-algorithm

目次