線性表的概念大家應該還記得，鏈式表是線性表的一個分類，當然也具備線性表的所有特性了，只不過它的結構方式特異而已，也就是和鏈子似的，和順序表的不同之處在于鏈式表引入對象應用，就是其他語言中的指針，每個鏈子（我自己的說法）包含一個數據元素
(element)
和一個指針域
(next)
，這個鏈子就稱為節點，通俗的說有很多節點連接成的線性表就是鏈式表，根據其結構方式又可以分為單鏈表、單循環鏈表、雙向鏈表，還有一種不常用的仿真鏈表，所有的鏈表都有一個共同的特征，都是由節點組成，根據前一章的思想我們很自然的會想到要構造一個節點類
Node.java
：
?
public class Node {
?/**
? * @author
張鈺
? */
?????? Object element;//
數據元素
??? 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();
}
?? ,
節點類的構造就是為了實現鏈表的操作，鏈表最常見的是單鏈表，單鏈表就是其每個節點都只有一個指向直接后繼節點的指針，其中包括帶頭節點的和不帶頭節點的，根據單鏈表的結構我們可以設計如下的類
LinList.java
（注意和
java
中的
LinkList
不一樣，
LinkList
是個線性結構容器，提供線性表、堆棧、隊列等操作）：
/**
?* @author
張鈺
?*
?*/
public class LinList implements List {
?
?????? Node head;//
頭指針
?????? Node current;//
當前節點位置
?????? int size;//
數據元素個數
?????? LinList(){
????????????? head=current=new Node(null);
??????
??? size=0;
?????? }
?????? public void index(int i) throws Exception{ //
定位元素
?
??????????? if(i<-1||i>size-1){
?
?????????????????? throw new Exception("
參數錯誤
");
?
??????????? }
?
??????????? 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("
參數錯誤
");
?????????? }
?????????? 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("
參數錯誤
");
????????????? }
????????????? 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("
參數錯誤
");
????????????? }
????????????? index(i);
????????????? return current.getElement();
?????? }
?
??????
?????? public int size() {
????????????? //
獲取元素個數
????????????? return size;
?????? }
?
?????? /*
（非
Javadoc
）
??????
?* @see List#isEmpty()
??????
?*/
?????? public boolean isEmpty() {
????????????? //
判斷是否為空
????????????? return size==0;
?????? }
?
}
，設計說明：
(1)
構造函數完成三件事：創建頭節點，使
head
和
current
均表示所創建的頭節點，置
s ize
為
0
；
(2)
定位成員函數
index(int i)
的實現，其設計方式是：用一個循環過程從頭開始計數尋找第
i
個節點；
順序表和單鏈表的比較：順序表和單鏈表的邏輯功能完全一樣，但是兩者的應用背景以及不同情況下的使用效率略有不同，順序表的主要優點就是支持隨機讀取，以及內存空間利用效率高，順序表的主要特點就是需要給出數組的最大數據元素個數，而這通常很難準確做到，另外，順序表的插入和刪除操作時需要移動較多的數據元素，單鏈表的缺點就是每個節點中都有個指針，所以其空間利用率略低于順序表，單鏈表不支持隨機讀取。
單鏈表另一種常見的形勢就是循環單鏈表，其結構特點就是鏈表中最后一個節點的指針不再是結束標記，而是指向整個鏈表的第一個節點，從而使單鏈表形成一個環，，就是在構造函數中增加
head.next=head
，在定位函數
index(i)
中，把循環結束條件
current!=null
換成
current!=head
，這樣最后一個節點就循環到第一個了！鏈表最常見的一個應用就是循環雙鏈表，
java
中的
LinkedList
就是通過循環雙鏈表來實現的，其長度可以隨著數據元素的增減很容易的變化，
LinkedList
提供了線性表、堆棧、隊列、雙端隊列等數據結構所要求的全部成員函數，例如
addFirst()
和
removeFirst()
就是支持堆棧所要求的成員函數，這里就不過多講解了，回到循環雙鏈表，雙向鏈表中每個節點包括三個域：
element
、
next
、
prior
，其中
element
是數據元素，
next
是指向后繼節點的對象應用，
prior
是指向前驅節點的對象應用，
?
設
p
為第
i
個節點，則
p.next
為第
i+1
個節點，
p.next.prior==p,
這就是雙向鏈表的方式，結合前面的內容，雙向鏈表類的設計留給大家，有興趣的同學可以和我一起討論！
最后還有仿真鏈表，鏈式儲存結構中，實現元素之間的關系靠的是指針，但是也可以用數組來構造仿真鏈表，方法是在數祖中增加一個（或兩個）
int
類型的變量域，這些變量用來表示后一個或前一個元素在數組中的下標，這就是仿真鏈表，其應用不是很多，這里就不多介紹，有興趣的同學可以研究，下一講：堆棧和隊列！