文本主要内容：
連結清單結構
單連結清單代碼實作
單連結清單的效率分析
一、連結清單結構： （實體存儲結構上不連續，邏輯上連續；大小不固定）
概念：
鍊式存儲結構是基于指針實作的。我們把一個資料元素和一個指針稱為結點。
資料域：存數資料元素資訊的域。
指針域：存儲直接後繼位置的域。
鍊式存儲結構是用指針把互相直接關聯的結點（即直接前驅結點或直接後繼結點）連結起來。鍊式存儲結構的線性表稱為連結清單。
連結清單類型：
根據連結清單的構造方式的不同可以分為：
單向連結清單
單向循環連結清單
雙向循環連結清單
二、單連結清單：
連結清單的每個結點中隻包含一個指針域，叫做單連結清單（即構成連結清單的每個結點隻有一個指向直接後繼結點的指針）
單連結清單中每個結點的結構：
1、頭指針和頭結點：
單連結清單有帶頭結點結構和不帶頭結點結構兩種。
“連結清單中第一個結點的存儲位置叫做頭指針”，如果連結清單有頭結點，那麼頭指針就是指向頭結點的指針。 頭指針所指的不存放資料元素的第一個結點稱作頭結點（頭結點指向首元結點）。頭結點的資料域一般不放資料（當然有些情況下也可存放連結清單的長度、用做監視哨等） 存放第一個資料元素的結點稱作第一個資料元素結點，或稱首元結點。
如下圖所示：
不帶頭結點的單連結清單如下：
帶頭結點的單連結清單如下圖：
關于頭指針和頭結點的概念區分，可以參考如下部落格：
<a href="http://blog.csdn.net/hitwhylz/article/details/12305021" target="_blank">http://blog.csdn.net/hitwhylz/article/details/12305021</a>
2、不帶頭結點的單連結清單的插入操作：
上圖中，是不帶頭結點的單連結清單的插入操作。如果我們在非第一個結點前進行插入操作，隻需要a(i-1)的指針域指向s，然後将s的指針域指向a(i)就行了；如果我們在第一個結點前進行插入操作，頭指針head就要等于新插入結點s，這和在非第一個資料元素結點前插入結點時的情況不同。另外，還有一些不同情況需要考慮。
是以，算法對這兩種情況就要分别設計實作方法。
3、帶頭結點的單連結清單的插入操作：（操作統一，推薦）
上圖中，如果采用帶頭結點的單連結清單結構，算法實作時，p指向頭結點，改變的是p指針的next指針的值（改變頭結點的指針域），而頭指針head的值不變。
是以，算法實作方法比較簡單，其操作與對其它結點的操作統一。
問題1：頭結點的好處：
頭結點即在連結清單的首元結點之前附設的一個結點，該結點的資料域中不存儲線性表的資料元素，其作用是為了對連結清單進行操作時，可以對空表、非空表的情況以及對首元結點進行統一處理，程式設計更友善。
問題2：如何表示空表：
無頭結點時，當頭指針的值為空時表示空表；
有頭結點時，當頭結點的指針域為空時表示空表。
問題3：頭結點的資料域内裝的是什麼？
頭結點的資料域可以為空，也可存放線性表長度等附加資訊，但此結點不能計傳入連結表長度值。
三、單項連結清單的代碼實作：
1、結點類：
單連結清單是由一個一個結點組成的，是以，要設計單連結清單類，必須先設計結點類。結點類的成員變量有兩個：一個是資料元素，另一個是表示下一個結點的對象引用（即指針）。
步驟如下：
（1）頭結點的構造（設定指針域即可） （2）非頭結點的構造 （3）獲得目前結點的指針域 （4）獲得目前結點資料域的值 （5）設定目前結點的指針域 （6）設定目前結點資料域的值
注：類似于get和set方法，成員變量是資料域和指針域。
代碼實作：
(1)list.java:（連結清單本身也是線性表，隻不過實體存儲上不連續）
(2)node.java:結點類
2、單連結清單類：
單連結清單類的成員變量至少要有兩個：一個是頭指針，另一個是單連結清單中的資料元素個數。但是，如果再增加一個表示單連結清單目前結點位置的成員變量，則有些成員函數的設計将更加友善。
(3)linklist.java:單向連結清單類(核心代碼)
3、測試類：（單連結清單的應用）
使用單連結清單建立一個線性表，依次輸入十個0-99之間的随機數，删除第5個元素，列印輸出該線性表。
(4)test.java:
運作效果：
四、開發可用的連結清單：
對于連結清單實作，node類是整個操作的關鍵，但是首先來研究一下之前程式的問題：node是一個單獨的類，那麼這樣的類是可以被使用者直接使用的，但是這個類由使用者直接去使用，沒有任何的意義，即：node這個類有用，但是不能讓使用者去用，隻能讓linklist類去調用，内部類node中完成。
于是，我們需要把node類定義為内部類，并且在node類中去完成addnode和delnote等操作。使用内部類的最大好處是可以和外部類進行私有操作的互相通路。
注：内部類通路的特點是：内部類可以直接通路外部類的成員，包括私有；外部類要通路内部類的成員，必須先建立對象。
1、增加資料：
public boolean add(資料 對象)
（1）linklist.java:（核心代碼）
代碼解釋：
14行：如果我們第一次調用add方法，那根結點肯定是空的，此時add的是根節點。
當繼續調用add方法時，此時是往根節點後面添加資料，需要用到遞歸（42行），這個遞歸需要在内部類中去完成。遞歸這段代碼需要去反複了解。
（2）linklistdemo.java:
2、增加多個資料：
public boolean addall(資料 對象 [] )
上面的操作是每次增加了一個對象，那麼如果現在要求增加多個對象呢，例如：增加對象數組。可以采用循環數組的方式，每次都調用add()方法。
在上面的（1）linklist.java中加入如下代碼：
3、統計資料個數：
public int size()
在一個連結清單之中，會儲存多個資料（每一個資料都被封裝為node類對象），那麼要想取得這些儲存元素的個數，可以增加一個size()方法完成。
具體做法如下：
在上面的（1）linklist.java中增加一個統計的屬性count：
當使用者每一次調用add()方法增加新資料的時候應該做出統計：（下方第18行代碼）
而size()方法就是簡單的将count這個變量的内容傳回：
4、判斷是否是空連結清單：
public boolean isempty()
所謂的空連結清單指的是連結清單之中不儲存任何的資料，實際上這個null可以通過兩種方式判斷：一種判斷連結清單的根節點是否為null，另外一個是判斷儲存元素的個數是否為0。
在linklist.java中添加如下代碼：
5、查找資料是否存在：
public boolean contains(資料 對象)
現在如果要想查詢某個資料是否存在，那麼基本的操作原理：逐個盤查，盤查的具體實作還是應該交給node類去處理，但是在盤查之前必須有一個前提：有資料存在。
在linklist.java中添加查詢的操作：
緊接着，在node類之中，完成具體的查詢，查詢的流程：
判斷目前節點的内容是否滿足于查詢内容，如果滿足傳回true；
如果目前節點的内容不滿足，則向後繼續查，如果已經沒有後續節點了，則傳回false。
6、删除資料：
public boolean remove(資料 對象)
在linklist.java中加入如下代碼：
注意第2代碼中，我們是假設删除的這個string字元串是唯一的，不然就沒法删除了。
删除時，我們需要從根節點開始判斷，如果根節點是需要删除的節點，那就直接删除，此時下一個節點變成了根節點。
然後，在node類中做節點的删除：
7、輸出所有節點：
然後，在node類中做節點的輸出：
8、取出全部資料：
public 資料 [] toarray()
對于連結清單的這種資料結構，最為關鍵的是兩個操作：删除、取得全部資料。
在linklist類之中需要定義一個操作數組的腳标：
在linklist類中定義傳回數組，必須以屬性的形式出現，隻有這樣，node類才可以通路這個數組并進行操作：
在linklist類之中增加toarray()的方法：
修改node類的操作，增加toarraynode()方法：
不過，按照以上的方式進行開發，每一次調用toarray()方法，都要重複的進行資料的周遊，如果在資料沒有修改的情況下，這種做法是一種非常差的做法，最好的做法是增加一個修改标記，如果發現資料增加了或删除的話，表示要重新周遊資料。
然後，我們修改linklist類中的toarray()方法：（其他代碼保持不變）
9、根據索引位置取得資料：
public 資料 get(int index)
在一個連結清單之中會有多個節點儲存資料，現在要求可以取得指定節點位置上的資料。但是在進行這一操作的過程之中，有一個小問題：如果要取得資料的索引超過了資料的儲存個數，那麼是無法取得的。
在linklist類之中，增加一個get()方法：
在node類之中配置getnode()方法：
10、清空連結清單：
public void clear()
所有的連結清單被root拽着，這個時候如果root為null，那麼後面的資料都會斷開，就表示都成了垃圾：
總結：
上面的10條方法中，linklist的完整代碼如下：
四、單連結清單的效率分析：
在單連結清單的任何位置上插入資料元素的機率相等時，在單連結清單中插入一個資料元素時比較資料元素的平均次數為：
删除單連結清單的一個資料元素時比較資料元素的平均次數為：
是以，單連結清單插入和删除操作的時間複雜度均為o（n）。另外，單連結清單讀取資料元素操作的時間複雜度也為o（n）。
2、順序表和單連結清單的比較：
順序表：
優點：主要優點是支援随機讀取，以及記憶體空間利用效率高；
缺點：主要缺點是需要預先給出數組的最大資料元素個數，而這通常很難準确作到。當實際的資料元素個數超過了預先給出的個數，會發生異常。另外，順序表插入和删除操作時需要移動較多的資料元素。
單連結清單：
優點：主要優點是不需要預先給出資料元素的最大個數。另外，單連結清單插入和删除操作時不需要移動資料元素；
缺點：主要缺點是每個結點中要有一個指針，是以單連結清單的空間使用率略低于順序表的。另外，單連結清單不支援随機讀取，單連結清單取資料元素操作的時間複雜度為o（n）；而順序表支援随機讀取，順序表取資料元素操作的時間複雜度為o（1）。