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的源代碼如下:
package?cn.javatx;?import?java.io.IOException;/***?@author?ljfan
*?
*/
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);
}public?Object?remove()?{
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()?{
if?(Head?==?null)
throw?new?java.lang.NullPointerException();
else?if?(Pointer?==?null)
return?Head;
else
return?Pointer.next;
}public?static?void?main(String[]?args)?{
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.out.println("You?can?press?return?to?quitn");
try?{
System.in.read()();
}?catch?(IOException?e)?{
}
}
}class?Node?{
Object?data;
Node?next;Node(Object?d)?{
data?=?d;
next?=?null;
}
}
當然,雙向鏈表基本操作的實現略有不同。鏈表和雙向鏈表的實現方法,也可以用在堆棧和隊列的現實中。