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

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

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