線性表的概念大家應(yīng)該還記得，鏈?zhǔn)奖硎蔷€性表的一個(gè)分類，當(dāng)然也具備線性表的所有特性了，只不過它的結(jié)構(gòu)方式特異而已，也就是和鏈子似的，和順序表的不同之處在于鏈?zhǔn)奖硪雽ο髴?yīng)用，就是其他語言中的指針，每個(gè)鏈子（我自己的說法）包含一個(gè)數(shù)據(jù)元素 (element) 和一個(gè)指針域 (next) ，這個(gè)鏈子就稱為節(jié)點(diǎn)，通俗的說有很多節(jié)點(diǎn)連接成的線性表就是鏈?zhǔn)奖恚鶕?jù)其結(jié)構(gòu)方式又可以分為單鏈表、單循環(huán)鏈表、雙向鏈表，還有一種不常用的仿真鏈表，所有的鏈表都有一個(gè)共同的特征，都是由節(jié)點(diǎn)組成，根據(jù)前一章的思想我們很自然的會(huì)想到要構(gòu)造一個(gè)節(jié)點(diǎn)類 Node.java ：

?

public class Node {

?/**

? * @author 張鈺

? */

?????? Object element;// 數(shù)據(jù)元素

??? Node next;

??? Node(Node nextval){

?????? ???? next=nextval;

??? }

?? Node(Object obj,Node nextval){

?????? ?element=obj;

?????? ?next=nextval;

?? }

public Object getElement() {

?????? return element;

}

public void setElement(Object obj) {

?????? element = obj;

}

public Node getNext() {

?????? return next;

}

public void setNext(Node nextval) {

?????? next = nextval;

}

public String toString(){

?????? return element.toString();

}

?? , 節(jié)點(diǎn)類的構(gòu)造就是為了實(shí)現(xiàn)鏈表的操作，鏈表最常見的是單鏈表，單鏈表就是其每個(gè)節(jié)點(diǎn)都只有一個(gè)指向直接后繼節(jié)點(diǎn)的指針，其中包括帶頭節(jié)點(diǎn)的和不帶頭節(jié)點(diǎn)的，根據(jù)單鏈表的結(jié)構(gòu)我們可以設(shè)計(jì)如下的類 LinList.java （注意和 java 中的 LinkList 不一樣， LinkList 是個(gè)線性結(jié)構(gòu)容器，提供線性表、堆棧、隊(duì)列等操作）：

/**

?* @author 張鈺

?*

?*/

public class LinList implements List {

?

?????? Node head;// 頭指針

?????? Node current;// 當(dāng)前節(jié)點(diǎn)位置

?????? int size;// 數(shù)據(jù)元素個(gè)數(shù)

?????? LinList(){

????????????? head=current=new Node(null);

?????? ??? size=0;

?????? }

?????? public void index(int i) throws Exception{ // 定位元素

? ??????????? if(i<-1||i>size-1){

? ?????????????????? throw new Exception(" 參數(shù)錯(cuò)誤 ");

? ??????????? }

? ??????????? if(i==-1) return;

? ??????????? current=head.next;

? ??????????? int j=0;

? ??????????? while((current!=null)&&j<i){

? ?????????????????? current=current.next;

? ?????????????????? j++;

? ??????????? }

?????? }

?????? public void insert(int i, Object obj) throws Exception {

????????????? // 插入

?????????? if(i<0||i>size){

??????? ?????? ???throw new Exception(" 參數(shù)錯(cuò)誤 ");

?????????? }

?????????? index(i-1);

?????????? current.setNext(new Node(obj,current.next));

?????????? size++;

?????? }

?

?

?????? public Object delete(int i) throws Exception {

????????????? // 刪除

????????????? if (size==0){

???????????????????? throw new Exception(" 鏈表已空無元素可刪除！ ");

????????????? }

????????????? if(i<0||i>size-1){

???????????????????? throw new Exception(" 參數(shù)錯(cuò)誤 ");

????????????? }

????????????? index(i-1);

????????????? Object obj=current.next.getElement();

????????????? current.setNext(current.next.next);

????????????? size--;

????????????? return obj;

?????? }

?

??????

?????? public Object getData(int i) throws Exception {

????????????? // 獲取元素

????????????? if(i<-1||i>size-1){

???????????????????? throw new Exception(" 參數(shù)錯(cuò)誤 ");

????????????? }

????????????? index(i);

????????????? return current.getElement();

?????? }

?

??????

?????? public int size() {

????????????? // 獲取元素個(gè)數(shù)

????????????? return size;

?????? }

?

?????? /* （非 Javadoc ）

?????? ?* @see List#isEmpty()

?????? ?*/

?????? public boolean isEmpty() {

????????????? // 判斷是否為空

????????????? return size==0;

?????? }

?

}

，設(shè)計(jì)說明：

(1) 構(gòu)造函數(shù)完成三件事：創(chuàng)建頭節(jié)點(diǎn)，使 head 和 current 均表示所創(chuàng)建的頭節(jié)點(diǎn)，置 s ize 為 0 ；

(2) 定位成員函數(shù) index(int i) 的實(shí)現(xiàn)，其設(shè)計(jì)方式是：用一個(gè)循環(huán)過程從頭開始計(jì)數(shù)尋找第 i 個(gè)節(jié)點(diǎn)；

順序表和單鏈表的比較：順序表和單鏈表的邏輯功能完全一樣，但是兩者的應(yīng)用背景以及不同情況下的使用效率略有不同，順序表的主要優(yōu)點(diǎn)就是支持隨機(jī)讀取，以及內(nèi)存空間利用效率高，順序表的主要特點(diǎn)就是需要給出數(shù)組的最大數(shù)據(jù)元素個(gè)數(shù)，而這通常很難準(zhǔn)確做到，另外，順序表的插入和刪除操作時(shí)需要移動(dòng)較多的數(shù)據(jù)元素，單鏈表的缺點(diǎn)就是每個(gè)節(jié)點(diǎn)中都有個(gè)指針，所以其空間利用率略低于順序表，單鏈表不支持隨機(jī)讀取。

單鏈表另一種常見的形勢就是循環(huán)單鏈表，其結(jié)構(gòu)特點(diǎn)就是鏈表中最后一個(gè)節(jié)點(diǎn)的指針不再是結(jié)束標(biāo)記，而是指向整個(gè)鏈表的第一個(gè)節(jié)點(diǎn)，從而使單鏈表形成一個(gè)環(huán)，，就是在構(gòu)造函數(shù)中增加 head.next=head ，在定位函數(shù) index(i) 中，把循環(huán)結(jié)束條件 current!=null 換成 current!=head ，這樣最后一個(gè)節(jié)點(diǎn)就循環(huán)到第一個(gè)了！鏈表最常見的一個(gè)應(yīng)用就是循環(huán)雙鏈表， java 中的 LinkedList 就是通過循環(huán)雙鏈表來實(shí)現(xiàn)的，其長度可以隨著數(shù)據(jù)元素的增減很容易的變化， LinkedList 提供了線性表、堆棧、隊(duì)列、雙端隊(duì)列等數(shù)據(jù)結(jié)構(gòu)所要求的全部成員函數(shù)，例如 addFirst() 和 removeFirst() 就是支持堆棧所要求的成員函數(shù)，這里就不過多講解了，回到循環(huán)雙鏈表，雙向鏈表中每個(gè)節(jié)點(diǎn)包括三個(gè)域： element 、 next 、 prior ，其中 element 是數(shù)據(jù)元素， next 是指向后繼節(jié)點(diǎn)的對象應(yīng)用， prior 是指向前驅(qū)節(jié)點(diǎn)的對象應(yīng)用，

?

設(shè) p 為第 i 個(gè)節(jié)點(diǎn)，則 p.next 為第 i+1 個(gè)節(jié)點(diǎn)， p.next.prior==p, 這就是雙向鏈表的方式，結(jié)合前面的內(nèi)容，雙向鏈表類的設(shè)計(jì)留給大家，有興趣的同學(xué)可以和我一起討論！