JAVA語言中鏈表和雙向鏈表的實現

　　鏈表是一種重要的數據結構在程序設計中占有很重要的地位C語言和C++語言中是用指針來實現鏈表結構的由於JAVA語言不提供指針所以有人認為在JAVA語言中不能實現鏈表其實不然JAVA語言比C和C++更容易實現鏈表結構JAVA語言中的對象引用實際上是一個指針（本文中的指針均為概念上的意義而非語言提供的數據類型）所以我們可以編寫這樣的類來實現鏈表中的結點
　　
　　class Node
　　
　　{
　　
　　Object data;
　　
　　Node next; // 指向下一個結點
　　
　　}
　　
　　　　將數據域定義成Object類是因為Object類是廣義超類（所有類的祖先）任何類對象都可以給其賦值增加了代碼的通用性為了使鏈表可以被訪問還需要定義一個表頭表頭必須包含指向第一個結點的指針和指向當前結點的指針為了便於在鏈表尾部增加結點還可以增加一指向鏈表尾部的指針另外還可以用一個域來表示鏈表的大小當調用者想得到鏈表的大小時不必遍歷整個鏈表下圖是這種鏈表的示意圖
　　
　　　
　　
　　圖一 鏈表的數據結構
　　
　　　
　　
　　我們可以用類List來實現鏈表結構用變量HeadTailLengthPointer來實現表頭存儲當前結點的指針時有一定的技巧Pointer並非存儲指向當前結點的指針而是存儲指向它的前趨結點的指針當其值為null時表示當前結點是第一個結點那麼我們為什麼要這樣做呢？這是因為當我們刪除當前結點後仍需保證剩下的結點構成鏈表如果Pointer指向當前結點則會給操作帶來很大困難那麼如何得到當前結點呢我們定義了一個方法cursor()返回值是指向當前結點的指針類List還定義了一些方法來實現對鏈表的基本操作通過運用這些基本操作我們可以對鏈表進行各種操作例如reset()方法使第一個結點成為當前結點insert( Object d )方法在當前結點前插入一個結點並使其成為當前結點remove()方法刪除當前結點同時返回其內容並使其後繼結點成為當前結點如果刪除的是最後一個結點則第一個結點變為當前結點
　　
　　鏈表類List的源代碼如下
　　
　　import javaio*;
　　
　　public class List
　　
　　{
　　
　　/* 用變量來實現表頭 */
　　
　　private Node Head=null;
　　
　　private Node Tail=null;
　　
　　private Node Pointer=null;
　　
　　private int Length = ;
　　
　　public void deleteAll()
　　
　　　
　　
　　/* 清空整個鏈表 */
　　
　　{
　　
　　Head = null;
　　
　　Tail = null;
　　
　　Pointer = null;
　　
　　Length = ;
　　
　　}
　　
　　public void reset()
　　
　　　
　　
　　/* 鏈表復位使第一個結點成為當前結點 */
　　
　　{
　　
　　Pointer = null;
　　
　　}
　　
　　public boolean isEmpty( )
　　
　　　
　　
　　/* 判斷鏈表是否為空 */
　　
　　{
　　
　　return( Length == );
　　
　　}
　　
　　public boolean isEnd()
　　
　　　
　　
　　/* 判斷當前結點是否為最後一個結點 */
　　
　　{
　　
　　if ( Length == )
　　
　　throw new javalangNullPointerException();
　　
　　else if ( Length == )
　　
　　return true;
　　
　　else
　　
　　return( cursor() == Tail );
　　
　　}
　　
　　public Object nextNode()
　　
　　/* 返回當前結點的下一個結點的值並使其成為當前結點 */
　　
　　{
　　
　　if ( Length == )
　　
　　throw new javautilNoSuchElementException();
　　
　　else if ( Length == )
　　
　　throw new javalangNullPointerException();
　　
　　else
　　
　　{
　　
　　Node temp = cursor();
　　
　　Pointer = temp;
　　
　　if ( temp != Tail )
　　
　　return( tempnextdata );
　　
　　else
　　
　　throw new javautilNoSuchElementException();
　　
　　}
　　
　　}
　　
　　public Object currentNode()
　　
　　/* 返回當前結點的值 */
　　
　　{
　　
　　Node temp = cursor();
　　
　　return tempdata;
　　
　　}
　　
　　　
　　
　　public void insert( Object d )
　　
　　/* 在當前結點前插入一個結點並使其成為當前結點 */
　　
　　{
　　
　　Node e = new Node( d );
　　
　　if ( Length == )
　　
　　{
　　
　　Tail = e;
　　
　　Head = e;
　　
　　}
　　
　　else
　　
　　{
　　
　　Node temp = cursor();
　　
　　enext = temp;
　　
　　if ( Pointer == null )
　　
　　Head = e;
　　
　　else
　　
　　Pointernext = e;
　　
　　}
　　
　　Length++;
　　
　　}
　　
　　public int size()
　　
　　/* 返回鏈表的大小 */
　　
　　{
　　
　　return ( Length );
　　
　　}
　　
　　public Object remove()
　　
　　/* 將當前結點移出鏈表下一個結點成為當前結點 如果移出
　　
　　的結點是最後一個結點則第一個結點成為當前結點 */
　　
　　{
　　
　　Object temp ;
　　
　　if ( Length == )
　　
　　throw new javautilNoSuchElementException();
　　
　　else if ( Length == )
　　
　　{
　　
　　temp = Headdata;
　　
　　deleteAll();
　　
　　}
　　
　　else
　　
　　{
　　
　　Node cur = cursor();
　　
　　temp = curdata;
　　
　　if ( cur == Head )
　　
　　Head = curnext;
　　
　　else if ( cur == Tail )
　　
　　{
　　
　　Pointernext = null;
　　
　　Tail = Pointer;
　　
　　reset();
　　
　　}
　　
　　else
　　
　　Pointernext = curnext;
　　
　　Length;
　　
　　}
　　
　　return temp;
　　
　　}
　　
　　private Node cursor()
　　
　　/* 返回當前結點的指針 */
　　
　　{
　　
　　if ( Head == null )
　　
　　throw new javalangNullPointerException();
　　
　　else if ( Pointer == null )
　　
　　return Head;
　　
　　else
　　
　　return Pointernext;
　　
　　}
　　
　　　
　　
　　public static void main( String[] args )
　　
　　/* 鏈表的簡單應用舉例 */
　　
　　{
　　
　　List a = new List();
　　
　　for ( int i = ; 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(); // 確保用戶看清程序運行結果
　　
　　}
　　
　　catch( IOException e )
　　
　　{}
　　
　　}
　　
　　}
　　
　　class Node
　　
　　/* 構成鏈表的結點定義 */
　　
　　{
　　
　　Object data;
　　
　　Node next;
　　
　　Node( Object d )
　　
　　{
　　
　　data = d;
　　
　　next = null;
　　
　　}
　　
　　}
　　
　　讀者還可以根據實際需要定義新的方法來對鏈表進行操作。tw.wiNgwIT.cOm雙向鏈表可以用類似的方法實現只是結點的類增加了一個指向前趨結點的指針。
　　
　　我們可以用這樣的代碼來實現：
　　
　　class Node
　　
　　{
　　
　　Object data;
　　
　　Node next;
　　
　　Node previous;
　　
　　　
　　
　　Node ( Object d )
　　
　　{
　　
　　data = d;
　　
　　next = null;
　　
　　previous = null;
　　
　　}
　　
　　}
　　
　　當然雙向鏈表基本操作的實現略有不同，這裡就不再詳述了。鏈表和雙向鏈表的實現方法，也可以用在堆棧和隊列的實現中，這裡就不再多寫了，有興趣的讀者可以將List類的代碼稍加改動即可。
　　

From:http://tw.wingwit.com/Article/program/Java/Javascript/201311/25266.html