C++ 实现单链表

单链表是一种由使用自引用结构创建的节点组成的数据结构。这些节点中的每一个包含两个部分，即数据和下一个链表节点的引用。仅需要引用到第一个链表节点就可以访问整个链表。这被称为头部。列表中的最后一个节点指向空，因此在该部分存储NULL。

实现单链表的程序如下所示。

示例

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node *next;
};
struct Node* head = NULL;
void insert(int new_data) {
   struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
   new_node->data = new_data;
   new_node->next = head;
   head = new_node;
}
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 linked list is: ";
   display();
   return 0;
}

输出

The linked list is: 9 2 7 1 3

在上面的程序中，结构Node形成了链表节点。它包含了数据和指向下一个链表节点的指针。具体如下所示。

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

插入函数 insert() 将数据插入链表的开头。它创建一个 new_node 并将数字插入到 new_node 的数据字段中。然后 new_node 指向头部。最后，头部是 new_node ，也就是说链表从此开始。如下所示：

void insert(int new_data) {
   struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
   new_node->data = new_data;
   new_node->next = head;
   head = new_node;
}

该函数 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 linked list is: ";
   display();
   return 0;
}