Java數(shù)據(jù)結構和算法

第o講綜述

參考教材:Java數(shù)據(jù)結構和算法（第二版），［美］Robertlafore

L數(shù)據(jù)結構的特性

數(shù)據(jù)結構優(yōu)點缺點

數(shù)組插入快；如果知道下標，可以非?？斓卮嫒〔檎衣?，刪除慢，大小固定

有序數(shù)組比無序的數(shù)組查找快刪除和插入慢，大小固定

棧提供后進先出方式的存取存取其他項很慢

隊列提供先進先出方式的存取存取其他項很慢

鏈表插入快，刪除快查找慢

二叉樹查找、插入、刪除都快（如果樹保持平衡）刪除算法復雜

紅-黑樹查找、插入、刪除都快；樹總是平衡的算法復雜

2-3-4樹查找、插入、刪除都快；樹總是平衡的；類算法復雜

似的樹對磁盤存儲有用

哈希表如果關鍵字已知，則存儲極快；插入快刪除慢，如果不知道關鍵字則存

儲很慢,對存儲空間使用不充分

堆插入、刪除快；對大數(shù)據(jù)項的存取很快對其他數(shù)據(jù)項存取慢

圖對現(xiàn)實世界建模有些算法慢且復雜

2.經(jīng)典算法總結

查找算法：線性查找和二分查找

排序算法：

用表展示

第一講數(shù)組

1.Java中數(shù)組的基礎知識

1）創(chuàng)建數(shù)組

在Java中把數(shù)組當作對象來對待，因此在創(chuàng)建數(shù)組時必須使用new操作符:

int[]intArr=newint[10];

一旦創(chuàng)建數(shù)組，數(shù)組大小便不可改變。

2)訪問數(shù)組數(shù)據(jù)項

數(shù)組數(shù)據(jù)項通過方括號中的下標來訪問，其中第一個數(shù)據(jù)項的下標是0：

intArr[0]=123;

3)數(shù)組的初始化

當創(chuàng)建數(shù)組之后，除非將特定的值賦給數(shù)組的數(shù)據(jù)項，否則它們一史是特殊的null對象。

int(]intArr={1,2,3,4,5);

等效于下面使用new來創(chuàng)建數(shù)組并初始化:

int[]intArr=newint[5];

intArr[0]=1;

intArr[1]=2;

intArr[2]=3;

intArr[3]=4;

intArr[4]=5;

2.面向對象編程方式

1)使用自定義的類封裝數(shù)組

MyArray類：

publicclassMyArray{

privatelong[]arr;

privateintsize;//記錄數(shù)組的有效長度

publicMyArray(){

arr=newlong[10];

)

publicMyArray(intmaxSize){

arr=newlong[maxSize];

}

//向數(shù)組中插入數(shù)據(jù)

publicvoidinsert(longelement){

arr[size]=element;

size++;

)

//顯示數(shù)組中的數(shù)據(jù)

publicvoidshow(){

for(inti=0;i<size;i++){

if(i==0){

System.out.print(°[*,+arr[i；+",n);

}elseif(i==size-l){

System.out.printIn(arr[i]+"]**);

}else{

System.out.print(arr[i]+",H);

)

}

)

//根據(jù)值查找索引(出現(xiàn)該值的第一個位置)：線性杳找

publicintqueryByValue(longelement){

inti;

for(i=0;i<size;i++){//linearsearch

if(arr[i]==element)break；

}

if(i==size){

return-1;

}else{

returni;

)

}

〃根據(jù)索引查找值

publiclongqueryBylndex(intindex){

if(index>=sizeIIindex<0){

thrownewArraylndexOutOfBoundsException();

}else{

returnarr[index];

}

}

//刪除數(shù)據(jù)

publicvoiddelete(intindex){

if(index>=size||index<0){

thrownewArraylndexOutOfBoundsException();

}else{

//當size=maxSize,刪除最后一個數(shù)時，不會執(zhí)行for

for(inti=index;i<size-l;i++){

arr[index]=arr[index+1];

System.out.printin("for");

)

size——;

)

〃更新數(shù)據(jù)

publicvoidupdate(intindex,longvalue){

if(index>=size||index<0){

thrownewArraylndexOutOfBoundsException();

}else{

arr[index]=value;

}

)

}

2)添加類方法實現(xiàn)數(shù)據(jù)操作

測試MyArray類方法：

publicvoidtestMyArray()throwsException{

MyArraymyArray=newMyArray();

myArray.insert(123);

myArray.insert(456);

myArray.insert(789);

niyAx￡cty.show();//[123z456,789]

System.out.printIn(myArray.queryByValue(111));//-I

System.out.printin(myArray.queryBylndex(2));//789

myArray.delete(2);

myArray.show();//[123,456]

myArray.update(0,0);

myArray.show();//[0z456]

3.有序數(shù)組

1)有序數(shù)組簡介以及其優(yōu)點

有序數(shù)組是一種數(shù)組元素按一定的順序排列的數(shù)組，從而方便使用二分查找來查找數(shù)組中

特定的元素。有序數(shù)組提高了查詢的效率，但并沒有提高刪除和插入元素的效率。

2)構建有序數(shù)組

將2.1中自定義的類封裝數(shù)組MyArray的insert方法改為如下：

//向有序數(shù)組中插入數(shù)據(jù)，按大小從前往后排列

publicvoidinsert(longelement)(

inti;

for(i=0;i<size;i++){//findwhereitgoes

if(element<arr[i])break；

)

for(intj=size;j>i;j-){//movebiggeronesup

arr[j]=arr[j-1];

)

arr[i]=elenent;

size++;

得到有序數(shù)組的類封裝MyOrdcrcdArray類，測試該類中的insert方法：

publicvoidtestMyOrderedArray()throwsException{

MyOrderedArraymyOrderedArray=newMyOrderedArray();

myOrderedArray.insert(999);

myOrderedArray.insert(555);

myOrderedArray.insert(777);

myOrderedArray.show();//[555,777,999]

4.查找算法

1)線性查找

在查找過程中，將要查找的數(shù)一個一個地與數(shù)組中的數(shù)據(jù)項比較，直到找到要找的數(shù)。在2.1

中自定義的類封裝數(shù)組MyArray的queryByValue方法，使用的就是線性查找。

2)二分查找

二分查找(又稱折半查找)，即不斷將有序數(shù)組進行對半分割，每次拿中間位置的數(shù)和

要查找的數(shù)進行比較：如果要杳找的數(shù)<中間數(shù)，則表明要查的數(shù)在數(shù)組的前半段；如果要

查的數(shù)>中間數(shù)，則表明該數(shù)在數(shù)組的后半段；如果要查的數(shù)二中間數(shù)，則返回中間數(shù)。

在有序數(shù)組的類封裝類MyOrderedArray中添加binarySearch方法

~//根據(jù)值二分查找索引(前提：有序)

publicintbinarySearch(longvalue){

intmiddle=0;

intleft=0;

intright=size-1;

while(true)

middle=(left+right)/2;

if(arr[middle]==value){

returnmiddle;//foundit

}elseif(left>right){

return-1;//can'tfoundit

}else{//dividerange

if(arr[middle]>value){

right=middle-1;//inlowerhalf

}else{

left=middle+1;//inupperhalf

)

}

)

測試該二分查找方法：

publicvoidtestMyOrderedArray()throwsException{

MyOrderedArraymyOrderedArray=newMyOrderedArray();

myOrderedArray.insert(999);

myOrderedArray.insert(555);

myOrderedArray.insert(777);

myOrderedArray.insert(333);

System,out.printIn(myOrderedArray.bmarySearch(333));//0

第二講簡單排序

1.本講提到的排序算法都假定了數(shù)組作為數(shù)據(jù)存儲結構，本講所有算法的時間復雜度都

是。在大多數(shù)情況下，假設當數(shù)據(jù)展比較小或基本上有序時，插入排序算法是三種簡單排序

算法中最好的選擇，是應用最多的。對于更大數(shù)據(jù)量的排序來說，后面講到的快速排序通常

是最快的方法。

2.冒泡排序

1)基本思想

在要排序的一組數(shù)中，對當前還未排好序的范圍內的全部數(shù)，自下而上對相鄰的兩個數(shù)依次

進行比較和調整，讓較大的數(shù)往下沉，較小的往上冒。即：每當兩相鄰的數(shù)比較后發(fā)現(xiàn)它們

的排序與排序要求相反時.就將它們互換。

2)算法實現(xiàn)

冒泡排序的Java代碼:

//bubblesort

publicstaticvoidbubbleSort(long[]arr){

longtemp;

for(inti=0;Karr.length-1;i++){//outerloop(forward)

for(intj=arr.length-1;j>i;j-){//innerloop(backward)

if(arr[j]<arr[j-1]){//swapthem

temp=arr[j];

arr[j]=arr[j-l];

arr[j-1]=temp;

)

)

)

}

測試冒泡排序及輸出結果：

publicvoidtestBubbleSort()throwsException{

long[]arr={79,91,13,52,34);

Sort.bubbleSort(arr);

System.out.printIn(Arrays.toStringfarr));//[13,34,52,79,91]

3.選擇排序

1)基本思想

在要排序的一組數(shù)中，選出最小的一個數(shù)與第一個位置的數(shù)交換；然后在剩下的數(shù)當中再找

最小的與第二個位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個數(shù)和最后一個數(shù)比較為止。

與冒泡排序相比，選擇排序將必要的交換次數(shù)從O(N*N)減少到0(N),但比較次數(shù)仍然保持

為O(N*N)。

2)算法實現(xiàn)

選擇排序的Java代碼:

//LauxL

publicstaticvoidselectSort(long[]arr){

longtemp;

for(inti=0;i<arr.length-1;i++){//outerloop

intk=i;//locationofminimum

for(intj=i+l;j<arr.length;j++){//innerloop

if(arr[j]<arr[k]){

k=j;//anewminimumlocation

)

1

temp=arr[i];

arr[i]=arr[k];

arr[k]=temp;

)

測試選擇排序及輸出結果:

publicvoidtestSelectSort()throwsException(

long[]arr={79,91,13,52,34);

Sort.selectSort(arr);

System.out.printIn(Arrays.toString(arr));//[13,34,52,79,91]

)

4.插入排序

1)基本思想

在要排序的一組數(shù)中，假設前面(n-l)[n>=21個數(shù)己經(jīng)是排好順序的(局部有序),現(xiàn)在要把

第n個數(shù)插到前面的有序數(shù)中，使得這n個數(shù)也是排好順序的。如此反復循環(huán)，直到全部排

好順序。

在插入排序中，一組數(shù)據(jù)僅僅是局部有序的；而冒泡排序和選擇排序，一組數(shù)據(jù)項在某個時

刻是完全有序的。

2)算法實現(xiàn)

插入排序的Java代碼：

//insertsort

publicstaticvoidinsertsort(long[]arr){

longtemp;

for(inti=l;i<arr.length;i++){//iismarkedlocation

temp=arr[i];//removemarkeditem

intj=i;//startshiftsati

while(j>=l&&arr[j-1]>temp){//untiloneissmaller

arr[j；=arr[j-1];//shiftitemright

j;//goleftoneposition

)

arr[j]=temp;//insertmarkeditem

)

}

測試插入排序以及輸出結果：

publicvoidtestlnsertSort()throwsException{

long[]arr={79,91,13,52,34,34);

Sort.insertSort(arr);

System.out.printIn(Arrays.toString(arr));

//[13,34,34,52,79,91]

第三講棧和隊列

1.棧和隊列都是抽象數(shù)據(jù)類型(abstractdautype,ADT),它們既可以用數(shù)組實現(xiàn)，乂可以

用鏈表實現(xiàn)。

2.棧

1)棧模型

入棧出棧

{A,B,C,D}{D,C,B,A}

棧頂D

C

B

A

棧底

棧（Slack,乂LIFO:后進先出）是一種只能在固定的一端進行插入和刪除的數(shù)據(jù)結構。棧

只允許訪問一個數(shù)據(jù)項：即最后插入的數(shù)據(jù)項，移除這個數(shù)據(jù)項后才能訪問倒數(shù)第二個插入

的數(shù)據(jù)項，以此類推。?？梢杂脭?shù)組來實現(xiàn)，也可以用鏈表來實現(xiàn)。

2）棧的數(shù)組實現(xiàn)

棧的Java代碼：

publicclassMyStack{

privatelong[]arr;//底層使用數(shù)組實現(xiàn)

privateinttop;

publicMyStack(){

arr=newlong[10];

top=-1;

}

publicMyStack(intmaxSize)(

arr=newlong[maxSize];

top=-1;

}

//putitemonLopo￡stack

publicvoidpush(longvalue){

arr[++top]=value;

)

//takeitemfromtopofstack

publiclongpop(){

returnarr[top——];

//peekattopofstack

publiclongpeek(){

returnarr[top);

)

//tureifstackisempty

publicbooleanisEmpty(){

return(top==-1);

}

//tureifstackisfull

publicbooleanisFull(){

return(top==arr.length-1);

測試棧的特性：

publicvoidtestMyStack()throwsException{

MyStackmyStack=newMyStack(4);

myStack.push(12);

myStack.push(34);

myStack.push(56);

myStack.push(78);

System.out.piintin(myStack.isFull());//true

while(!myStack.isEmpty()){

System.out.print(myStack.pop());//78z56,34,12

if(!myStack.isEmpty()){

System.out.print('*,*');

)

)

System.out.printin();

System.out.printin(myStack.isFull());//false

3.隊列

1）隊列模型

隊列（Queue,乂FIFO:先進先出）是一種插入時在一端進行而刪除時在另一端進行的數(shù)據(jù)

結構。

為解決順序隊列假溢出問題，而采用循環(huán)隊列：即讓隊頭、隊尾指針在達到尾端時，又繞回

到開頭。

2）隊列的數(shù)組實現(xiàn)

隊列的Java代碼：

pxiblicclassMyQueue{

privatelong[]arr;

privateintsize;

privateintfront;

privateintrear;

publicMyQueue(){

arr=newlong[10];

size=0;

front=0;

rear=-1;

}

publicMyQueue(intmaxSize)(

arr=newlong(maxSize];

size=0;

front=0;

rear=-1;

//putitematrearofqueue

publicvoidinsert(longvalue){

if(isEmpty()){//throv;exceptionifqueueisfull

thrownewArrayindexoutofBoundsException();

}______

if(rear==arr.length-1){//dealwithwraparound(環(huán)繞式處理)

rear=-1;

)

arr[++rear]=value;//incrementrearandinsert

size++;//incrementsize

//takeitemfromfrontofqueue

publiclongremove(){

longvalue=arr[front++];//getvalueandincrementfront

if(front==arr.length){//dealw_thwraparound

front=0;

)

size——;//onelessitem

returnvalue；

〃peekatfrontofqueue

publiclongpeek(){

returnarr[front];

)

//trueifqueueisempty

publicbooleanisEmpty(){

return(size==0);

)

//trueifqueueisfull

publicbooleanisFull(){

return(size==arr.length);

}

測試隊列的特性：

publicvoidtestMyQueue()throwsException{

MyQueuemyQueue=newMyQueue(4);

myQueue.insert(12);

myQueue.insert(34);

myQueue.insert(56);

myQueue.insert(78);

System.out.println(myQueue.isFull());//true

while(!myQueue.isEmpty()){

System.out.print(myQueue.remove());//12,34z56,78

if(!myQueue.isEmpty()){

System.out.print('*,*');

)

)

System.out.printin();

System.out.printin(myQueue.isEmpty());//true

myQueue.insert(99);

System.out.printin(myQueue.peek());//99

第四講鏈表

L鏈結點

一個鏈結點（Link,或稱結點）是某個類的對象，該對象中包含對下一個鏈結點引用的字段

（通常叫next）。而鏈表本身的對象中有一個字段指向對第一個鏈結點的引用，

datanext

head----------------------------------------------------------------------

—>----->—-----?Oj----?q+i—????-?an-iA

Link類的定義：

publicclassLink{

publiclongdata;//dataitem

publicLinknext;//nextlinkinlist

publicLink.(longdata)(

this.data=data;

}

publicvoiddisplayLink(){//displayourself

System,out.print(data+'*);

2.單鏈表(LinkList)

?LinkLisi類顯示了一個單鏈表，該鏈表可以進行的操作有：

在鏈表頭插入?個數(shù)據(jù)(insertFirst):設置新添加的結點的next設為原來的頭結點，再將新

添加的結點設為頭結點。

在鏈表頭刪除一個數(shù)據(jù)(deleteFirst):將第二個結點設為頭結點。

遍歷鏈表顯示所有數(shù)據(jù)(displayList)：使用臨時指針current,從頭結點開始，沿著鏈表先前

移動，依次遍歷每個節(jié)點。

LinkList類:

publicclassLinkList{

privateLinkfirst;//referencetofirstlinkonlist

publicLinkList(){

this.first=null;

}

//insertatstartoflist

publicvoidinsertFirst(longvalue){

LinknewLink=newLink(value);

newLink.next=first;//nev/Link-->oldfirst

first=newLink;//first——>newLink

}

//deletefirstitem

publicLinkdeleteFirst(){

if(first==null){

returnnull;

)

Linktemp=first;

first=first.next;//deleteit:first-->oldnext

returntemp;//returndeletedlink

)

publicvoiddisplayList(){

Linkcurrent=first;//startatteginningoflist

while(current!=null){//untilendoflist

current.displayLink.();

current=current.next;//movelisttonextlink

}

System.out.printIn();

}

}

測試LinkLisl類的方法:

publicvoidtestLinkList()throwsException{

LinkListlinkList=newLinkList();

linkList.insertFirst(88);

linkList.insertFirst(66);

linkList.insertFirst(44);

linkList.insertFirst(22);

linkList.displayList();//22-->44-->66-->88-->

linkList.deieteFirst();

linkList.displayList();//44-->66-->88-->

3.查找和刪除指定鏈結點

?此外，還能對指定的結點值進行查找和刪除：

查找指定結點(find):類似于之前的displayLisl方法。

刪除指定結點(delete)：在刪除指定結點時，必須把前一個結點和后一個結點連接在

一起，所以需要一個臨時指針(previous)來保存對前一個結點的引用。

向LinkList類中添加查找(find)和刪除(delete)方法：

//findlinkwithgivenkey

publicLinkfind(longkey){

Linkcurrent=first;//startat1first'

while(current.data!=key){

if(current.next==null){//didn*tfindit

returnnull;

}else{//gotonextlink

current=current.next;

)

)

returncurrent;

}

//deletelinkwithgivenkey

publicLink,delete(longkey){

Linkcurrent=first;//searchforexpectedlink

Linkprevious=first;

while(current.data!=key){

if(current.next==null){

returnnull;//didn*tfindit

}else{

previous=current;

current=current.next;//gotonextlink.

)

}//findit

if(current==first){//iffirstlink,changefirst

first=first.next;

}else{//otherwise,bypassit

previous.next=current.next;

)

returncurrent;

}

測試添加的find和delete方法：

publicvoidtestLinkList()throwsException{

LinkListlinkList=newLinkList();

linkList.insertFirst(88);

linkList.insertFirst(66);

linkList.insertFirst(44);

linkList.insertFirst(22);

linkList.displayList();//22―>44—>66—>88->

linkList.find(44).displayLink();//44-->

System.out.printIn();

linkList.delete(44).displayLink();//44-->

System.out.printIn();

linkList.displayList();//22-->66-->88-->

第五講雙端鏈表和雙向鏈表

1.雙端鏈表

鏈表中保存著對最后一個鏈結點的引用

?從頭部進行插入(inserlFirst):要對鏈表進行判斷，如果鏈表為空，則設置尾結點為新

添加的結點。

從尾部進行插入(insertLast)：如果鏈表為空，則直接設置頭結點為新添加的結點，否

則設置尾結點的后一個節(jié)點為新添加的結點。

從頭部進行刪除(deEeFirst)：判斷頭結點是否有二一個結點，如果沒有則設置尾結點

為nullo

雙端鏈表FirstLastList類:

publicclassFirstLastList{

privateLinkfirst;//referencetofirstlink

privateLinklast;//referencetolastlink

publicFirstLastList(){

this.first=null;

this.last=null;

}

publicbooleanisEmpty(){//trueifnolinks

returnfirst==null;

}

//insertatfrontoflist

publicvoidinsertFirst(longvalue){

LinknewLink=newLink(value);

if(isEmpty()){//ifemptylist

last=newLink;//newLink<--last

)

newLink.next=first;//newLink-->oldfirst

first=newLink;//first一一>newLink

}

//insertatendoflist

publicvoidinsertLast(longvalue){

LinknewLink=newLink(value);

if(isEmpty()){//ifemptylist

first=newLink;//first-->newLink

}else{

last.next=newLink;//oldlast——>newLink

)

last=nevzLink;//newLink<——last

}

//deletefirstlink

publicLinkdeleteFirst(){

Linktemp=first;

if(first.next——null){//ifonlyoneitem

last=null;//null<--last

)

first=first.next;//first-一>oldnext

returntemp;

}

publicvoiddisplayList(){

Linkcurrent=first;//startatteginningoflist

while(current!=null){//untilendoflist

current.displayLink.();

current=current.next;//movelisttonextlink

)

System.out.printIn();

}

}

測試FirstLastList類及輸出結果:

publicvoidtestFirstLastList()throwsException{

FirstLastListlist=newFirstLastList();

list.insertLast(24);

list.insertFirst(13);

list.insertFirst(5);

list.insertLast(46);

list.displayList();//5—>13—>24->46-->

list.deleteFirst();

list.displayList();//13-->24-->46-->

2.雙向鏈表

?雙向鏈表既允許向后遍歷，也允許向前遍歷整個鏈表。即每個節(jié)點除了保存了對下一個

節(jié)點的引用，同時后保存了對前一個節(jié)點的引用。

?從頭部進行插入(insertFirst):要對鏈表進行判斷，如果為空，則設置尾結點為新添加

的結點；如果不為空.還需要設置頭結點的前一個結點為新添加的結點。

?從尾部進行插入(insertLast):如果鏈表為空，則直接設置頭結點為新添加的結點，否

則設置尾節(jié)點的后一個結點為新添加的結點。同時設置新添加的結點的前一個結點為尾

結點。

?從頭部進行刪除(deleteFirst)：判斷頭結點是否有人一個結點，如果沒有則設置尾結點

為null；否則設置頭結點的下一個結點的previous為null.

?從尾部進行刪除(dclctcLast)：如果頭結點后沒有其他結點，則設置頭結點為null。否

則設置尾結點的前一個結點的next為nulU設置尾結點為其前一個結點。

在指定結點后插入(insertAfter):

刪除指定結點(deleteKey):不再需要在使用一個臨時的指針域指向前一個結點。

雙向鏈表的鏈接點Link類的定義:

publicclassDoubleLink{

publiclongdata;//dataitem

publicDoubleLinknext;//nextlinkinlist

publicDoubleLinkprevious;//previouslinkinlist

publicDoubleLink(longdata){

this.data=data;

}

publicvoiddisplayLink(){//displayourself

System,out.print(data+'*<==>");

}

)

雙向鏈表DoublyLinkedList類：

publicclassDoublyLinkedList{

privateDoubleLinkfirst;//referencetofirstlink

privateDoubleLinklast;//referencetolastlink

publicDoublyLinkedList(){

this.first=null;

this.last=null;

}

publicbooleanisEmpty(){//trueifnolinks

returnfirst==null;

}

//insertatfrontoflist

publicvoidinsertFirst(longvalue){

DoubleLinknewLink=newDoubleLink(value);

if(isEmpty()){//ifemptylist

last=newLink;//newLink<——last

}else{

first.previous=newLink;//newLink<-oldfirst

)

newLink.next=first;//newLink-->oldfirst

first=newLink;//first-->newLink

)

//insertatendoflist

publicvoidinsertLast(longvalue){

DoubleLinknewLink=newDoubleLink(value);

if(isEmpty()){//ifemptylist

first=newLink;//firstnewLink

}else{

last.next=newLink;//oldlast——>newLink

newLink.previous=last;//oldlastnev/Link

)

last=newLink;//newLink<--last

)

//deletefirstlink

publicDoubleLinkdeleteFirst(){

DoubleLinktemp=first;

if(first.next==null){//ifonlyoneitem

last=null;//null<--last

}else{

first.next.previous=null;//null<--oldnext

I

first=first.next;//first-->oldnext

returntemp;

}

//deletelastlink

publicDoubleLinkdeleteLast(){

DoubleLinktemp=last;

if(first.next==null){//ifonlyoneitem

first=null;//first-->null

}else{

last.previous.next=null;//oldpreviousnull

}

last=last.previous;//oldprevious<--last

returntemp;

//insertdatajustafterkey

publicbooleaninsertAfter(longkey,longdata){

DoubleLinkcurrent=first;//startatbeginning

while(current.data!=key){//untilmatchisfound

if(current.next==null){

returnfalse;

}else(

current=current.next;

)

}//findthepositionofkey

DoubleLinknev/Link=newDoubleLink(data);//makenewlink

if(current==last)(//iflastlink,

newLink.next=null;//newLink-->null

last=newLink;//newLink<-last

}else{//notlastlink.

newLink.next=current.next;//newLink-->oldnext

current.next.previous=newLink;//newLink<一一oldnext

)

current.next=newLink;//oldcurrent-->newLink

newLink.previous=current;//oldcurrent<-newLink

returntrue;

)

//deletelinkwithgivenkey

publicDoubleLinkdeleteKey(longkey){

DoubleLinkcurrent=first;//searchforexpectedlink

while(current.data!=key){

if(current.next==null){

returnnull;//didn'tfindit

}else{

current=current.next;//gotonextlink.

)

}//findit

if(current==first){//iffirstLink,changefirst

first=first.next;//first-->oldnext

}else{//otherwise,oldprevious-->oldnext

current.previous.next=current.next;}

if(current==last){//lastitem?

last=last.previous;//oldprevious<--last

}else{//notlast:oldprevious<——oldnext

current.next.previous=current.previous;

}

returncurrent;

publicvoiddisplayForward(){

System.out.print("first—>last:");

DoubleLinkcurrent=first;//startatbeginningoflist

while(current!=null){//untilendoflist

current.displayLink();

current=current.next;//movelisttonextlink

}

System.out.printin();

)

publicvoiddisplayBackward(){

System,out.print("lasts-->first:");

DoubleLinkcurrent=last;//startatendoflist

while(current!=null){//untilstartoflist

current.displayLink();

current=current.previous;//movelisttopreviouslink

)

System.out.printIn();

}

)

測試該類的主要方法:

publicvoidtestDoublyLinkedList()throwsException{

DoublyLinkedListlist=newDoublyLinkedList();

list.insertLast(24);

list.insertFirst(13);

list.insertFirst(b);

list.i