當前位置:編程學習大全網 - 源碼下載 - Java語言沒有指針,怎樣實現鏈表?

Java語言沒有指針,怎樣實現鏈表?

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;

}

}

當然,雙向鏈表基本操作的實現略有不同。鏈表和雙向鏈表的實現方法,也可以用在堆棧和隊列的現實中。

  • 上一篇:茶樓廣告標語
  • 下一篇:希望ol私服源碼
  • copyright 2024編程學習大全網