第Java數(shù)據(jù)結(jié)構(gòu)之雙向鏈表的實(shí)現(xiàn)目錄1雙向鏈表1.1雙向鏈表介紹1.2雙向鏈表實(shí)現(xiàn)思路2雙向鏈表實(shí)現(xiàn)完整代碼2.1節(jié)點(diǎn)類Student.java2.2雙向鏈表實(shí)現(xiàn)類StudentDoubleLinkedList.java2.3測(cè)試類StudentDoubleLinkedListDemo.java2.4結(jié)果3雙向鏈表小結(jié)

1雙向鏈表

1.1雙向鏈表介紹

相較單鏈表，雙向鏈表除了data與next域，還多了一個(gè)pre域用于表示每個(gè)節(jié)點(diǎn)的前一個(gè)元素。這樣做給雙向鏈表帶來了很多優(yōu)勢(shì)：

單向鏈表查找的方向只能是一個(gè)方向，而雙向鏈表可以向前或者向后查找；

單鏈表如果想要實(shí)現(xiàn)刪除操作，需要找到待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。而雙向鏈表可以實(shí)現(xiàn)自我刪除。

雙向鏈表結(jié)構(gòu)示意圖如下：

1.2雙向鏈表實(shí)現(xiàn)思路

與單鏈表實(shí)現(xiàn)類似，交集部分不再贅述，詳情可參考文章：Java數(shù)據(jù)結(jié)構(gòu)：?jiǎn)捂湵淼膶?shí)現(xiàn)與面試題匯總

遍歷：

與單鏈表遍歷方式一樣，同時(shí)，雙向鏈表可以支持向前和向后兩種查找方式

添加：

添加到末尾

先找到雙向鏈表最后一個(gè)節(jié)點(diǎn)cur.next=newNode；newNode.pre=cur；

按照no順序添加

先判斷該鏈表是否為空，如果為空則直接添加如果不為空則繼續(xù)處理根據(jù)no遍歷鏈表，找到合適的位置newNode.next=cur.next;cur.next=newNode;newNode.pre=cur;

修改操作與單鏈表實(shí)現(xiàn)步驟一致

刪除操作：

雙向鏈表可以實(shí)現(xiàn)自我刪除直接找到待刪除的節(jié)點(diǎn)cur.pre.next=cur.next;cur.next.pre=cur.pre;需要特別注意是否為最后一個(gè)元素，如果為最后一個(gè)元素，cur.next為null，此時(shí)使用cur.next.pre會(huì)出現(xiàn)空指針異常，所以，如果為最后一個(gè)元素，則該步驟可以省略，cur.next為null即可。

以刪除紅色的2號(hào)節(jié)點(diǎn)為例：

2雙向鏈表實(shí)現(xiàn)完整代碼

2.1節(jié)點(diǎn)類Student.java

/**

*@author興趣使然黃小黃

*@version1.0

*學(xué)生類節(jié)點(diǎn)

publicclassStudentNode{

publicStringno;//學(xué)號(hào)

publicStringname;//姓名

publicintage;//年齡

publicStudentNodepre;//指向前一個(gè)節(jié)點(diǎn)

publicStudentNodenext;//指向下一個(gè)節(jié)點(diǎn)

//構(gòu)造器

publicStudentNode(Stringno,Stringname,intage){

this.no=no;

=name;

this.age=age;

//為了顯示方便

@Override

publicStringtoString(){

return"StudentNode{"+

"no='"+no+'\''+

",name='"+name+'''+

",age="+age+

'}';

2.2雙向鏈表實(shí)現(xiàn)類StudentDoubleLinkedList.java

/**

*@author興趣使然黃小黃

*@version1.0

*學(xué)生雙向鏈表的具體實(shí)現(xiàn)

publicclassStudentDoubleLinkedList{

//定義頭節(jié)點(diǎn)

privateStudentNodehead=newStudentNode("","",0);

//獲取頭節(jié)點(diǎn)

publicStudentNodegetHead(){

returnhead;

//遍歷雙向鏈表的方法

publicvoidshowList(){

//判斷鏈表是否為空

if(head.next==null){

System.out.println("當(dāng)前鏈表為空");

return;

//遍歷使用輔助指針

StudentNodetemp=head;

while(temp!=null){

//更新指針

temp=temp.next;

if(temp.next==null){

System.out.print(temp);

break;

System.out.print(temp+"---

//添加節(jié)點(diǎn)的方法

//添加到尾部

publicvoidadd(StudentNodenewNode){

//先找到最后一個(gè)節(jié)點(diǎn)

StudentNodecur=head;

while(true){

//到達(dá)最后退出循環(huán)

if(cur.next==null){

break;

//更新指針

cur=cur.next;

//添加操作

newNode.next=cur.next;//也可以省略，因?yàn)楹銥閚ull

cur.next=newNode;

newNode.pre=cur;

//添加節(jié)點(diǎn)的方法

//根據(jù)學(xué)號(hào)順序添加

publicvoidaddByOrder(StudentNodenewNode){

//如果當(dāng)前鏈表為空，則直接添加

if(head.next==null){

head.next=newNode;

newNode.pre=head;

return;

//按照學(xué)號(hào)找到對(duì)應(yīng)位置

StudentNodecur=head;

booleanflag=false;//標(biāo)識(shí)待添加的no是否存在

while(true){

if(cur.next==null){

//已經(jīng)到達(dá)鏈表的尾部

break;

}elseif(Integer.parseInt(cur.next.no)==Integer.parseInt(newNode.no)){

//已經(jīng)存在

flag=true;

break;

}elseif(Integer.parseInt(cur.next.no)Integer.parseInt(newNode.no)){

//位置找到

break;

cur=cur.next;

if(flag){

System.out.println("當(dāng)前no已經(jīng)存在，無法添加!");

}else{

//添加操作

newNode.next=cur.next;

cur.next=newNode;

newNode.pre=cur;

//根據(jù)no學(xué)號(hào)修改學(xué)生信息

publicvoidupdate(StudentNodestudentNode){

if(head.next==null){

System.out.println("當(dāng)前鏈表為空,無法修改");

return;

StudentNodetemp=head.next;

booleanflag=false;//表示是否找到節(jié)點(diǎn)

while(true){

if(temp==null){

break;

if(temp.no==studentNode.no){

flag=true;

break;

temp=temp.next;

if(flag){

=studentN;

temp.age=studentNode.age;

System.out.println("更新成功!");

}else{

System.out.println("沒有找到");

//從雙向鏈表中刪除節(jié)點(diǎn)

publicvoiddelete(Stringno){

//直接找到對(duì)應(yīng)no的節(jié)點(diǎn)直接刪除

StudentNodecur=head.next;

booleanflag=false;//標(biāo)記是否找到

while(true){

if(cur==null){

break;

if(cur.no.equals(no)){

flag=true;//找到了

break;

cur=cur.next;

if(flag){

//刪除操作

//注意考慮最后一個(gè)節(jié)點(diǎn)后一個(gè)為空的情況

if(cur.next!=null){

cur.next.pre=cur.pre;

cur.pre.next=cur.next;

System.out.println("刪除成功!");

}else{

System.out.println(no+"節(jié)點(diǎn)不存在，無法刪除！");

2.3測(cè)試類StudentDoubleLinkedListDemo.java

/**

*@author興趣使然黃小黃

*@version1.0

*雙向鏈表測(cè)試類

publicclassDoubleLinkedListDemo{

publicstaticvoidmain(String[]args){

StudentDoubleLinkedListdoubleLinkedList=newStudentDoubleLinkedList();

doubleLinkedList.addByOrder(newStudentNode("1","黃小黃",20));

doubleLinkedList.addByOrder(newStudentNode("3","懶羊羊",20));

doubleLinkedList.addByOrder(newStudentNode("2","沸羊羊",25));

doubleLinkedList.addByOrder(newStudentNode("4","美羊羊",15));

System.out.println("遍歷:");

doubleLinkedList.showList();

//測(cè)試更新方法

System.out.println("\n更新編號(hào)為4的信息后:");

doubleLinkedList.update(newStudentNode("4","禰豆子",14));

doubleLinkedList.showList();

//測(cè)試刪除方法

System.out.println("\n刪除第一個(gè)和最后一個(gè):");

doubleLinkedList.delete("1");

doubleLinkedList.delete("4");

doubleLinkedList.showList();

2.4結(jié)果

遍歷:

StudentNode{no=1,name=黃小黃,age=20}---StudentNode{no=2,name=沸羊羊,age=25}---StudentNode{no=3,name=懶羊羊,age=20}---StudentNode{no=4,name=美羊羊,age=15}

更新編號(hào)為4的信息后:

更新成功!

StudentNode{no=1,name=黃小黃,age=20}---StudentNode{no=2,name=沸羊羊,age=25}---StudentNode{no=3,name=懶羊羊,age=20}---StudentNode{no=4,name=禰豆子,age=14}

刪除第一個(gè)和最后一個(gè):

刪除成功!

刪除成功!

StudentNode{no=2,name=沸羊羊,age=25}---StudentNode{no=3,name=懶羊羊,age=20}

Processfi