与数组一样，链表是一种线性数据结构。与数组不同，链表元素不存储在连续的位置；元素使用指针链接。
为什么选择链表？
数组可用于存储类似类型的线性数据，但数组有以下限制。
1） 数组的大小是固定的：所以我们必须提前知道元素数量的上限。此外，一般而言，分配的内存与使用情况无关，等于上限。
2) 在元素数组中插入一个新元素是昂贵的，因为必须为新元素创建房间，并且必须移动现有元素才能创建房间。
例如，在一个系统中，如果我们在数组 id[] 中维护一个排序的 ID 列表。
id[] = [1000, 1010, 1050, 2000, 2040]。
而如果我们要插入一个新的ID 1005，那么为了保持排序顺序，我们必须将1000之后的所有元素（不包括1000）移动。
除非使用某些特殊技术，否则删除数组的代价也很高。例如，要删除 id[] 中的 1010，必须移动 1010 之后的所有内容。
优于数组
1) 动态大小
2) 易于插入/删除
缺点
1) 不允许随机访问。我们必须从第一个节点开始按顺序访问元素。所以我们不能用它的默认实现有效地对链表进行二分搜索。
2) 列表的每个元素都需要额外的指针存储空间。
3) 对缓存不友好。由于数组元素是连续的位置，因此存在引用的局部性，而在链表的情况下则不存在。
表示
链表由指向链表第一个节点的指针表示。第一个节点称为头部。如果链表为空，则头部的值为NULL。 列表中的每个节点至少由两部分组成：
- 数据
- 指向下一个节点的指针（或引用） 在 C 中，我们可以使用结构来表示一个节点。下面是一个带有整数数据的链表节点的例子。
在 Java 或 C# 中，LinkedList 可以表示为一个类，而一个 Node 可以表示为一个单独的类。LinkedList 类包含一个 Node 类类型的引用。
这是C++中一个简单链表
class Node { public: int data; Node* next; };
让我们创建一个具有 3 个节点的简单链表。
c++
复制代码
// 一个简单的引入链表的cpp程序 #include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; }; // 创建一个具有 3 个节点的简单链表的程序 int main() { Node* head = NULL; Node* second = NULL; Node* third = NULL; // 在堆中分配 3 个节点 head = new Node(); second = new Node(); third = new Node(); /* 三个块已被动态分配。 我们有指向这三个块的 指针作为head、second 和 third head second third | | | | | | +---+-----+ +----+----+ +----+----+ | # | # | | # | # | | # | # | +---+-----+ +----+----+ +----+----+ # 代表任何随机值。数据是随机的，因为我们还没有分配任何东西 */ head->data = 1; // 在第一个节点分配数据 head->next = second; // 链接第一个节点和第二个节点 /* 数据已分配给第一个块（由头指向的块）的数据部分。 第一个块的下一个指针指向第二个。所以它们都是链接的。 head second third | | | | | | +---+---+ +----+----+ +-----+----+ | 1 | o----->| # | # | | # | # | +---+---+ +----+----+ +-----+----+ */ // 将数据分配给第二个节点 second->data = 2; // 将第二个节点与第三个节点连接起来 second->next = third; /* 数据已分配给第二个块的数据部分（由秒指向的块）。 第二块的next指针指向第三块。 所以所有三个块都是链接的。 head second third | | | | | | +---+---+ +---+---+ +----+----+ | 1 | o----->| 2 | o-----> | # | # | +---+---+ +---+---+ +----+----+ */ third->data = 3; // 将数据分配给第三个节点 third->next = NULL; /* 数据已分配给第三个块（由第三个指向的块）的数据部分。 第三块的next指针为NULL，表示链表在此终止。 我们已经准备好了链表。 head | | +---+---+ +---+---+ +----+------+ | 1 | o----->| 2 | o-----> | 3 | NULL | +---+---+ +---+---+ +----+------+ 请注意，只有头部足以表示整个列表。 我们可以按照下一个指针遍历整个列表。*/ return 0; }
链表遍历
在前面的程序中，我们创建了一个简单的具有三个节点的链表。让我们遍历创建的列表并打印每个节点的数据。对于遍历，让我们编写一个通用函数 printList() 来打印任何给定的列表。
// 一个用于遍历链表的简单 C++ 程序 #include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; }; // 此函数打印从给定节点开始的链表内容 void printList(Node* n) { while (n != NULL) { cout << n->data << " "; n = n->next; } } // 驱动程序代码 int main() { Node* head = NULL; Node* second = NULL; Node* third = NULL; // 在堆中分配 3 个节点 head = new Node(); second = new Node(); third = new Node(); head->data = 1; // 在第一个节点分配数据 head->next = second; // 将第一个节点与第二个节点连接起来 second->data = 2; // 将数据分配给第二个节点 second->next = third; third->data = 3; // 将数据分配给第三个节点 third->next = NULL; printList(head); return 0; }
输出：
1 2 3
