數(shù)據(jù)結(jié)構(gòu)(Java)-第2章線性表-鏈表

//在不確定數(shù)據(jù)域數(shù)值的情況下，采用泛型定義publicclassNode<E>{Edata;//數(shù)據(jù)域Node<E>next;//指針域}datanext單個(gè)節(jié)點(diǎn)的表示方法//在不確定數(shù)據(jù)域數(shù)值的情況下，采用泛型定義publicclassLinkList<E>{ Node<E>head;Node<E>p;}datanext單個(gè)節(jié)點(diǎn)的表示方法datanextdatanextheadnull建立鏈表datanextheadNULLnewnode//說明head頭指針newnode新節(jié)點(diǎn)指針newnode.data數(shù)據(jù)域表示方式newnode.next指針域表示方式NULLnewnode無后繼節(jié)點(diǎn)headNULLPNULL初始狀態(tài),無節(jié)點(diǎn)

head=NULL;P=NULL;publicLinkList(){head=null;p=null;}初始化datanextheadNULLpnewode建立鏈表publicvoidaddhead(Node<E>e){Node<E>newhead=newNode<E>();newhead.data=e.data;newhead.next=e.next;head=newhead;p=head;p.next=null;}遍歷輸出publicvoidprintlist(){ p=head; if(head==null) {System.out.println("這是一個(gè)空鏈表"); }while(p!=null)

{System.out.println(p.data); p=p.next; }}在鏈表后面插入節(jié)點(diǎn)datanextheadNULLnewnodedatanextp注意：添加節(jié)點(diǎn)后，鏈表的長度+1publicvoidaddlist(Node<E>e){Node<E>newnode=newNode<E>();newnode.data=e.data;newnode.next=e.next;p.next=newnode;p=p.next;p.next=null;}publicstaticvoidmain(String[]args){ScannerAA=newScanner(System.in);LinkList<Integer>obj1=newLinkList<Integer>();Node<Integer>tt=newNode<Integer>();System.out.print("請輸入第1數(shù):");tt.data=AA.nextInt();obj1.addhead(tt);Node<Integer>tb=newNode<Integer>();intk;inti=2;do{System.out.print("請輸入第"+i+"數(shù):");k=AA.nextInt();if(k==0)break;tb.data=k;obj1.addlist(tb);i++;}while(true);此段代碼:表示連續(xù)建立多個(gè)節(jié)點(diǎn)，知道輸入的數(shù)字為0，就不再建立新的節(jié)點(diǎn)obj1.printlist();System.out.print("請輸入第插入節(jié)點(diǎn)的值");tb.data=AA.nextInt();obj1.addnode(tb,2);obj1.printlist();System.out.print("請輸入首節(jié)點(diǎn)插入的值");tb.data=AA.nextInt();obj1.addH(tb);obj1.printlist();}單鏈表的插入（1）只定節(jié)點(diǎn)后插入新的節(jié)點(diǎn)圖示

s.next=p.next;p.next=s;(2)前插結(jié)點(diǎn)

（2）只定節(jié)點(diǎn)前插入新的節(jié)點(diǎn)圖示

s.next=p;q.next=s;單鏈表的刪除

q.next=p.next;p.next=null;單鏈表的按值查找操作 }

單鏈表操作的效率分析

（1）單鏈表是一種順序存取結(jié)構(gòu)，不是隨機(jī)存取結(jié)構(gòu)。要訪問任意一個(gè)結(jié)點(diǎn)ai（1≤i≤n），必須從頭指針head開始，沿著“鏈”的方向逐個(gè)查找，執(zhí)行i-1次p=p.getNext()操作，平均進(jìn)行n/2次。（2）單鏈表的插入和刪除操作，必須知道其直接前驅(qū)結(jié)點(diǎn)。（3）與順序表相比，單鏈表中結(jié)點(diǎn)的存儲(chǔ)空間是動(dòng)態(tài)申請和釋放的，不需要預(yù)先分配。同時(shí)，對單鏈表執(zhí)行插入和刪除操作時(shí)，只需要改變相關(guān)結(jié)點(diǎn)的“鏈”，不需要移動(dòng)結(jié)點(diǎn)。因此，單鏈表在一定程度上可以提高運(yùn)行效率和存儲(chǔ)空間的利用率。循環(huán)鏈表

head是單鏈表的頭指針，設(shè)rear是單鏈表的尾指針。將單鏈表中最后一個(gè)結(jié)點(diǎn)的指針域指回鏈表的頭結(jié)點(diǎn)，即rear.next=head，則整個(gè)單鏈表頭尾相連形成了一個(gè)環(huán)，就構(gòu)成了循環(huán)單鏈表。

雙向鏈表

在單鏈表中，從任意一個(gè)結(jié)點(diǎn)出發(fā)都能通