第三章 鏈結串列 3-1　 單向鏈結串列 3-2 環狀鏈結串列 3-3 雙向鏈結串列

單向鏈結串列 「單向鏈結串列」中第一個節點是「串列指標首」，指向最後一個節點的鏈結欄位設為Null表示它是「串列指標尾」，不指向任何地方。 例如串列A={a，b，c，d，x}，其單向串列資料結構如下

java語言中要模擬鏈結串列中的節點，必須宣告如下的Node類別： class Node { int data; Node next; public Node(int data) //節點宣告的建構子 this.data=data; this.next=null; }

單向鏈結串列的建立 使用java語言的鏈結串列處理以下學生的成績問題。學生成績處理會有以下欄位。 座號 姓名 成績 01 黃小華 85 02 方小源 95 03 林大暉 68 04 孫阿毛 72 05 王小明 79

必須宣告節點的資料型態，讓每一個節點包含一筆資料，並且包含指向下一筆資料的指標，使所有資料能被串在一起而形成一個串列結構，如下圖：

類別宣告了三個方法： 方法名稱 功能說明 public boolean isEmpty() 用來判斷目前的鏈結串列是否為空串列 public void print() 用來將目前的鏈結串列內容列印出來 public void insert(int data,String names,int np) 用來將指定的節點資料插入至目前的鏈結串列

範例程式：ch03_01.java

運作原理詳細說明如下： 步驟1 建立新節點。 步驟2 將鏈結串列的first及last指標欄指向newNode。 步驟3 建立另一個新節點。

步驟4 將兩個節點串起來。 last.next=newNode; last=newNode; 步驟5 依序完成如下圖所示的鏈結串列結構。

串列首 只要有串列首存在，就可以對整個串列進行走訪、加入及刪除節點等動作。而之前建立的節點若沒有串起來就會形成無人管理的節點，並一直佔用記憶體空間。 在建立串列時必須有一串列指標指向串列首，並且除非必要否則不可移動串列首指標。

單向鏈結串列的節點刪除 刪除串列的第一個節點： 只要把串列首指標指向第二個節點即可。 if(first.data==delNode.data) first=first.next;

刪除串列內的中間節點： 將刪除節點的前一個節點的指標，指向欲刪除節點的下一個節點即可，如下段程式碼所示： newNode=first; tmp=first; while(newNode.data!=delNode.data) { tmp=newNode; newNode=newNode.next; } tmp.next=delNode.next;

刪除串列後的最後一個節點： 只要指向最後一個節點的指標，直接指向null即可。 if(last.data==delNode.data) { newNode=first; while(newNode.next!=last) newNode=newNode.next; newNode.next=last.next; last=newNode; }

範例程式：ch03_02.java

單向鏈結串列的節點插入 1.在串列的第一節點插入節點 只需把新節點的指標指向串列首，再把串列首移到新節點上即可。

2.在串列的最後一個節點後面插入節點： 把串列的最後一個節點的指標指向新節點，新節點再指向null即可。

3.在串列的中間位置插入節點： 如果插入的節點是在X與Y之間，只要將X節點的指標指向新節點，新節點的指標指向Y節點即可。

單向鏈結串列的反轉功能 鏈結串列中的節點特性是知道下一個節點的位置，可是卻無從得知它的上一個節點位置，不過如果要將串列反轉，則必須使用三個指標變數。如下圖所示：

範例程式：ch03_03.java

單向鏈結串列的連結 對於兩個或以上鏈結串列的連結(Concatenation)，其實作法也很容易；只要將串列的首尾相連即可。如下圖所示：

多項式的串列表示法 使用陣列表示法經常會出現以下的困擾： 多項式內容變動時，對陣列結構的影響相當大，演算法處理不易。 由於陣列是靜態資料結構，所以事先必須尋找一塊連續夠大的記憶體，容形成空間的浪費。

多項式相加演算法範例 A=3X3+4X+2 B=6X3+8X2+6X+9

範例程式：ch03_04.java

範例 3.2.1 假設一鏈結串列的節點結構如下： 來表示多項式XAYBZC之項。 (a)請繪出多項式X6-6XY5+5Y6的鏈結串列圖。 (c)繪出多項式X6-3X5-4X4+2X3+3X+5的鏈結串列圖。

範例3.2.2 請設計一串列資料結構表示 P(x,y,z)=x10y3z10+2x8y3z2+3x8y2z2+x4y4z+6x3y4z+2yz

環狀鏈結串列 環狀鏈結串的定義 環狀鏈結串列的節點插入 環狀鏈結串列的節點刪除 環狀鏈結串列的結合 環狀鏈結串列表示稀疏矩陣

環狀鏈結串的定義 建立的過程與單向鏈結串列相似，唯一的不同點是必須要將最後一個節點指向第一個節點。如下圖所示：

環狀鏈結串列的節點插入 1.直接將新節點插在第一個節點前成為串列首。圖形如下： 步驟 將新節點的指標指向原串列首。 找到原串列的最後一個節點，並將指標指向新節點。 將串列首指向新節點。

2.將新節點I插在任意節點X之後，圖形如下： 步驟 將新節點I的指標指向X節點的下一個節點。 將X節點的指標指向I節點。

環狀鏈結串列的節點刪除 1.刪除環狀鏈結串列的第一個節點。圖形如下： 步驟 將串列首head移到下一個節點。 將最後一個節點的指標移到新的串列首。

2.刪除環狀鏈結串列的中間節點。圖形如下： 步驟 請先找到所要刪除節點X的前一個節點。 將X節點的前一個節點的指標指向節點X的下一個節點。

環狀鏈結串列的結合 單向鏈結串列的連結只需改變一個指標就可以了，如下圖所示：

範例程式：StuLinkedList.java

環狀鏈結串列表示稀疏矩陣 環狀鏈結串列也可以用來表現稀疏矩陣，而且簡單方便許多。它的資料結構如下： Row: 以i表示非零項元素所在列數 Col: 以j表示非零項元素所在行數 Down: 為指向同一行中下一個非零項元素的指標 Right: 為指向同一列中下一個非零項元素的指標 Value: 表示此非零項的值

範例 3.3.1 稀疏矩陣(sparse matrix)可以鏈結串列(linked list)來表示，請用鏈結串列表下列矩陣： 範例 3.3.2 用陣列法和鏈結串列法表示稀疏矩陣有何優缺點，又如果用鏈結串列表示時，回收到AVL串列(可用空間串列)，時間複雜度為多少？

雙向鏈結串列 雙向鏈結串列可以改善這兩個缺點，因為它的基本結構和單向鏈結串列類似，至少有一個欄位存放資料，只是它有兩個欄位存放指標，其中一個指標指向後面的節點，另一個則指向前面節點。

雙向鏈結串列的定義 雙向鏈結串列的資料結構，可以定義如下： 每個節點具有三個欄位，中間為資料欄位。左右各有兩個鏈結欄位，分別為LLINK及RLINK。 通常加上一個串列首，此串列不存任何資料，其左邊鏈結欄指向串列最後一個節點，而右邊鏈結指向第一個節點。 假設ptr為一指向此串列上任一節點的鏈結，則有： ptr=RLINK(LLINK(ptr))=LLINK(RLINK(ptr))

雙向鏈結串列的節點加入 1.將新節點加入此串列的第一個節點前，如下圖： 步驟 將新節點的右鏈結(RLINK)指向原串列的第一個節點。 將原串列第一個節點的左鏈結(LLINK)指向新節點。 將原串列的串列首指標head指向新節點，且新節點的左鏈結指向NULL。

2.將新節點加入此串列的最後一個節點之後。如下圖： 步驟 將原串列的最後一個節點的右鏈結指向新節點。 將新節點的左鏈結指向原串列的最後一個節點，並將新節點的右鏈結指向NULL。

3.將新節點加入到ptr節點之後，如下圖 步驟 將ptr節點的右鏈結指向新節點。 將新節點的左鏈結指向ptr節點。

雙向鏈結串列節點刪除 1.刪除串列的第一個節點。如下圖： 步驟 將串列首指標head指到原串列的第二個節點。 將新的串列首指標指向NULL。

2.刪除此串列的最後一個節點。如下圖： 步驟 將原串列最後一個節點之前一個節點的右鏈結指向NULL即可。

3.刪除串列中間的ptr節點。如下圖： 步驟 將ptr節點的前一個節點右鏈結指向ptr節點的下一個節點。

範例3.3.1 試比較雙向鏈結串列與單向鏈結串列間的優缺點。