链表第一课

链表是一种基础的数据结构，它表示一列元素。

链表由节点（Node）组成，一个节点包含两个变量，一个变量存储我们需要保存的数据，另一个变量指向下一个节点，如下图所示：

在程序中表示如下：

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)中，栈使用后进先出的策略，在表头添加节点，在表头删除节点；队列使用先进先出的策略，在表头添加节点，在表尾删除节点。