第Java實現雙鏈表的示例代碼目錄一、雙向鏈表是什么二、具體方法實現定義結點下標訪問異常獲取鏈表長度打印鏈表清空鏈表頭插法尾插法指定位置插入查找元素刪除第一次出現的關鍵字刪除所有值為key的節點三、完整代碼

一、雙向鏈表是什么

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。一般我們都構造雙向循環鏈表。

LinkedList底層就是一個雙向鏈表，我們來實現一個雙向鏈表。

這里多一個尾指針，方便我們對尾插操作從O(n)降到O(1).每個結點多了前驅結點，方便我們對鏈表進行操作。

二、具體方法實現

定義結點

classListNode{

intvalue;

ListNodenext;

ListNodeprev;

publicListNode(intvalue){

this.value=value;

下標訪問異常

publicclassIndexWrongExceptionextendsRuntimeException{

publicIndexWrongException(){

publicIndexWrongException(Stringmessage){

super(message);

獲取鏈表長度

classListNode{

intvalue;

ListNodenext;

ListNodeprev;

publicListNode(intvalue){

this.value=value;

打印鏈表

classListNode{

intvalue;

ListNodenext;

ListNodeprev;

publicListNode(intvalue){

this.value=value;

清空鏈表

publicvoidclear(){

if(this.head==null){

return;

ListNodecur=this.head;

while(cur!=null){

ListNodecurNext=cur.next;

cur.prev=null;

cur.next=null;

cur=curNext;

head=null;

tail=null;

頭插法

publicvoidaddFirst(intdata){

ListNodenode=newListNode(data);

if(head==null){

this.head=node;

this.tail=node;

return;

node.next=this.head;

this.head.prev=node;

this.head=node;

尾插法

publicvoidaddLast(intdata){

ListNodenode=newListNode(data);

if(head==null){

this.head=node;

this.tail=node;

return;

tail.next=node;

node.prev=tail;

tail=node;

指定位置插入

publicvoidaddIndex(intindex,intdata)throwsIndexWrongException{

if(index0||indexsize()){

thrownewIndexWrongException("輸入下標不合法");

ListNodenode=newListNode(data);

if(index==0){

addFirst(data);

return;

if(index==size()){

addLast(data);

return;

ListNodecur=this.head;

while(index!=0){

cur=cur.next;

index--;

node.next=cur;

cur.prev.next=node;

node.prev=cur.prev;

cur.prev=node;

}

查找元素

publicbooleancontains(intkey){

if(head==null){

returnfalse;

ListNodecur=this.head;

while(cur!=null){

if(cur.value==key){

returntrue;

cur=cur.next;

returnfalse;

刪除第一次出現的關鍵字

publicvoidremove(intkey){

ListNodecur=head;

while(cur!=head){

if(cur.value==key){

if(cur==head){

head=head.next;

if(head.next!=null){

head.prev=null;

}else{

tail=null;

}else{

cur.prev.next=cur.next;

if(cur.next!=null){

cur.next.prev=cur.prev;

}else{

tail=cur.prev;

tail.next=null;

return;

cur=cur.next;

}

刪除所有值為key的節點

publicvoidremoveAllKey(intkey){

ListNodecur=head;

while(cur!=head){

if(cur.value==key){

if(cur==head){

head=head.next;

if(head.next!=null){

head.prev=null;

}else{

tail=null;

}else{

cur.prev.next=cur.next;

if(cur.next!=null){

cur.next.prev=cur.prev;

}else{

tail=cur.prev;

tail.next=null;

cur=cur.next;

}

三、完整代碼

publicclassLinkedList{

staticclassListNode{

intvalue;

ListNodenext;

ListNodeprev;

publicListNode(intvalue){

this.value=value;

ListNodehead;

ListNodetail;

//頭插法

publicvoidaddFirst(intdata){

ListNodenode=newListNode(data);

if(head==null){

this.head=node;

this.tail=node;

return;

node.next=this.head;

this.head.prev=node;

this.head=node;

//尾插法

publicvoidaddLast(intdata){

ListNodenode=newListNode(data);

if(head==null){

this.head=node;

this.tail=node;

return;

tail.next=node;

node.prev=tail;

tail=node;

//任意位置插入,第一個數據節點為0號下標

publicvoidaddIndex(intindex,intdata)throwsIndexWrongException{

if(index0||indexsize()){

thrownewIndexWrongException("輸入下標不合法");

ListNodenode=newListNode(data);

if(index==0){

addFirst(data);

return;

if(index==size()){

addLast(data);

return;

ListNodecur=this.head;

while(index!=0){

cur=cur.next;

index--;

node.next=cur;

cur.prev.next=node;

node.prev=cur.prev;

cur.prev=node;

//查找是否包含關鍵字key是否在單鏈表當中

publicbooleancontains(intkey){

if(head==null){

returnfalse;

ListNodecur=this.head;

while(cur!=null){

if(cur.value==key){

returntrue;

cur=cur.next;

returnfalse;

//刪除第一次出現關鍵字為key的節點

publicvoidremove(intkey){

ListNodecur=head;

while(cur!=head){

if(cur.value==key){

if(cur==head){

head=head.next;

if(head.next!=null){

head.prev=null;

}else{

tail=null;

}else{

cur.prev.next=cur.next;

if(cur.next!=null){

cur.next.prev=cur.prev;

}else{

tail=cur.prev;

tail.next=null;

return;

cur=cur.next;

//刪除所有值為key的節點

publicvoidremoveAllKey(intkey){

ListNodecur=head;

while(cur!=head){

if(cur.value==key){

if(cur==head){

head=head.next;

if(head.next!=null){

head.prev=null;

}else{

tail=null;

}else{

cur.prev.next=cur.next;

if(cur.next!=null){

cur.next.prev=cur.prev;

}else{

tail=cur.prev;

tail.next=null;

cur=cur.next;

//得到單鏈表的長度

publicintsize(){

ListNodecur=head;

intcount=0;

while(cur!=null){

cur=cur.next;

count++;

returncount;

publicvoiddisplay(){

ListNodecur=head;

while(cur!=null){

System.out.print(cur