二重リンクリスト: C++, Python (Code 例）

⚡ スマートサマリー

二重リンクリストは線形データ構造であり、各ノードはデータに加えて、前のノードへのポインタと次のノードへのポインタの2つを格納します。そのため、順方向と逆方向の両方に効率的に移動できます。

🧩 ノード構造： 二重リンクリストの各ノードには、データフィールド、 前のページ 前のノードへのポインタ、そして次の次のノードへのポインタ。
🔁 双方向トラバーサル： 追加の「前の」ポインタにより、アルゴリズムは先頭から末尾、末尾から先頭へと走査することが可能になります。これは単方向連結リストでは不可能なことです。
➕ 挿入 Operaション： ノードは、先頭、末尾、対象ノードの後、または対象ノードの前に、定数時間または線形時間で追加できます。
➖ 削除 Operaション： 先頭ノード、末尾ノード、または一致したノードを削除すると、隣接ノードのprevポインタとnextポインタの両方が更新され、解放されたメモリが解放されます。
💻 C++ (NAIST) と Python Code: 完全な実装では、挿入、削除、検索、および走査ルーチンが実行可能な出力とともに示されます。
📊 複雑： 先頭または末尾への挿入または削除のコストはO(1)です。検索コストは平均でO(n)です。全体の空間計算量はO(n)です。
🏭 用途： デック、LRUキャッシュ、ブラウザの履歴、アンドゥ/リドゥスタック、音楽プレーヤーのプレイリストなどは、二重リンクリストに依存している。

二重リンクリストとは何ですか？

二重リンクリストでは、各ノードは前のノードと次のノードの両方へのリンクを持っています。各ノードは3つの要素で構成されます。1つはデータを保持し、残りの2つは次のノードと前のノードへのポインタです。これらの2つのポインタは、特定のノードから前後に移動するのに役立ちます。

二重リンクリストの基本的な構造は以下のとおりです。

二重リンクリストの構造

すべての連結リストには先頭ノードと末尾ノードがあります。先頭ノードには 前のページ （前のポインタ）ノード、そして末尾ノードには次のノード。

二重リンクリストに関する重要な用語をいくつか紹介します。

前のページ： 各ノードは前のノードにリンクされています。ポインタまたはリンクとして使用されます。
次の投稿： 各ノードは次のノードにリンクされます。ポインタまたはリンクとして使用されます。
日付： これはノードにデータを保存するために使用されます。データは他のものを保持できますデータ構造その内部には、文字列、辞書、セット、ハッシュマップなどの構造体を格納できます。

二重リンクリストにおける単一ノードの基本的な構造は以下のとおりです。

二重リンクリストのノードの構造

Opera二重リンクリストの構成

二重リンクリストの操作には、ノードの追加、削除、挿入、および削除、ならびにリストを上から下または下から上に走査することが含まれます。

二重リンクリストに対して実行可能な操作の一覧は以下のとおりです。

前で挿入
末端または最後のノードへの挿入
ノードの後に挿入
ノードの前に挿入
前から削除
末尾からの削除
ノードの検索と削除
頭から尾までトラバースする
尾部から頭までトラバースする

これらの各操作の実装と擬似コードを以下に示します。

二重リンクリストの先頭への挿入

先頭への挿入とは、連結リストにノードを作成し、それをリストの先頭に配置することを意味します。

例えば、あるノードが与えられたとします。 15ヘッドノードとして追加する必要があります。

この操作を実行する際には、以下の2つの重要な条件が適用されます。

二重リンクリストが空の場合、新しいノードが先頭ノードになります。
既に先頭ノードが存在する場合、以前の先頭ノードは新しいノードに置き換えられます。

この操作の擬似コードは以下のとおりです。

function insertAtFront(ListHead, value):
  newNode = Node()
  newNode.value = value
  ListHead.prev = newNode
  newNode.next = ListHead
  newNode.prev = NULL
  return ListHead

フロントノードへの挿入

二重リンクリストの末尾への挿入

末尾への挿入とは、連結リストにノードを作成し、それを末尾に配置することを意味します。

この操作を実行するには、次の2つの方法があります。

方法1： 二重リンクリストの先頭から順にたどっていき、次の null になります。次に、新しいノードをリンクします。次のポインター。
方法2： 二重リンクリストの最後のノードを取ります。次に、次の最後のノードのポインタが新しいノードを指す。新しいノードが末尾ノードとなる。

末尾ノードへの挿入を表す擬似コードは以下のとおりです。

function insertAtTail(ListHead, value):
  newNode = Node()
  newNode.value = value
  newNode.next = NULL
  while ListHead.next is not NULL:
    ListHead = ListHead.next
  newNode.prev = ListHead
  ListHead.next = newNode
  return ListHead

リンクされたリストの最後に挿入

ノードの後の挿入

以下のような既存の二重リンクリストを考えてみましょう。

目標は、指定されたノードを、そのノードの値の後にリンクすることです。 12.

ステップ1） 先頭から最後のノードまでをたどります。どのノードに値があるかを確認します。 12.

ステップ2） 新しいノードを作成し、それをノードの次のポインターとして割り当てます。 12を選択します。次の新しいノードのノード数は15になります。

二重リンクリストにおいて、ノードの後にノードを挿入するための擬似コードを以下に示します。

function insertAfter(ListHead, searchItem, value):
  List = ListHead
  newNode = Node()
  newNode.value = value
  while List.value is not equal searchItem:
    List = List.next
  newNode.next = List.next
  newNode.prev = List
  List.next = newNode

ノードの後の挿入

ノードの前への挿入

この操作は、ノードの後に挿入する操作に似ています。特定のノード値が検索され、その後、新しいノードが作成されて、検索されたノードの前に挿入されます。

指定されたノードを挿入するには 15 ノードの前 12、次の手順を実行します：

ステップ1） リンクされたリストを先頭ノードから末尾ノードまでたどります。

ステップ2） 現在のノードの次のポインターが値を持っているかどうかを確認します 12.

ステップ3） 新しいノードを挿入します次の現在のノードのノード。

二重リンクリストにおいて、ノードの前にノードを挿入するための擬似コードを以下に示します。

function insertBefore(ListHead, searchItem, value):
  List = ListHead
  newNode = Node()
  newNode.value = value
  while List.next.value is not equal searchItem:
    List = List.next
  newNode.next = List.next
  newNode.prev = List
  List.next = newNode

ノードの前にノードを挿入する

二重リンクリストの先頭要素を削除する

二重リンクリストの先頭ノードには前のノードがありません。次の現在のヘッドが削除されると、ポインタが新しいヘッドノードになります。削除されたノードが占有していたメモリを解放することも必要です。

ヘッドノードを削除する手順は以下のとおりです。

ステップ1） 現在のヘッドノードに変数を割り当てます。

ステップ2） 仕様書や製品情報の確認は、次の現在のヘッドノードのノードを作成し、 前のページ ポインタがNULLです。これにより、2番目のノードが1番目のノードから切断されます。

ステップ3） 前の先頭ノードが占有していたメモリを解放します。

二重リンクリストから先頭要素を削除するための擬似コードを以下に示します。

function deleteHead(ListHead):
  PrevHead = ListHead
  ListHead = ListHead.next
  ListHead.prev = NULL
  PrevHead.next = NULL
  free memory(PrevHead)
  return ListHead

ヘッドノードの削除

削除後には、割り当てられたメモリを解放する必要があります。そうしないと、削除されたブロックのメモリはプログラムの実行中ずっと占有されたままになり、他のアプリケーションはそのメモリ領域を使用できなくなります。

二重リンクリストの末尾を削除する

この操作は、先頭の削除に似ています。先頭の代わりに末尾が削除されます。ノードが末尾であるかどうかを識別するには、次のポインタがNULLかどうかを確認します。末尾を削除した後、メモリを解放する必要があります。

この手術は、 背面からの削除.

これを行う手順は次のとおりです。

ステップ1） 二重リンクリストの末尾ノードまで走査します。

ステップ2） 変数またはポインターを末尾ノードに割り当てます。

ステップ3） をセットする次の NULLへのポインタを生成し、末尾ノードのメモリを解放します。

末尾ノードを削除するための擬似コードは以下のとおりです。

function deleteTail(ListHead):
  head = ListHead
  while ListHead.next is not NULL:
    ListHead = ListHead.next
  Tail = ListHead
  ListHead.prev.next = NULL
  free memory(Tail)
  return head

二重リンクリストからノードを検索して削除する

この操作では、特定のノード値を検索し、そのノードを削除します。連結リストは線形データ構造であるため、線形検索が必要です。削除後、メモリを解放する必要があります。

二重リンクリスト内のノードを検索および削除する手順は以下のとおりです。

ステップ1） リンクリストの先頭から順にたどり、ノードの値が検索項目と一致するまで進みます。

ステップ2） 変数に値を代入する ノードの削除 一致したノードへ。

ステップ3） 前のノードをリンクします ノードの削除 次のノードへ移動し、次のノードの 前のページ 前のノードへのポインタ。

ステップ4） 記憶を解放する ノードの削除.

以下は、連結リストからノードを検索および削除するための擬似コードです。

function searchAndDelete(ListHead, searchItem):
  head = ListHead
  while head.value not equals searchItem:
    head = head.next
  deleteNode = head
  head.prev.next = head.next
  if head.next is not NULL:
    head.next.prev = head.prev
  free memory(deleteNode)
  return ListHead

検索と削除操作

二重リンクリストを前方から走査する

先頭ノードから順に走査し、NULLが見つかるまで次のノードを順に処理します。各ノードを走査する際に、その値を表示できます。順方向走査の手順は以下のとおりです。

ステップ1） 現在のヘッドノードにポインターまたは変数を割り当てます。

ステップ2） NULL になるまで、先頭の次のノードを繰り返します。

ステップ3） 各反復処理でノードデータを出力します。

ステップ4） ヘッドノードを返します。

二重リンクリストを先頭から走査するための擬似コードを以下に示します。

function traverseFromFront(ListHead):
  head = ListHead
  while head not equals NULL:
    print head.data
    head = head.next
  return ListHead

返却は必須ではありませんが、操作後にヘッドノードを返却することは良い習慣です。

二重リンクリストを後方から走査する

この操作は、正面からのトラバースの逆です。アプローチは同じですが、1つだけ小さな違いがあります。まず終点ノードに到達し、次にヘッドに向かって後ろ向きに歩きます。 前のページ ポインター。

二重リンクリストを末尾から走査する手順は以下のとおりです。

ステップ1） 末端ノードに到達するまで辿ります。

ステップ2） 末端ノードから、以下を使用してトラバースします。 前のページ 前のノードがNULLになるまで。 前のページ ヘッドノードのポインタがnullです。

ステップ3） 各反復処理において、ノードデータを出力する。

後方から走査するための擬似コードを以下に示します。

function traverseFromBack(ListHead):
  head = ListHead
  while head.next is not NULL:
    head = head.next
  tail = head
  while tail is not NULL:
    print tail.value
    tail = tail.prev
  return ListHead

単方向リンクリストと双方向リンクリストの違い

単方向連結リストと双方向連結リストの主な違いは、各ノードが持つリンクの数です。

単方向連結リストと双方向連結リストのノードの違いは以下のとおりです。

フィールド	単方向リスト	二重リンクリスト
Structure	単方向リスト XNUMX つのデータフィールドと次のノードへの XNUMX つのリンクがあります。	二重リンクリストには XNUMX つのデータフィールドと XNUMX つのリンクがあります。 XNUMX つは前のノード用で、もう XNUMX つは次のノード用です。
トラバーサル	頭から尾までしか移動できません。	前方にも後方にも横断できます。
メモリ	メモリの占有量が少なくなります。	単方向連結リストよりも多くのメモリを消費します。
ユーザー補助	単方向連結リストは、次のノードへのリンクが1つしかないため、効率が劣ります。前のノードへのリンクはありません。	双方向アクセスにおいては、双方向リンクリストは単方向リンクリストよりも効率的です。

二重リンクリスト C++

以下は完全なものです C++ 挿入、削除、検索、走査操作を備えた二重リンクリストの実装。

#include<iostream>
using namespace std;
struct node{
  int data;
  struct node *next;
  struct node *prev;
};
void insertFront(node* &listHead, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  if(listHead != NULL){
    listHead->prev = newNode;
    newNode->next = listHead;
  }
  listHead = newNode;
  cout<<"Added "<<value<<" at the front"<<endl;
}
void insertEnd(node* &listHead, int value){
  if(listHead == NULL){
    insertFront(listHead, value);
    return;
  }
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL){
    head = head->next;
  }
  head->next = newNode;
  newNode->prev = head;
  cout<<"Added "<<value<<" at the end"<<endl;
}
void insertAfter(node* &listHead, int searchValue, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL && head->data != searchValue){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  newNode->prev = head;
  if(newNode->next != NULL){
    newNode->next->prev = newNode;
  }
  cout<<"Inserted "<<value<<" after node "<<searchValue<<endl;
}
void insertBefore(node* &listHead, int searchValue, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL && head->next->data != searchValue){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  newNode->prev = head;
  if(newNode->next != NULL){
    newNode->next->prev = newNode;
  }
  cout<<"Inserted "<<value<<" before node "<<searchValue<<endl;
}
void traverseFromFront(node *listHead){
  node* head = listHead;
  cout<<"Traversal from head:\t";
  while(head != NULL){
    cout<<head->data<<"\t";
    head = head->next;
  }
  cout<<endl;
}
void traverseFromEnd(node *listHead){
  node* head = listHead;
  cout<<"Traversal from tail:\t";
  while(head->next != NULL){
    head = head->next;
  }
  node *tail = head;
  while(tail != NULL){
    cout<<tail->data<<"\t";
    tail = tail->prev;
  }
  cout<<endl;
}
void searchAndDelete(node **listHead, int searchItem){
  node* head = (*listHead);
  while(head != NULL && head->data != searchItem){
    head = head->next;
  }
  if(*listHead == NULL || head == NULL) return;
  if((*listHead)->data == head->data){
    *listHead = head->next;
  }
  if(head->next != NULL){
    head->next->prev = head->prev;
  }
  if(head->prev != NULL){
    head->prev->next = head->next;
  }
  free(head);
  cout<<"Deleted Node\t"<<searchItem<<endl;
}
int main(){
  node *head = NULL;
  insertFront(head, 5);
  insertFront(head, 6);
  insertFront(head, 7);
  insertEnd(head, 9);
  insertEnd(head, 10);
  insertAfter(head, 5, 11);
  insertBefore(head, 5, 20);
  traverseFromFront(head);
  traverseFromEnd(head);
  searchAndDelete(&head, 7);
  traverseFromFront(head);
  traverseFromEnd(head);
}

出力

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversal from head:    7  6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6  7
Deleted Node    7
Traversal from head:    6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6

二重リンクリスト Python

以下は完全なものです Python ノードとリスト自体にクラスを使用した二重リンクリストの実装。

class Node:
  def __init__(self, data=None, prev=None, next=None):
    self.data = data
    self.next = next
    self.prev = prev
class DoublyLinkedList:
  def __init__(self):
    self.head = None
  def insertFront(self, val):
    newNode = Node(data=val)
    newNode.next = self.head
    if self.head is not None:
      self.head.prev = newNode
    self.head = newNode
    print("Added {} at the front".format(val))
  def insertEnd(self, val):
    newNode = Node(data=val)
    if self.head is None:
      self.head = newNode
      print("Added {} at the end".format(val))
      return
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    newNode.prev = temp
    print("Added {} at the end".format(val))
  def traverseFromFront(self):
    temp = self.head
    print("Traversing from head:\t", end="")
    while temp is not None:
      print("{}\t".format(temp.data), end="")
      temp = temp.next
    print()
  def traverseFromEnd(self):
    temp = self.head
    print("Traversing from tail:\t", end="")
    while temp.next is not None:
      temp = temp.next
    tail = temp
    while tail is not None:
      print("{}\t".format(tail.data), end="")
      tail = tail.prev
    print()
  def insertAfter(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp
    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} after node {}".format(value, searchItem))
  def insertBefore(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp
    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} before node {}".format(value, searchItem))
  def searchAndDelete(self, searchItem):
    temp = self.head
    while temp is not None and temp.data != searchItem:
      temp = temp.next
    if self.head is None or temp is None:
      return
    if self.head.data == temp.data:
      self.head = temp.next
    if temp.next is not None:
      temp.next.prev = temp.prev
    if temp.prev is not None:
      temp.prev.next = temp.next
    print("Deleted Node\t{}".format(searchItem))
doublyLinkedList = DoublyLinkedList()
doublyLinkedList.insertFront(5)
doublyLinkedList.insertFront(6)
doublyLinkedList.insertFront(7)
doublyLinkedList.insertEnd(9)
doublyLinkedList.insertEnd(10)
doublyLinkedList.insertAfter(5, 11)
doublyLinkedList.insertBefore(5, 20)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()
doublyLinkedList.searchAndDelete(7)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()

出力

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversing from head:   7  6  20  5  11  9  10
Traversing from tail:   10  9  11  5  20  6  7
Deleted Node    7
Traversing from head:   6  20  5  11  9  10
Traversing from tail:   10  9  11  5  20  6

二重リンクリストの複雑さ

時間計算量は一般的に、最良の場合、平均的な場合、最悪の場合の3種類に分類されます。

二重リンクリストの最良のケースにおける時間の計算量:

先頭または末尾への挿入は、連結リスト内部の走査が不要なため、O(1)の計算量で済みます。先頭ポインタと末尾ポインタによって、先頭ノードと末尾ノードに直接アクセスできます。
先頭または末尾の削除にはO(1)のコストがかかります。
ノードの検索コストは、対象ノードがヘッドノードの場合、O(1)です。

二重リンクリストの平均的なケースにおける時間の計算量:

先頭または末尾への挿入にはO(1)のコストがかかります。
先頭または末尾の削除にはO(1)のコストがかかります。
ノードの検索にはO(n)のコストがかかります。なぜなら、ターゲットはリスト内のどこにでも存在する可能性があるからです。 n ノードの合計数です。

二重リンクリストの最悪ケースの時間計算量は、平均的なケースと同じです。

二重リンクリストのメモリ複雑度

メモリの複雑さはO(n)であり、 n これはノードの総数です。リンクリストを実装する際には、メモリを解放する必要があります。そうしないと、大きなリンクリストではメモリリークが発生します。

二重リンクリストの応用

双方向リンクリストは、双方向走査によって多くの一般的な操作が簡素化されるため、現実世界の様々なデータ構造で利用されています。

LRUキャッシュ: 最も最近使用されていないキャッシュは、O(1)の先頭への移動と削除のためにハッシュマップを備えた二重リンクリストを使用します。
ブラウザの履歴： 戻る/進むナビゲーションは、リンクされたリストをどちらの方向にも移動します。
元に戻す/やり直しスタック: エディタとIDE trac前後のポインタを持つk個のドキュメントバージョン。
デク： Double両端キューは、両端からO(1)の時間でプッシュとポップを行う。
音楽プレイリスト: 前へと次へ trackボタンは、前後のポインタに依存しています。

よくあるご質問

二重リンクリストは、深層学習のバッチパイプラインやベクトルストアのフロントエンドで使用されるLRUキャッシュのバックエンドであり、AIシステムが最近アクセスされたテンソルをO(1)の時間で先頭に移動させ、高速に再利用できるようにします。

はい。GitHub CopilotとGPTはC言語で完全な二重リンクリストを生成できます。 C++, Java, PythonまたはRustで記述され、挿入、削除、検索、逆方向走査のメソッド、および単体テストが含まれます。

単方向連結リストは次のノードへのポインタを1つ持ち、一方向にのみ走査します。双方向連結リストは前方向と後方向の両方のポインタを持ち、前後に走査しますが、より多くのメモリを使用します。

一般的な応用例としては、LRUキャッシュ、ブラウザの戻る/進む履歴、エディタのアンドゥ/リドゥスタック、デックの実装、プレイリストのナビゲーション、オペレーティングシステムのスレッドスケジューリングなどが挙げられる。

先頭または末尾での挿入または削除はO(1)です。任意の位置での検索、挿入、または削除はO(n)です。各ノードが追加のprevポインタを格納するため、空間計算量はO(n)です。

二重リンクリストは、両端での挿入と削除がO(1)で、動的メモリ割り当てが可能です。配列は、ランダムアクセスがO(1)で、キャッシュの局所性も優れています。ワークロードに応じて選択してください。

リストを一周する間、各ノードのprevポインタとnextポインタを交換します。ループが終了したら、headポインタを以前のtailポインタに更新します。この操作はO(n)の時間で実行されます。

はい。循環二重リンクリストは、末尾の次のポインタを先頭に、先頭の前のポインタを末尾に接続します。この構造は、ラウンドロビン方式のスケジューリングやバッファリングで使用されます。

二重リンクリスト: C++, Python (Code 例）

二重リンクリストとは何ですか？

Opera二重リンクリストの構成

二重リンクリストの先頭への挿入

二重リンクリストの末尾への挿入

ノードの後の挿入

ノードの前への挿入

二重リンクリストの先頭要素を削除する

二重リンクリストの末尾を削除する

二重リンクリストからノードを検索して削除する

二重リンクリストを前方から走査する

二重リンクリストを後方から走査する

単方向リンクリストと双方向リンクリストの違い

二重リンクリスト C++

出力

二重リンクリスト Python

出力

二重リンクリストの複雑さ

二重リンクリストの応用

よくあるご質問

この投稿を要約すると次のようになります:

ニュースレターに登録する

二重リンクリストとは何ですか？

Opera二重リンクリストの構成

二重リンクリストの先頭への挿入

二重リンクリストの末尾への挿入

ノードの後の挿入

ノードの前への挿入

関連記事

二重リンクリストの先頭要素を削除する

二重リンクリストの末尾を削除する

二重リンクリストからノードを検索して削除する

二重リンクリストを前方から走査する

二重リンクリストを後方から走査する

単方向リンクリストと双方向リンクリストの違い

二重リンクリスト C++

出力

二重リンクリスト Python

出力

二重リンクリストの複雑さ

二重リンクリストの応用

よくあるご質問

この投稿を要約すると次のようになります:

ニュースレターに登録する