JAVA中怎么實現鏈表和雙向鏈表

這篇文章給大家介紹JAVA中怎么實現鏈表和雙向鏈表，內容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

JAVA基礎:語言中鏈表和雙向鏈表的實現(轉)[@more@]鏈表是一種重要的數據結構，在程序設計中占有很重要的地位。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

{

/* 用變量來實現表頭 */

private Node Head=null;

private Node Tail=null;

private Node Pointer=null;

private int Length = 0;

public void deleteAll()

　

/* 清空整個鏈表 */

{

Head = null;

Tail = null;

Pointer = null;

Length = 0;

}

public void reset()

　

/* 鏈表復位，使第一個結點成為當前結點 */

{

Pointer = null;

}

public boolean isEmpty( )

　

/* 判斷鏈表是否為空 */

{

return( Length == 0 );

}

public boolean isEnd()

　

/* 判斷當前結點是否為最后一個結點 */

{

if ( Length == 0 )

throw new java.lang.NullPointerException();

else if ( Length == 1 )

return true;

else

return( cursor() == Tail );

}

public Object nextNode()

/* 返回當前結點的下一個結點的值，并使其成為當前結點 */

{

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()

/* 返回當前結點的值 */

{

Node temp = cursor();

return temp.data;

}

　

public void insert( Object d )

/* 在當前結點前插入一個結點，并使其成為當前結點 */

{

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 );

}

關于JAVA中怎么實現鏈表和雙向鏈表就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。