链表是一种重要的数据结构，在程序设计中占有很重要的地位。C 语言和 C＋＋语言中是

用指针来实现链表结构的，由于 Java 语言不提供指针，所以有人认为在 Java 语言中不

能实现链表，其实不然，Java 语言比 C 和 C＋＋更容易实现链表结构。Java 语言中的对

象引用实际上是一个指针（本文中的指针均为概念上的意义，而非语言提供的数据类

 

型），所以我们可以编写这样的类来实现链表中的结点。

　　class Node

　　{

　　Object data;

　　Node next;//指向下一个结点

　　}

　　将数据域定义成 Object 类是因为 Object 类是广义超类，任何类对象都可以给其赋

值，增加了代码的通用性。为了使链表可以被访问还需要定义一个表头，表头必须包含指

向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点，还可以增加

一指向链表尾部的指针，另外还可以用一个域来表示链表的大小，当调用者想得到链表

的大小时，不必遍历整个链表。下图是这种链表的示意图：

　　链表的数据结构

　　我们可以用类 List 来实现链表结构，用变量 Head、Tail、Length、Pointer 来实现表

头。存储当前结点的指针时有一定的技巧，Pointer 并非存储指向当前结点的指针，而是

存储指向它的前趋结点的指针,当其值为 null 时表示当前结点是第一个结点。那么为什么

要这样做呢？这是因为当删除当前结点后仍需保证剩下的结点构成链表，如果 Pointer

指向当前结点，则会给操作带来很大困难。那么如何得到当前结点呢，我们定义了一个方

法 cursor(),返回值是指向当前结点的指针。类 List 还定义了一些方法来实现对链表的基

本操作，通过运用这些基本操作我们可以对链表进行各种操作。例如 reset()方法使第一

个结点成为当前结点。insert(Object d)方法在当前结点前插入一个结点，并使其成为当

前结点。remove()方法删除当前结点同时返回其内容，并使其后继结点成为当前结点，

如果删除的是最后一个结点，则第一个结点变为当前结点。

　　链表类 List 的源代码如下：

　　import java.io.*;

　　public class List

　　{