9.1定义

链表是由一系列连接在一起的结点构成，其中的每个结点都是一个数据结构。

9.2特点

链表的结点通常是动态分配、使用和删除的，允许链表在程序运行时增大或缩小。

• 如果需要将新信息添加到链表中，则程序只需分配另一个结点并将其插入到系列中。
• 如果需要从链表中删除特定的信息块，则程序将删除包含该信息的结点。
• 当一个结点插入链表或从链表中删除结点时，其他结点都不必移动。

9.3链表的结构

链表中的每个结点都包含一个或多个保存数据的成员。例如，存储在结点中的数据可以是库存记录；或者它可以是由客户的姓名、地址和电话号码等组成的客户信息记录。

除了数据之外，每个结点还包含一个后继指针指向链表中的下一个结点。

图 1 单个结点的组成

非空链表的第一个结点称为链表的头。要访问链表中的结点，需要有一个指向链表头的指针。从链表头开始，可以按照存储在每个结点中的后继指针访问链表中的其余结点。最后一个结点中的后继指针被设置为 nullptr 以指示链表的结束。

因为指向链表头的指针用于定位链表的头部，所以也可以认为它代表了链表头。同样的指针也可以用来定位整个链表，从头开始，后面跟着后续指针，所以也可以很自然地把它看作是代表了整个链表。

图 2 给出了一个由 3 个结点组成的链表，其中显示了指向头部的指针，链表的 3 个结点以及表示链表末尾的 nullptr 指针。

图 2 链表结构图解

注意，图 2 中绘制的链表结点彼此非常接近，排列整齐。实际上，链表结点可能散布在内存的各个部分。

9.4创建链表

• 尾插法 ```cpp struct point { int num; point next; }; int main() { int x; point head, rear, p; head = rear = new point; cout << “Please input integers to build the link(or to end)” << endl;

  while (true) {

    cin >> x;
    if (x == 0) break;
    p = new point;
    p->num = x;
    rear->next = p;
    rear = p;

  }

  rear->next = NULL;

  //读出链表的内容 cout << “链表的内容为：” << endl; p = head->next; while (p != NULL) {

    cout << p->num << '\t';
    p = p->next;

  } cout << endl;

return 0;

}

```