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

二重リンクリストは、リンクリストのバリエーションであり、単一リンクリストと比較して、順方向と逆方向の両方の方法で簡単にナビゲーションできます。以下は、二重リンクリストの概念を理解するための重要な用語です。

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

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

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

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

二重リンクリスト表現

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

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

  • 各リンクには、データフィールドとnextおよびprevと呼ばれる2つのリンクフィールドがあります。

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

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

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

基本操作

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

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

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

  • Insert Last −リストの最後に要素を追加します。

  • Delete Last −リストの最後から要素を削除します。

  • Insert After −リストの項目の後に要素を追加します。

  • Delete −キーを使用してリストから要素を削除します。

  • Display forward −完全なリストを順方向に表示します。

  • Display backward −完全なリストを逆方向に表示します。

挿入操作

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

//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プログラミング言語での実装を確認するには、ここをクリックしてください。