class Node {
創(chuàng)新互聯(lián)從2013年成立，先為榕江等服務(wù)建站，榕江等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為榕江企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。
Object data;
Node next;//申明類Node類的對象叫Next
public Node(Object data) { //類Node的構(gòu)造函數(shù)
setData(data);
}
public void setData(Object data) {
this.data = data;
}
public Object getData() {
return data;
}
}
class Link {
Node head;//申明一個Node類的一個對象 head
int size = 0;
public void add(Object data) {
Node n = new Node(data); //調(diào)用Node類的構(gòu)造函數(shù)
鏈表是一種重要的數(shù)據(jù)結(jié)構(gòu)，在程序設(shè)計中占有很重要的地位。C語言和C＋＋語
言中是用指針來實現(xiàn)鏈表結(jié)構(gòu)的，由于Java語言不提供指針，所以有人認(rèn)為在
Java語言中不能實現(xiàn)鏈表，其實不然，Java語言比C和C＋＋更容易實現(xiàn)鏈表結(jié)構(gòu)
。Java語言中的對象引用實際上是一個指針（本文中的指針均為概念上的意義，
而非語言提供的數(shù)據(jù)類型），所以我們可以編寫這樣的類來實現(xiàn)鏈表中的結(jié)點。
class Node
{
Object data;
Node next;//指向下一個結(jié)點
}
將數(shù)據(jù)域定義成Object類是因為Object類是廣義超類，任何類對象都可以給
其賦值，增加了代碼的通用性。為了使鏈穗派表可以被訪問還需要定義一個表孫備頭，表
頭必須包含指向第一個結(jié)點的指針和指向當(dāng)前結(jié)點的指針。為了便于在鏈表尾部
增加結(jié)點，還可以增加一指向鏈表尾部的指針，另外還可以用一個域來表示鏈表
的大小，當(dāng)調(diào)用者想得到鏈表的大小時，不必遍歷整個鏈表。下圖是這種鏈表的
示意圖：
鏈表的數(shù)據(jù)結(jié)構(gòu)
我們可以用類List來實現(xiàn)鏈表結(jié)構(gòu)，用變量Head、Tail、Length、Pointer
來實現(xiàn)表頭。存儲當(dāng)前結(jié)點的指針時有一定的技巧， Pointer并非存儲指向當(dāng)前
結(jié)點的指針，而是存儲指向它的前趨猜凱賀結(jié)點的指針,當(dāng)其值為null時表示當(dāng)前結(jié)點是
第一個結(jié)點。那么為什么要這樣做呢？這是因為當(dāng)刪除當(dāng)前結(jié)點后仍需保證剩下
的結(jié)點構(gòu)成鏈表，如果Pointer指向當(dāng)前結(jié)點，則會給操作帶來很大困難。那么如
何得到當(dāng)前結(jié)點呢，我們定義了一個方法cursor(),返回值是指向當(dāng)前結(jié)點的指
針。類List還定義了一些方法來實現(xiàn)對鏈表的基本操作，通過運用這些基本操作
我們可以對鏈表進(jìn)行各種操作。例如reset()方法使第一個結(jié)點成為當(dāng)前結(jié)點。
insert(Object d)方法在當(dāng)前結(jié)點前插入一個結(jié)點，并使其成為當(dāng)前結(jié)點。
remove()方法刪除當(dāng)前結(jié)點同時返回其內(nèi)容，并使其后繼結(jié)點成為當(dāng)前結(jié)點，如
果刪除的是最 后一個結(jié)點，則第一個結(jié)點變?yōu)楫?dāng)前結(jié)點。
鏈表類List的源代碼如下：
import java.io.*;
public class List
{
/*用變量來實現(xiàn)表頭*/
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()
/*鏈表復(fù)位，使第一個結(jié)點成為當(dāng)前結(jié)點*/
{
Pointer=null;
}
public boolean isEmpty()
/*判斷鏈表是否為空*/
{
return(Length==0);
}
public boolean isEnd()
/*判斷當(dāng)前結(jié)點是否為最后一個結(jié)點*/
{
if(Length==0)
throw new java.lang.NullPointerException();
else if(Length==1)
return true;
else
return(cursor()==Tail);
}
public Object nextNode()
/*返回當(dāng)前結(jié)點的下一個結(jié)點的值，并使其成為當(dāng)前結(jié)點*/
{
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é)點的值*/
{
Node temp=cursor();
return temp.data;
}
public void insert(Object d)
/*在當(dāng)前結(jié)點前插入一個結(jié)點，并使其成為當(dāng)前結(jié)點*/
{
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é)點移出鏈表，下一個結(jié)點成為當(dāng)前結(jié)點，如果移出的結(jié)點是最后
一個結(jié)點，則第一個結(jié)點成為當(dāng)前結(jié)點*/
{
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é)點的指針*/
{
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();
//確保用戶看清程序運行結(jié)果
}
catch(IOException e)
{}
}
}
class Node
/*構(gòu)成鏈表的結(jié)點定義*/
{
Object data;
Node next;
Node(Object d)
{
data=d;
next=null;
}
}
讀者還可以根據(jù)實際需要定義新的方法來對鏈表進(jìn)行操作。雙向鏈表可以用
類似的方法實現(xiàn)只是結(jié)點的類增加了一個指向前趨結(jié)點的指針。
可以用這樣的代碼來實現(xiàn)：
class Node
{
Object data;
Node next;
Node previous;
Node(Object d)
{
data=d;
next=null;
previous=null;
}
}
當(dāng)然，雙向鏈表基本操作的實現(xiàn)略有不同。鏈表和雙向鏈表的實現(xiàn)方法，也
可以用在堆棧和隊列的實現(xiàn)中，這里就不再多寫了，有興趣的讀者可以將List類
的代碼稍加改動即可。
1.先定義一個節(jié)點類
package com.buren;
public class IntNode {
//定義一個節(jié)點類
int
info;
//定義屬性，節(jié)點中的值
IntNode next;
//定義指向下一個節(jié)點的屬性
public IntNode(int
i){ //構(gòu)造一個next為空的節(jié)點
this(i,null);
}
public IntNode(int i,IntNode
n){ //構(gòu)造值為i指向n的節(jié)點
info=i;
next=n;
}
}
2.再定義一個鏈表類，這是主要部分
package com.buren;
public class IntSLList {
private IntNode head,tail;
//定義指向頭結(jié)點和尾結(jié)點的指針，
//如果大家看著這個不像指針的話，那就需要對指針有更深刻的了解
public
IntSLList(){
//定義一個空節(jié)點
head=tail=null;
}
public boolean
isEmpty(){
//判斷節(jié)點是否為空
return
head==null;
//這行代碼看起來似乎很神奇，其實真的很神奇，偶是服了
}
public void addToHead(int el){
//將el插入到頭結(jié)點前
head=new
IntNode(el,head);
//將節(jié)點插入到頭結(jié)點前，作為新的投節(jié)點
if(head==tail){
//給空鏈表插入節(jié)點時
tail=head;
//頭結(jié)點和尾結(jié)點指向同一個節(jié)點
}
}
public void addToTail(int
el){
//向鏈表的尾部增加結(jié)點
if(!isEmpty()){
//判斷鏈表是否為空
tail.next=new
IntNode(el);
//新建立一個值為el的節(jié)點，將鏈表的尾結(jié)點指向新節(jié)點
tail=tail.next;
//更新尾指針的指向
}else{
head=tail=new
IntNode(el);
//如果鏈表為空，新建立一個節(jié)點，將頭尾指針同時指向這個節(jié)點
}
}
public int
deleteFromHead(){
//刪除頭結(jié)點，將節(jié)點信息返回
int
el=head.info;
//取出節(jié)點信息
if(head==tail){
//如果鏈表中只有一個節(jié)點
head=tail=null;
//刪除這一個節(jié)點
}else{
head=head.next;
//如果鏈表中不止一個節(jié)點，將頭結(jié)點的胡敬下一個節(jié)點作為頭結(jié)點
}
return
el;
//返回原頭結(jié)點的值
}
public int
deleteFromTail(){
//刪除尾結(jié)點，返回尾結(jié)點的信息
int
el=tail.info;
//取出尾結(jié)點的值
if(head==tail){
// 如果鏈表中只有一個節(jié)點
head=tail=null;
//刪除這個節(jié)點
}else{
IntNode
temp;
//定義中間變量
for(temp=head;temp.next!=tail;temp=temp.next);
//找出尾結(jié)點的前一個節(jié)點，注意最后的分號，
//這個for循環(huán)是沒有循環(huán)體的，目滲棗的在于找出尾結(jié)點的前一個節(jié)點
//在整個程序中用了很多次這樣的寫褲喊慎法，相當(dāng)經(jīng)典啊
tail=temp;
//將找出來的節(jié)點作為尾結(jié)點，刪除原來的尾結(jié)點
tail.next=null;
//將新尾結(jié)點的指向設(shè)為空
}
return
el;
//返回原尾結(jié)點的信息
}
public void
printAll(){
//打印鏈表中所有節(jié)點的信息
if(isEmpty()){
//如果鏈表為空
System.out.println("This
list is
empty!");
//輸出提示信息
return;
//返回到調(diào)用的地方
}
if(head==tail){
//當(dāng)鏈表中只有一個節(jié)點時
System.out.println(head.info);
//輸出這個節(jié)點的信息，就是頭結(jié)點的信息
return;
}
IntNode
temp;
//定義一個中間變量
for(temp=head;temp!=null;temp=temp.next){
//遍歷整個鏈表
System.out.print(temp.info+"
");
//輸出每個節(jié)點的信息
}
System.out.println();
//輸出一個換行，可以沒有這一行
}
public boolean isInList(int
el){
//判斷el是否存在于鏈表中
IntNode
temp;
//定義一個中間變量
for(temp=head;temp!=null
temp.info!=el;temp=temp.next);
//將el找出來，注意最后的分
return
temp!=null;
// 如果存在返回true，否則返回flase，這兩行代碼很有思想
}
public void delete(int
el){
//刪除鏈表中值為el的節(jié)點
if(head.info==el
head==tail){
//如果只有一個節(jié)點，并且節(jié)點的值為el
head=tail=null;
//刪除這個節(jié)點
}else
if(head.info==el){
// 不止一個節(jié)點，而頭結(jié)點的值就是el
head=head.next;
//刪除頭結(jié)點
}else{
IntNode
pred,temp;
//定義兩個中間變量
for(pred=head,temp=head.next;temp.info!=el
temp.next!=null;pred=pred.next,temp=temp.next);
//跟上面的類似，自己琢磨吧，也是要注意最后的分號
pred.next=temp.next;
//將temp指向的節(jié)點刪除，最好畫一個鏈表的圖，有助于理解
if(temp==tail){
//如果temp指向的節(jié)點是尾結(jié)點
tail=pred;
//將pred指向的節(jié)點設(shè)為尾結(jié)點，
}
}
}
//下面這個方法是在鏈表中值為el1的節(jié)點前面插入一個值為el2的節(jié)點，
//用類似的思想可以再寫一個在鏈表中值為el1的節(jié)點后面插入一個值為el2的節(jié)點
public boolean insertToList(int el1,int
el2){
//定義一個插入節(jié)點的方法，插入成功返回true，否則返回false
IntNode
pred,temp; //定義兩個中間變量
if(isEmpty()){
//判斷鏈表是否為空
return
false;
//如果鏈表為空就直接返回false
}
if(head.info==el1
head==tail){
//如果鏈表中只有一個節(jié)點，并且這個節(jié)點的值是el1
head=new
IntNode(el2,head);
//新建立一個節(jié)點
return
true;
}else if(head.info==el1){
IntNode t=new
IntNode(el2);
t.next=head;
head=t;
return
true;
}else{
for(pred=head,temp=head.next;temp!=null
temp.info!=el1;pred=pred.next,temp=temp.next);
if(temp!=null){
IntNode
a=new IntNode(el2);
pred.next=a;
a.next=temp;
return
true;
}else{
System.out.println(el1+"
NOT EXEISTS!");
return
false;
}
}
}
3.下面是測試代碼
public static void main(String[] args){
IntSLList test=new
IntSLList();
//test.addToHead(7);
test.addToTail(7);
System.out.println(test.insertToList(7,5));
test.printAll();
System.out.println(test.isInList(123));
}
}
Java語言中的對象引用實際上是一個指針（這里的指針均為概念褲讓上的意義，而非語言提供的數(shù)據(jù)類型），所以我們可以編寫這樣的類來實現(xiàn)鏈表中的結(jié)點。
程序代碼：
class?Node?
{?
Object?data;?
Node?next;//指向下一個結(jié)點?
}
將數(shù)據(jù)域定義成Object類是因為Object類是廣義超類，任何類對象都可以給其賦值，增加了代碼的通用性。為了使鏈表可以被訪問還需要定義一個表頭，表頭必須包含指向第一個結(jié)點的指針和指向當(dāng)前結(jié)點的指針。為了便于在鏈表尾部增加結(jié)點，還可以增加一指向鏈表尾部的指針，另外還可以用一個域來表示鏈表的大小，當(dāng)調(diào)用者想得到鏈表的大小時，不必遍歷整個鏈表。
鏈表的數(shù)據(jù)結(jié)構(gòu)我們可以用類List來實現(xiàn)鏈表結(jié)構(gòu)，用變量Head、Tail、Length、Pointer來實現(xiàn)表頭。存儲當(dāng)前結(jié)點的指針時有一定的技巧，Pointer并非存儲指向當(dāng)前結(jié)點的指針，而是存儲指向它的前趨結(jié)點的指針,當(dāng)其值為null時表示當(dāng)前結(jié)點是第一個結(jié)點，因為當(dāng)刪除當(dāng)前結(jié)點后仍需保證剩下的結(jié)點構(gòu)成鏈表，如果Pointer指向當(dāng)前結(jié)點，則會給操作帶來很大困難。如何得到當(dāng)前結(jié)點呢？我們定義了一個方法cursor(),返回值是指向當(dāng)前結(jié)點的指針。類List還定義了一些方法來實現(xiàn)對鏈表的基本操作，通過運用這些基本操作我們可以對鏈表進(jìn)行各種操作。例如reset()方法使第段散一個結(jié)點成為當(dāng)前結(jié)點。insert(Object d)方法在當(dāng)前結(jié)點前插入一個結(jié)點，并使其成為當(dāng)前結(jié)點。remove()方法刪除當(dāng)前結(jié)點同時返回其內(nèi)容，并使其后繼結(jié)點成為當(dāng)前結(jié)點，如果刪除的是最后一個結(jié)點，則第一個結(jié)握純氏點變?yōu)楫?dāng)前結(jié)點。
鏈表類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;
}
}
當(dāng)然，雙向鏈表基本操作的實現(xiàn)略有不同。鏈表和雙向鏈表的實現(xiàn)方法，也可以用在堆棧和隊列的現(xiàn)實中。
重慶分公司
重慶分公司
