二重リンクリスト: C++, Python (コード例)
サラ・チェン
二重リンクリストとは何ですか?
二重リンクリストでは、各ノードには前と次の両方のノードへのリンクがあります。 各ノードは XNUMX つの要素で構成されます。XNUMX つはデータを保持し、他の XNUMX つは次と前のノードのポインターです。 これら XNUMX つのポインターは、特定のノードから前進または後退するのに役立ちます。
二重リンクリストの基本構造は次のとおりです。
すべてのリンクされたリストには先頭ノードと末尾ノードがあります。 Head ノードには「prev」(前のポインタ) ノードがありません。また、tail ノードには「next」ノードがありません。
二重リンクリストに関する重要な用語をいくつか示します。
- 前のページ： 各ノードは前のノードにリンクされています。 ポインタまたはリンクとして使用されます。
- 次の投稿： 各ノードは次のノードにリンクされます。 ポインタまたはリンクとして使用されます。
- 日付： これはノードにデータを保存するために使用されます。 「データ」には他のものを保持できます データ構造 その中。 たとえば、文字列、辞書、セット、ハッシュマップなどを「データ」に保存できます。
二重リンク リストの単一ノードの基本構造は次のとおりです。
Opera二重リンクリストの構成
二重リンク リストの操作には、ノードの追加と削除、ノードの挿入と削除、リンク リストの上から下へのトラバースが含まれます。
二重リンクリストを使用して実装できる操作のリストは次のとおりです。
- 前で挿入
- 末尾または最後のノードへの挿入
- ノードの後に挿入
- ノードの前に挿入
- 前から削除
- 末尾からの削除
- ノードの検索と削除
- 頭から尾までトラバースする
- 尾部から頭までトラバースする
上記のすべての操作の実装と疑似コードを確認します。
二重リンクリストの前への挿入
前に挿入するということは、リンク リストにノードを作成し、それをリンク リストの先頭に配置する必要があることを意味します。
たとえば、特定のノード「15」があります。 これをヘッド ノードに追加する必要があります。
この操作を実行する際の重要な条件が 2 つあります。
- 二重リンク リストにノードがない場合、新しいノードがヘッド ノードになります。
- すでにヘッド ノードがある場合は、前のヘッドが新しいノードに置き換えられます。
この操作の疑似コードは次のとおりです。
function insertAtFront (ListHead, value): newNode = Node() newNode.value = value ListHead.prev = NewNode NewNode.next = ListHead newNode.prev = NULL return ListHead
二重リンクリストの最後に挿入
「最後に挿入」とは、リンクされたリストにノードを作成し、それを最後に配置することを意味します。
これを実行するには、次の XNUMX つの方法を使用できます。
- 方法1： 二重リンクリストの先頭から「次」が null になるまでトラバースを開始します。 次に、新しいノードを「次」にリンクします。
- 方法2： 二重リンクリストの最後のノードを取得します。 次に、最後のノードの「次」のノードが新しいノードにリンクします。 これで、新しいノードが末尾ノードになります。
末尾ノードに挿入するための疑似コードは次のとおりです。
function insertAtTail(ListHead, value): newNode = Node() newNode.value = value newNode.next = NULL while ListHead.next is not NULL: then 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 then List = ListHead.next 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 then List = ListHead.next NewNode.next = List.next NewNode.prev = List List.next = NewNode
二重リンクリストの先頭を削除
前のノードを持たない二重リンク リストのヘッド ノード。 したがって、ヘッド ノードを削除する場合、次のポインターは新しいヘッド ノードになります。 ノードを削除する際には、ノードが占有しているメモリを解放する必要もあります。
ヘッド ノードを削除する手順は次のとおりです。
ステップ1） 現在のヘッド ノードに変数を割り当てます。
ステップ2） 現在のヘッド ノードの「次」ノードに移動し、「前」(前のポインタ) ノードを「NULL」にします。 これは、XNUMX 番目のノードを最初のノードから切断していることを意味します。
ステップ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.next ListHead.next = NULL free memory( Tail ) return head
二重リンクリストからノードを検索して削除します
この操作により、特定のノード データを検索し、そのノードを削除できます。リンク リストは線形データ構造であるため、線形検索を実行する必要があります。削除後、メモリを解放する必要もあります。
二重リンクリスト内のノードを検索および削除する手順は次のとおりです。
ステップ1） ノードの値が検索項目と等しくなるまで、リンクされたリストを先頭からたどります。
ステップ2） 一致したノードに変数「deleteNode」を割り当てます。
ステップ3） 「deleteNode」の前のノードを次のノードに割り当てます。
ステップ4） 「deleteNode」のメモリを解放します。
リンクリストからノードを検索して削除するための疑似コードは次のとおりです。
function SearchAndDelete(ListHead, searchItem): head = ListHead while ListHead.next.value not equals searchItem: head = head.next deleteNode = head.next head.next = head.next.next head.next.prev = head deleteNode.next, deleteNode.next = NULL free memory(deleteNode) return ListHead
二重リンクリストを前方から走査する
ヘッド ノードからトラバースし、「NULL」が見つかるまで次のノードを反復します。 各ノードを走査しながら、ノードの値を出力できます。 正面（前方向）から横切る手順は次のとおりです。
ステップ1） 現在のヘッド ノードにポインターまたは変数を割り当てます。
ステップ2） 「NULL」になるまでヘッドの次のノードまで繰り返します。
ステップ3） 各反復でノードのデータを出力します。
ステップ4） ヘッド ノードを返します。
二重リンクリストを前から走査するための疑似コードは次のとおりです。
function traverseFromFront(ListHead): head = ListHead while head not equals to NULL: print head.data head = head.next return ListHead
ここで、戻りは必須ではありません。ただし、操作後にヘッドノードを返すことをお勧めします。
二重リンクリストを後方からたどる
この操作は、前方からのトラバースの逆です。アプローチは少し異なりますが、同じです。エンド ノードまでトラバースしてから、エンド ノードからフロント ノードまでトラバースする必要があります。
二重リンクリストを後ろからたどる手順は次のとおりです。
ステップ1） 尾部ノードに到達するまでトラバースします。
ステップ2） 末尾ノードから、前のノードが「NULL」になるまでトラバースします。 ヘッド ノードの「prev」(前のポインター) は null になります。
ステップ3） 各反復でノード データを出力します。
以下は、後方から横断するための疑似コードです。
function traverseFromBack(ListHead): head = ListHead while head not equals NULL: head = head.next tail = head while tail not equal to NULL: print tail.value tail = tail.prev return ListHead
単一リンクリストと二重リンクリストの違い
単一リンクリストと二重リンクリストの主な違いは、リンクの数です。
単一リンク リストのノードと二重リンク リストのノード構造の違いは次のとおりです。
| フィールド | 単方向リスト | 二重リンクリスト |
|---|---|---|
| Structure | 単方向リスト XNUMX つのデータ フィールドと次のノードへの XNUMX つのリンクがあります。 | 二重リンク リストには XNUMX つのデータ フィールドと XNUMX つのリンクがあります。 XNUMX つは前のノード用で、もう XNUMX つは次のノード用です。 |
| トラバーサル | 頭から尾までしか移動できません。 | 前方にも後方にも横断できます。 |
| メモリ | メモリの占有量が少なくなります。 | 単一リンクされたリストよりも多くのメモリを占有します。 |
| ユーザー補助 | 単一リンクリストは、次のノードへのリンクを XNUMX つだけ使用するため、効率が低くなります。 前のノードへのリンクはありません。 | 二重リンク リストは、単一リンク リストよりも効率的です。 |
二重リンクリスト 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);
}
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 = new 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 = new node();
head = listHead;
cout<<"Traversal from head:\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 = new node();
head = (*listHead);
while(head->next!=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;
return;
}
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 Aded 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 head: 10 9 11 5 20 6 7 Deleted Node 7 Traversal from head: 6 20 5 11 9 10 Traversal from head: 10 9 11 5 20 6
二重リンクリスト 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.insertFront(val)
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:
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 is not 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 is not 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.next is not None and temp.data is not searchItem:
temp = temp.next
if self.head is None or temp is None:
return
if self.head.data is 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))
return
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(1) の時間計算量がかかります。
- ノードの検索には、O(n) の時間計算量が必要です。これは、検索項目がリンク リスト内のどこにでも存在する可能性があるためです。ここで、「n」はリンク リスト内に存在するノードの合計です。
二重リンクリストの最悪のケースの時間計算量は、平均的なケースと同じになります。
二重リンクリストのメモリ複雑度
メモリの複雑度は O(n) です。ここで、n はノードの総数です。リンク リストを実装する際には、使用したメモリを解放する必要があります。そうしないと、リンク リストが大きくなるとメモリ リークが発生します。
まとめ
- リンク リストは、線形データ構造の一種であり、線形で表現されたデータの集合です。
- 二重リンク リストは、ノードが前と次の両方のノードとリンクを持つリンク リストの一種です。
- 二重リンク リストには、ノードの追加、ノードの削除、別のノードの後または前へのノードの挿入、リンク リストの先頭から末尾へのトラバースなどのすべての操作が含まれます。
- 二重リンク リストには XNUMX つのデータ フィールドと XNUMX つのリンクがあります。 XNUMX つは前のノード用で、もう XNUMX つは次のノード用です。
- 二重リンクリストの複雑さ 最良の場合、平均的な場合
- そして最悪の場合。
