鏈表是一種重要的數(shù)據(jù)結(jié)構(gòu)，在程序設(shè)計中占有很重要的地位。C語言和C＋＋語言中是用指針來實現(xiàn)鏈表結(jié)構(gòu)的，由于Java語言不提供指針，所以有人認為在Java語言中不能實現(xiàn)鏈表，其實不然，Java語言比C和C＋＋更容易實現(xiàn)鏈表結(jié)構(gòu)。Java語言中的對象引用實際上是一個指針（本文中的指針均為概念上的意義，而非語言提供的數(shù)據(jù)類型），所以我們可以編寫這樣的類來實現(xiàn)鏈表中的結(jié)點。
創(chuàng)新互聯(lián)建站-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價比共青城網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式共青城網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋共青城地區(qū)。費用合理售后完善，10年實體公司更值得信賴。
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)對鏈表的基本操作，通過運用這些基本操作我們可以對鏈表進行各種操作。例如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ù)實際需要定義新的方法來對鏈表進行操作。雙向鏈表可以用類似的方法實現(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類的代碼稍加改動即可。
希望對你有幫助。
這是我寫的一個差不多，你看一下吧：
package com.test.list;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class LinkedList {
public static void main(String[] args) {
MyList l = new MyList();
MyListNode node = l.createList();
l.printNode(node);
//l.searchNode(node, 4);
//node = l.insertNode(node, 3, "g");
//l.printNode(node);
node = l.deleteNode(node, "d");
l.printNode(node);
}
}
class MyListNode {
public String data;
public MyListNode nextNode;
}
class MyList {
public MyListNode createList() {
MyListNode node = new MyListNode();
MyListNode q ,p;
q = new MyListNode();
q = node;
while (true) {
String s = null;
try {
BufferedReader br = new BufferedReader(new InputStreamReader(
System.in));
System.out.println("請輸入節(jié)點數(shù)據(jù)：");
s = br.readLine();
if (s.equals("0")) {
break;
} else {
p = new MyListNode();
p.data = s;
p.nextNode = null;
q.nextNode = p;
q = p;
}
} catch (Exception e) {
e.printStackTrace();
}
}
return node;
}
public void printNode(MyListNode node) {
MyListNode p = node.nextNode;
while (p!= null) {
System.out.print(" "+p.data);
p = p.nextNode;
}
}
public void searchNode(MyListNode node, int i){
MyListNode p = node.nextNode;
int j = 1;
while (p != null ji) {
p = p.nextNode;
j++;
}
if( p == null || ji) {
System.out.println("error");
}
System.out.println(" --"+p.data+"--");
}
public MyListNode insertNode(MyListNode node, int i ,String s) {
MyListNode p = node.nextNode;
int j = 1;
while (p != null ji-1) {
p = p.nextNode;
j++;
}
if( p == null || ji-1) {
System.out.println("error");
}
MyListNode n = new MyListNode();
n.data = s;
n.nextNode = p.nextNode;
p.nextNode = n;
return node;
}
public MyListNode deleteNode(MyListNode node ,String s) {
MyListNode p = node;
while(p.nextNode != null !p.nextNode.data.equals(s)) {
p = p.nextNode;
}
p.nextNode = p.nextNode.nextNode;
return node;
}
}
/*逆位序創(chuàng)建
public MyListNode createList() {
MyListNode node = new MyListNode();
node.nextNode = null;
while(true) {
String s = null;
try {
BufferedReader br = new BufferedReader(new InputStreamReader(
System.in));
System.out.println("請輸入節(jié)點數(shù)據(jù)：");
s = br.readLine();
if(s.equals("0")) {
break;
}else {
MyListNode n = new MyListNode();
n.data = s;
n.nextNode = node.nextNode;
node.nextNode = n;
}
} catch (Exception e) {
e.printStackTrace();
}
}
return node;
}
*/
實現(xiàn)鏈表的思路： 1）鏈表類，結(jié)點類（鏈表類的內(nèi)部類），在main()方法創(chuàng)建一條鏈表類對象，通過方法逐步創(chuàng)建結(jié)點類，通過引用鏈接起來成為鏈表。2）結(jié)點類包含數(shù)據(jù)和對下個結(jié)點的引用，以及可以對數(shù)據(jù)賦值的構(gòu)造函數(shù)。3）鏈表類的構(gòu)造方法，只構(gòu)造出不含數(shù)據(jù)的頭結(jié)點。（外部類可以直接對內(nèi)部類的私有成員進行訪問，這樣就可以直接修改引用）
class Node {
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語言不提供指針，所以有人認為在
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)對鏈表的基本操作，通過運用這些基本操作
我們可以對鏈表進行各種操作。例如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ù)實際需要定義新的方法來對鏈表進行操作。雙向鏈表可以用
類似的方法實現(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類
的代碼稍加改動即可。
樓主，這個是合理的，分析如下：
在List 類的add方法中，循環(huán)：
while (e.next!=null)//居然是空的 那么這里判斷他非空不是沒有意義么
e=e.next;
作用是獲取鏈表的最后一個元素，以使新添加的結(jié)點能夠掛到最后面。當(dāng)你第一次添加結(jié)點的時候， head的next也是為空，那么循環(huán)后面的兩句代碼：
e.next=newEntry;
return newEntry;（注意這兩句不屬于循環(huán)體）意思就是把head的next結(jié)點設(shè)置為新添加的結(jié)點了。這個時候，head的next值就不為空了，其指向的是你剛才添加的結(jié)點。
這時如果再次添加結(jié)點，循環(huán)while (e.next!=null)將會循環(huán)一次，在循環(huán)結(jié)束時，e就不再指向head了，而是指向你上次添加的結(jié)點，也就是鏈表的最后一個結(jié)點。
remove方法中也是這樣的原理。希望能幫助到樓主
重慶分公司
重慶分公司
