鏈表是一種重要的數(shù)據(jù)結(jié)構(gòu)，在程序設(shè)計(jì)中占有很重要的地位。C語言和C＋＋語言中是用指針來實(shí)現(xiàn)鏈表結(jié)構(gòu)的，由于Java語言不提供指針，所以有人認(rèn)為在Java語言中不能實(shí)現(xiàn)鏈表，其實(shí)不然，Java語言比C和C＋＋更容易實(shí)現(xiàn)鏈表結(jié)構(gòu)。Java語言中的對象引用實(shí)際上是一個(gè)指針（本文中的指針均為概念上的意義，而非語言提供的數(shù)據(jù)類型），所以我們可以編寫這樣的類來實(shí)現(xiàn)鏈表中的結(jié)點(diǎn)。

　　class Node
　　{
　　Object data;
　　Node next;//指向下一個(gè)結(jié)點(diǎn)
　　}
　　將數(shù)據(jù)域定義成Object類是因?yàn)镺bject類是廣義超類，任何類對象都可以給其賦值，增加了代碼的通用性。為了使鏈表可以被訪問還需要定義一個(gè)表頭，表頭必須包含指向第一個(gè)結(jié)點(diǎn)的指針和指向當(dāng)前結(jié)點(diǎn)的指針。為了便于在鏈表尾部增加結(jié)點(diǎn)，還可以增加一指向鏈表尾部的指針，另外還可以用一個(gè)域來表示鏈表的大小，當(dāng)調(diào)用者想得到鏈表的大小時(shí)，不必遍歷整個(gè)鏈表。下圖是這種鏈表的示意圖：
鏈表的數(shù)據(jù)結(jié)構(gòu)
　　我們可以用類List來實(shí)現(xiàn)鏈表結(jié)構(gòu)，用變量Head、Tail、Length、Pointer來實(shí)現(xiàn)表頭。存儲當(dāng)前結(jié)點(diǎn)的指針時(shí)有一定的技巧，Pointer并非存儲指向當(dāng)前結(jié)點(diǎn)的指針，而是存儲指向它的前趨結(jié)點(diǎn)的指針,當(dāng)其值為null時(shí)表示當(dāng)前結(jié)點(diǎn)是第一個(gè)結(jié)點(diǎn)。那么為什么要這樣做呢？這是因?yàn)楫?dāng)刪除當(dāng)前結(jié)點(diǎn)后仍需保證剩下的結(jié)點(diǎn)構(gòu)成鏈表，如果Pointer指向當(dāng)前結(jié)點(diǎn)，則會(huì)給操作帶來很大困難。那么如何得到當(dāng)前結(jié)點(diǎn)呢，我們定義了一個(gè)方法cursor(),返回值是指向當(dāng)前結(jié)點(diǎn)的指針。類List還定義了一些方法來實(shí)現(xiàn)對鏈表的基本操作，通過運(yùn)用這些基本操作我們可以對鏈表進(jìn)行各種操作。例如reset()方法使第一個(gè)結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)。insert(Object d)方法在當(dāng)前結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)，并使其成為當(dāng)前結(jié)點(diǎn)。remove()方法刪除當(dāng)前結(jié)點(diǎn)同時(shí)返回其內(nèi)容，并使其后繼結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)，如果刪除的是最后一個(gè)結(jié)點(diǎn)，則第一個(gè)結(jié)點(diǎn)變?yōu)楫?dāng)前結(jié)點(diǎn)。
　　鏈表類List的源代碼如下：
　　import java.io.＊;
　　public class List  
　　{
　　/＊用變量來實(shí)現(xiàn)表頭＊/
　　private Node Head=null;
　　private Node Tail=null;
　　private Node Pointer=null;
　　private int Length=0;
public void deleteAll()
　　/＊清空整個(gè)鏈表＊/
　　{
　　Head=null;
　　Tail=null;
　　Pointer=null;
　　Length=0;
　　}
　　public void reset()
　　/＊鏈表復(fù)位，使第一個(gè)結(jié)點(diǎn)
成為當(dāng)前結(jié)點(diǎn)＊/
　　{
　　Pointer=null;
　　}
　　public boolean isEmpty()
　　/＊判斷鏈表是否為空＊/
　　{
　　return(Length==0);
　　}
　　public boolean isEnd()
　　/＊判斷當(dāng)前結(jié)點(diǎn)是否
為最后一個(gè)結(jié)點(diǎn)＊/
　　{
　　if(Length==0)
　　throw new java.lang.NullPointerException();
　　else if(Length==1)
　　return true;
　　else
　　return(cursor()==Tail);
　　}
　　public Object nextNode()
　　/＊返回當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的值，
并使其成為當(dāng)前結(jié)點(diǎn)＊/
　　{
　　if(Length==1)
　　throw new java.util.NoSuchElementException();
　　else if(Length==0)
　　throw new java.lang.NullPointerException();
　　else
　　{
　　Node temp=cursor();
　　Pointer=temp;
　　if(temp!=Tail)
　　return(temp.next.data);
　　else
　　throw new java.util.NoSuchElementException();
　　}
　　}
　　public Object currentNode()
　　/＊返回當(dāng)前結(jié)點(diǎn)的值＊/
　　{
　　Node temp=cursor();
　　return temp.data;
　　}
　　
　　public void insert(Object d)
　　/＊在當(dāng)前結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)，
并使其成為當(dāng)前結(jié)點(diǎn)＊/
　　{
　　Node e=new Node(d);
　　if(Length==0)
　　{
　　Tail=e;
　　Head=e;
　　}
　　else
　　{
　　Node temp=cursor();
　　e.next=temp;
　　if(Pointer==null)
　　Head=e;
　　else
　　Pointer.next=e;
　　}
　　Length＋＋;
　　}
　　public int size()
　　/＊返回鏈表的大�。�/
　　{
　　return (Length);
　　}
　　public Object remove()
　　/＊將當(dāng)前結(jié)點(diǎn)移出鏈表，下一個(gè)結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)，如果移出的結(jié)點(diǎn)是最后一個(gè)結(jié)點(diǎn)，則第一個(gè)結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)＊/
　　{
　　Object temp;
　　if(Length==0)
　　throw new java.util.NoSuchElementException();
　　else if(Length==1)
　　{
　　temp=Head.data;
　　deleteAll();
　　}
　　else
　　{
　　Node cur=cursor();
　　temp=cur.data;
　　if(cur==Head)
　　Head=cur.next;
　　else if(cur==Tail)
　　{
　　Pointer.next=null;
　　Tail=Pointer;
　　reset();
　　}
　　else
　　Pointer.next=cur.next;
　　Length－－;
　　}
　　return temp;
　　}
　　private Node cursor()
　　/＊返回當(dāng)前結(jié)點(diǎn)的指針＊/
　　{
　　if(Head==null)
　　throw new java.lang.NullPointerException();
　　else if(Pointer==null)
　　return Head;
　　else
　　return Pointer.next;
　　}
　　public static void main(String[] args)
　　/＊鏈表的簡單應(yīng)用舉例＊/
　　{
　　List a=new List ();
　　for(int i=1;i<=10;i＋＋)
　　a.insert(new Integer(i));
　　System.out.println(a.currentNode());
　　while(!a.isEnd())
　　System.out.println(a.nextNode());
　　a.reset();
　　while(!a.isEnd())
　　{
　　a.remove();
　　}
　　a.remove();
　　a.reset();
　　if(a.isEmpty())
　　System.out.println("There is no Node in List  \n");
　　System.in.println("You can press return to quit\n");
　　try
　　{
　　System.in.read();
//確保用戶看清程序運(yùn)行結(jié)果
　　}
　　catch(IOException e)
　　{}
　　}
　　}
　　class Node
　　/＊構(gòu)成鏈表的結(jié)點(diǎn)定義＊/
　　{
　　Object data;
　　Node next;
　　Node(Object d)
　　{
　　data=d;
　　next=null;
　　}
　　}
　　讀者還可以根據(jù)實(shí)際需要定義新的方法來對鏈表進(jìn)行操作。雙向鏈表可以用類似的方法實(shí)現(xiàn)只是結(jié)點(diǎn)的類增加了一個(gè)指向前趨結(jié)點(diǎn)的指針。
　　可以用這樣的代碼來實(shí)現(xiàn)：
　　class Node
　　{
　　Object data;
　　Node next;
　　Node previous;
　　Node(Object d)
　　{
　　data=d;
　　next=null;
　　previous=null;
　　}
　　}
　　當(dāng)然，雙向鏈表基本操作的實(shí)現(xiàn)略有不同。鏈表和雙向鏈表的實(shí)現(xiàn)方法，也可以用在堆棧和隊(duì)列的實(shí)現(xiàn)中，這里就不再多寫了，有興趣的讀者可以將List類的代碼稍加改動(dòng)即可。