链表是一种递归的数据结构，它或者为（null），或者是指向一个结点（node）的引用，该结点含有一个泛型的元素和一个指向另一条链表的引用。

用代码定义

private class Node {
    Item item;        
    Node next;
}

一个 Node 对象含有两个实例变量，类型分别为 Item（参数类型）和 Node。如上将 Node 类标记为 private，是因为链表一般是嵌套类，配合栈、队列等来使用的；Item 是一个占位符，表示我们希望用链表处理的任意数据类型（这里用泛型来表示任意类型）。

构造链表

若要构造一条链表，只需要一个 Node 类型的变量就能表示一条链条，只要保证它的值是 null 或者指向另一个 Node 对象且该对象的 next 域指向了另一条链表即可。

代码

Node first = new Node();
Node second = new Node();
Node third = new Node();

first.next = second;
second.next = third;

插入操作

表头插入

例如，要在首结点为 first 的链表开头插入字符串 not 的新结点。做法如下：

我们先将 first 保存在 oldfirst 中
然后将一个新结点赋予 first，并将它的 item 域设为 not，next 域设为 oldfirst

代码

Node oldfirst = first;
first = new Node();
first.item = "not";
first.next = oldfirst;

表尾插入

例如，要在尾结点为 third 的链表尾部插入字符串 not 的新结点。做法如下：

我们先将 third 保存在 oldthird 中
然后将一个新结点赋予 third，并将它的 item 域设为 not
将 oldthird 的 next 域设为 third

代码

Node oldthird = third;
third = new Node();
third.item = "not";
oldthird.next = third;

表中间插入

例如，要在结点位置 3 插入一个字符串 new 的新结点，这里 first 位置为 1，second 位置为 2，third 位置为 3，插入新结点后，third 位置变为 4。做法如下：

定义新结点 newNode，新结点位置的前一个结点叫做前驱结点 pre，后一个结点叫后驱结点 pre.next
这里关键在于找位置 3 的前驱结点，前驱结点的位置是 2
将找到的前驱结点 pre 指向 newNode，newNode 指向后驱结点 pre.next，便可实现插入。

代码

Node find(int position, Node headNode){
    Node currentNode = headNode;
    int i = 1;
    while(currentNode!=null && i<position){
        currentNode = currentNode.next;
        i++;
    }
    if(i==position) return currentNode;
    else return null;
}

Node pre = find(2, first);  
Node newNode = new Node();
newNode.item = 'new';
newNode.next = pre.next;  
pre.next = newNode;

删除操作

表头结点删除

只需要将 first 指向 first.next 即可。因为一旦改变了 first 的值，就再也无法访问它曾经指向的结点了。

代码

first = first.next;

表尾结点删除

只需将链表尾结点 third 的前一个结点 second 中的 next 值改为 null 即可。这里具体代码就不实现了，思路就是遍历整条链表并找出指向表尾的结点。

表中间结点删除

例如，我们要删除位置 2 的结点 second。只需找到被删除结点的前驱结点（位置为 1）pre，将其 next 指向被删结点的 next 即可。

代码

Node pre = find(1, first);
Node deleteNode = pre.next;
pre.next = deleteNode.next;

链表遍历

链表遍历非常简单，如下代码所示，其中 first 指向链表的首结点：

for(Node x = first; x != null; x = x.next){
    // 处理 x.item
}

链表