C++ 程序实现双向链表
c++programmingserver side programming
双向链表是一种数据结构，由使用自引用结构创建的节点组成。每个节点包含三个部分，即数据、对下一个列表节点的引用以及对上一个列表节点的引用。
只需引用第一个列表节点即可访问整个链表。这被称为头部。列表中的最后一个节点不指向任何内容，因此它在该部分存储 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() 将数据插入双向链表的开头。它创建一个新节点，并将数字插入新节点的数据字段中。然后，新节点中的 prev 指针指向 NULL，因为它是在开头输入的，而下一个指针指向头部。如果头部不为 NULL，则头部的 prev 指针指向新节点。最后，头部是新节点，即链表从那里开始。如下所示。
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 指向 head。然后不断转发到下一个节点，直到打印完所有节点的数据值。如下所示。
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;
}
