程序员必知的算法和数据结构：用这种方法理解链表，更易懂

一个单链表包括一系列节点(Nodes), 每个节点包括对后继节点的引用。通常，链表最后一个节点是null，这样表明链表终止了。

对于面向对象的编程，实现链表不是困难的。我们定义一个节点类，本质上它具备递归的特性。

2 链表中的节点定义

一个节点类的定义：

1class Node { 
2   String item; 
3   Node next; 
4} 

可以看到，一个Node对象包括两个实例变量，此处默认存储类型为String，和对下一个节点的引用。

3 串起节点

首先给出一个栈结构的示意图：每个节点的元素存储值为：to be or not to be.

那么以上节点是怎么被串起来的呢？我们首先构造出第一个节点 first, 如下所示：

接下来创建second, 并且first节点指向second

同理，直到形成如下的链表图：

4 链表的基本操作

4.1 插入一个节点到链表中

假定你想要插入一个新的节点到一个链表中，做插入最简单的地方就是在链表的刚开始第一个节点处。例如插入not字符串节点到以first节点为开始的链表中，这个正也是栈结构借助链表实现的track之一。

首先我们标记下即将成为老链表头的指针到oldFirst.

然后，new 一个即将成为新头的节点

给这个新节点的两个属性赋值，OK

4.2 从链表中删除一个节点

做删除最简洁地位置也是在刚开始节点，这个比较直观，直接将first指向first.next即可，不做任何物理上的删除。

4.3 对链表遍历

代码如下所示，遍历时在不断更新x指针。

1for (Node x = first; x != null; x = x.next) 
2    StdOut.println(x.item);

列出详细的过程示意图：