实现双重链接列表的C ++程序

双链表是一种数据结构，由使用自引用结构创建的节点组成。这些节点中的每一个都包含三个部分，即数据和对下一个列表节点的引用以及对上一个列表节点的引用。

访问整个链接列表仅需要引用第一个列表节点。这被称为头部。列表中的最后一个节点没有指向任何内容，因此它在该部分中存储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

在以上程序中，结构Node形成了双向链表节点。它包含数据和指向下一个和上一个链接列表节点的指针。给出如下。

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

该函数insert()将数据插入到双向链表的开头。它创建一个新节点，并将数字插入到新节点的数据字段中。然后，在newnode中的prev指针指向NULL，因为它是在开头输入的，而下一个指针则指向头部。如果head不为NULL，则head的prev指针指向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()显示整个双向链表。第一点指向头。然后将其连续转发到下一个节点，直到打印出节点的所有数据值为止。这在下面给出。

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;
}