链表是一种基础的数据结构，它表示一列元素。
链表由节点（Node）组成，一个节点包含两个变量，一个变量存储我们需要保存的数据（图中的item），另一个变量指向下一个节点（图中的next），如下图所示：
节点
在程序中表示如下：
private class Node
{
Item item; // 保存数据
Node next; // 指向下一个节点
}
若干个这样的节点一个一个连起来，就可以组成一个链表。此外，我们还需要两个变量，分别指向链表的头节点和尾节点：本文使用first变量指向头节点，last变量指向尾节点。
下面介绍四个链表的操作：
- 创建第一个节点。
- 在表头添加节点。
- 在表尾添加节点。
- 在表头删除节点。
创建第一个节点
创建第一个节点非常容易，只需要新建一个节点，并将变量first和last都指向这个节点即可：
创建第一个节点
这个节点的next变量为null（空），意味着它不指向其他节点，也就是说它是最后一个节点。它还是第一个节点，所以last和first变量都指向它。
这个节点的item变量被赋值为boy，这是我们希望存储的数据。
在表头添加节点
在表头添加节点需要使用一个临时变量，这里把这个临时变量叫做oldfirst，它指向添加新节点之前的头节点。
在表头添加节点的过程如下：
- 将oldfirst变量指向头节点；
- 新建一个节点并将first变量指向它；
- 将新节点的next变量指向oldfirst变量所指的节点。
这样，新建的节点成了整个链表的头节点，而原先的头节点成了链表的第二个节点。如下图：
在表头添加节点
至此，我们得到了一条拥有两个节点的链表：
拥有两个节点的链表
在表尾添加节点
在表尾添加节点和在表头添加节点非常相似，过程如下：
- 将oldlast变量指向尾节点；
- 新建一个节点并将last变量指向他；
- 将oldlast变量所指节点的next变量指向新节点。
在表尾添加节点
这样，新添加的节点变成了尾节点，原先的尾节点变成了倒数第二个节点。
至此，我们拥有了一条由三个节点构成的链表：
拥有三个节点的链表
在表头删除节点
在表头删除节点很简单，只需要将first变量指向第二个节点（头节点next变量所指的节点），然后让原先的头节点随风而去即可：
在表头删除节点
至此，链表的四种基本操作就介绍完了。
数组也可以用于保存一列元素，它们之间的主要区别有：
| 功能 | 数组 | 链表 |
|---|---|---|
| 随机访问和修改任意元素 | 可以，可以通过下标访问 | 不可以，只能从头节点一个一个往后寻找 |
| 不移动其他元素在内存中的位置的情况下插入元素 | 不可以 | 可以 |
| 事先估计元素容量 | 需要，因为数组元素个数一旦确定，便无法再更改 | 不需要 |
| 所需空间与元素容量成正比 | 一般不是，需要为添加和插入元素预留空间 | 是 |
链表一个典型的应用是在栈（LIFO）和队列（FIFO)中，栈使用后进先出的策略，在表头添加节点，在表头删除节点；队列使用先进先出的策略，在表头添加节点，在表尾删除节点。
网友评论