二重リンクリストを実装するC++プログラム

二重リンクリストは、自己参照構造を使用して作成されたノードで構成されるデータ構造の一種です。これらの各ノードには、データと次のリストノードへの参照、および前のリストノードへの参照の3つの部分が含まれています。

リンクリスト全体にアクセスするには、最初のリストノードへの参照のみが必要です。これは頭​​として知られています。リストの最後のノードは何も指していないため、その部分にNULLが格納されます。また、各ノードが前のノードと次のノードを指しているため、二重にリンクされたリストを両方向にトラバースできます。

二重リンクリストを実装するプログラムは次のとおりです。

例

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node *prev;
   struct Node *next;
};
struct Node* head = NULL;
void insert(int newdata) {
   struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
   newnode->data = newdata;
   newnode->prev = NULL;
   newnode->next = head;
   if(head != NULL)
   head->prev = newnode ;
   head = newnode;
}
void display() {
   struct Node* ptr;
   ptr = head;
   while(ptr != NULL) {
      cout<< ptr->data <<" ";
      ptr = ptr->next;
   }
}
int main() {
   insert(3);
   insert(1);
   insert(7);
   insert(2);
   insert(9);
   cout<<"The doubly linked list is: ";
   display();
   return 0;
}

出力

The doubly linked list is: 9 2 7 1 3

上記のプログラムでは、構造体ノードが二重リンクリストノードを形成しています。これには、データと、次および前のリンクリストノードへのポインタが含まれています。これは次のように与えられます。

struct Node {
   int data;
   struct Node *prev;
   struct Node *next;
};

関数insert（）は、二重リンクリストの先頭にデータを挿入します。 newnodeを作成し、newnodeのデータフィールドに番号を挿入します。次に、newnodeのprevポインターは、最初に入力されたときにNULLを指し、次のポインターはヘッドを指します。ヘッドがNULLでない場合、ヘッドのprevポインタはnewnodeを指します。最後に、ヘッドはnewnodeです。つまり、リンクリストはそこから始まります。これを以下に示します。

void insert(int newdata) {
   struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
   newnode->data = newdata;
   newnode->prev = NULL;
   newnode->next = head;
   if(head != NULL)
   head->prev = newnode ;
   head = newnode;
}

関数display（）は、二重リンクリスト全体を表示します。最初のptrは頭を指します。次に、ノードのすべてのデータ値が出力されるまで、次のノードに継続的に転送されます。これを以下に示します。

void display() {
   struct Node* ptr;
   ptr = head;
   while(ptr != NULL) {
      cout<< ptr->data <<" ";
      ptr = ptr->next;
   }
}

関数main（）では、insert（）を呼び出すことにより、最初にさまざまな値が二重リンクリストに挿入されます。次に、二重リンクリストが表示されます。これを以下に示します。

int main() {
   insert(3);
   insert(1);
   insert(7);
   insert(2);
   insert(9);
   cout<<"The doubly linked list is: ";
   display();
   return 0;
}