順序線性表的優點：友善存取（随機的），特點是實體位置和邏輯為主都是連續的（相鄰）。但是也有不足，比如；前面的插入和删除算法，需要移動大量元素，浪費時間，那麼鍊式線性表 (簡稱連結清單) 就能解決這個問題。
一般連結清單的存儲方法
一組實體位置任意的存儲單元來存放線性表的資料元素，當然實體位置可以連續，也可以不連續，或者離散的配置設定到記憶體中的任意位置上都是可以的。故連結清單的邏輯順序和實體順序不一定一樣。
因為，連結清單的邏輯關系和實體關系沒有必然聯系，那麼表示資料元素之間的邏輯映象就要使用指針，每一個存儲資料元素的邏輯單元叫結點（node）。
結點裡有兩個部分，前面存儲資料元素内容，叫資料域，後面部分存儲結點的直接後繼在記憶體的實體位置，叫指針域。那麼就可以實作用指針（也叫鍊）把若幹個結點的存儲映象連結為表，就是鍊式線性表。
上面開始介紹的是最簡單的連結清單，因為結點裡隻有一個指針域，也就是俗稱的單連結清單（也叫線性連結清單）。
單連結清單可以由一個叫頭指針的東東唯一确定，這個指針指向了連結清單（也就是直接指向第一個結點）。是以單連結清單可以用頭指針的名字來命名。且最後一個結點指針指向null。
連結清單類别
1、實作的角度：動态連結清單，靜态連結清單（類似順序表的動态和靜态存儲）
2、連結方式的角度：單連結清單，雙向連結清單，循環連結清單
單連結清單
單連結清單的頭結點
一般是使用單連結清單的頭指針指向連結清單的第一個結點，有的人還這樣做，在第一個結點之前再加一個結點（不儲存任何資料資訊，隻儲存第一個結點的位址，有時也儲存一些表的附加資訊，如表長等），叫頭結點（頭結點是頭結點，第一個結點是第一個結點）。那麼此時，頭指針指向了頭結點。并且有無頭結點都是可以的。連結清單還是那個連結清單，隻不過表達有差異。
那麼問題來了！為什麼還要使用頭結點？
作用是對連結清單進行操作時，可以對空表、非空表的情況以及對首元結點進行統一處理，程式設計更友善。
描述動态單連結清單
有兩種做法，一種是傳統的動态連結清單結構，暨隻定義結點的存儲結構，使用4個位元組的指針變量表示線性表。還有一種是直接采用結構體變量（類似順序表）來表示線性表。
顧名思義，肯定是第二種方法比較友善。
先看傳統存儲動态單連結清單結構的操作
view code
c變量的随用随定義，可以确定c99之後新增加的，和c++一樣，貌似一些編譯器還不支援
算法執行時間和value有關，時間複雜度為0（n），n表長
//時間複雜度0（n），n為表長
時間複雜度，雖然沒有移動任何元素，還是0（n），因為最壞時核心語句頻度為n（表長）
為什麼不是p？
//判斷表為非空，因為不止一次删除操作！總會删空，則p還是指向的頭結點！如果依然是while（p &&……），表空時，按道理函數不應該再執行核心語句，提前判斷出錯，但此時卻還要執行循環體，循環結束才能到if（！p），而使用while(p->next && ……），表空就直接跳出循環，到if語句，提示錯誤。這是删除算法總是需要注意的細節，插入算法則是如果記憶體有限，或者是順序的表，或者靜态連結清單，那麼總是要注意存儲空間滿足大小的問題
插入算法時間複雜度分析：0(n)，最壞情況下頻度是n
/插入和删除算法，還有一個思路，就是既然需要每次都找前驅，那麼為什麼不弄兩個指針呢？一個指向目前位置，一個緊随其後指向前，個人其實感覺是脫褲子放屁……
時間複雜度依然是o(n)
時間複雜度：必然是o（n），插入了n個元素
連結清單和順序表存儲結構不同，動态,整個可用記憶體空間可以被多個連結清單共享，每個連結清單無需事先配置設定存儲容量，由系統應要求自動申請。建立連結清單是動态的過程。
//如a b c d，依次頭插法（頭插 總是在第一個結點前插入，暨插入的結點總是作為第一個結點）到空連結清單裡，那麼完成之後是
//d c b a
下面是正序的尾插法，如圖
這樣操作，輸入的序列和輸出的序列是正序的，且時間複雜度為o（n）
算法時間複雜度，和頭插法比較的話，還是o（n）,其實順序表的有序歸并也是這個時間複雜度o（a.length + b.length），但是連結清單的尾插法歸并沒有移動元素，隻是解除和重建連結的操作，也沒有額外開辟記憶體空間。空間複雜度不同。
函數内部有動态配置設定記憶體的情形，應該把參數設定為指向指針的指針，當然還有别的方法，我習慣而已。
記得說：值傳遞函數，是把實參的一個拷貝送到函數體，函數體修改的是那份傳入的拷貝，不是函數跑到main裡去給它修改。
且形參和傳入的拷貝，還有函數體内的變量（棧中配置設定的記憶體），都是是代碼塊内的自動存儲類型的變量，也就是局部變量，函數執行完畢，變量自動銷毀，改變就不起作用。
指針形參可以改變實參，但是如果是針對函數内動态配置設定了記憶體的情況，把堆配置設定的記憶體位址賦給了指針參數，改變的是指針指向的内容，而指針變量（形參）本身的記憶體位址沒有改變，故根本句不會成功修改實參。
指向指針的指針，存放的是指向實參記憶體位址a的指針的位址b，修改b位址，改變了b指向的内容，而b指向的内容恰恰就是一級指針a本身，一級指針a的修改，使得實參被改變，對實參（指針變量c），需要取出指針c自己的的位址，傳入函數。達到間接修改實參的目的。
測試
scanf函數的特點是接受單詞，而不是字元串，字元串一般是gets函數，單個字元接收是getchar函數，因為scanf函數遇到空白字元（tab，空格，回車，制表符等）就不再讀取輸入，那字元串怎麼能友善輸入？
但是輸入隊列裡如果還有字元，那麼會留到緩存内，需要在定義裡使用getchar函數來消除回車帶來的影響。
辛苦的勞動，轉載請注明出處，謝謝……
http://www.cnblogs.com/kubixuesheng/p/4057063.html