前面我們提供了四種方式實作的單連結清單，有帶頭結點的不帶頭結點的，而單連結清單的結構體定義也有兩種方式，那麼這些實作方式，到底有什麼差別呢，為什麼會出現這麼多種實作方式呢，下面我們就來細細體會
首先我們對比一下，單連結清單結構體
不同方式的單連結清單實作時，連結清單結點的實作是相同的，不同之處在于單連結清單結構體的實作上
typedef int elemtype; // 自定義資料類型
//typedef struct linklistnode* plinklistnode; // 連結清單結點指針域
// 連結清單結點資料域
typedef struct linklistnode
{
elemtype m_data; // 資料域
struct linklistnode *m_next; // 指針域
}linklistnode;
typedef struct linklist
linklistnode *m_head; // 連結清單頭結點
int m_length; // 單連結清單資料結點個數指針域
}linklist;
// 帶頭結點的單連結清單
typedef struct linklistnode linklist;
// 不帶頭結點的單項連結清單
typedef struct linklistnode* linklist;
對于一個單連結清單來說，查找其長度的時，需要從前往後周遊一遍單連結清單，是以時間複雜度是o(n)，為了能更快的擷取其長度，我們設計了帶length辨別的單連結清單結構體，這對于經常擷取連結清單長度時，效率是十分客觀的，
而我們又發現同樣時不帶length辨別的單連結清單結構體，定義的方式卻又出現了細微的差别。這個又是為什麼呢？、
這個差別的根本就在于就是帶頭結點的單連結清單和不帶頭結點的單連結清單的差別了。
單連結清單的結點插入和删除，其實就是修改其前驅結點的next指針域的指向，我們學c語言的時候知道，無論什麼時候在函數中修改一個變量的值，需要傳入這個變量的指針作為參數，具體的參見下面的示例程式
#include <stdio.h>
#include <stdlib.h>
// 函數中修改一個變量的值
void modify1(int value); // 變量作為參數
void modify2(int *value); // 變量指針作為參數
int main(void)
int value = 0;
modify1(value);
printf("value = %d after func\n\n", value); // modify failed
modify2(&value);
printf("value = %d after func\n\n", value); // modify success
return exit_success;
}
// 變量作為參數
void modify1(int value)
value = 10;
printf("value = %d in %s\n", value, __func__);
// 變量指針作為參數
void modify2(int *value)
*value = 10;
printf("value = %d in %s\n", *value, __func__);
那麼單連結清單中删除删除元素時，需要修改在函數中修改指針的指向（尤其在插入首元時，需要修改頭指針的指向），是以需要使用指針的指針（即二重指針）
為了保證我們實作的代碼的一緻性，我們所有參數的傳遞均使用linklist *list，作為參數傳遞到函數中
這樣在帶length辨別的單連結清單結構體中，修改指針的指向時其實使用的已經是
linklistnode
*pnode = list->m_head;// 傳入的是linlist *, 而修改的是*list中的linklistnode *m_head可見已經是二重指針
那麼是作為二重指針，是可以修改掉m_head的指向的(我們可可以這樣了解，傳入的是linklist* list即變量的指針，那麼畢竟可以修改掉變量*list的值，變量*list作為結構體，他的資料就是*m_head和m_length，即可以修改掉指針的指向)
typedef struct
int *value;
int length
}list;
int glovalue1 = 0;
int glovalue2 = 10; // 全局變量
void modify1(list list); // 變量作為參數
void modify2(list *list); // 變量的指針作為參數
list list = {&glovalue1, 0};
printf("&glovalue1 = %p, &glovalue = %p\n", &glovalue1, &glovalue2);
printf("value = %d, addr = %p, length = %d after func\n\n", *(list.value), list.value, list.length);
modify1(list);
printf("value = %d, addr = %p, length = %d after modify1\n\n", *(list.value), list.value, list.length);
modify2(&list);
printf("value = %d, addr = %p, length = %d after modify2\n\n", *(list.value), list.value, list.length);
void modify1(list list)
list.value = &glovalue2; // 修改指針的值(即指針的指向) failed
list.length = 10; // failed
printf("value = %d, addr = %p, length = %d in %s\n", *(list.value), list.value, list.length, __func__);
void modify2(list *list)
list->value = &glovalue2; // 修改指針的值(即指針的指向) success
list->length = 10; // success
printf("value = %d, addr = %p, length = %d in %s\n", *(list->value), list->value, list->length, __func__);
那麼現在問題就清楚了，要想修改一個指針的指向，需要傳入指針的指針作為參數，那麼我們在插入删除的過程中，在那裡修改了指針的指向呢？
其實歸根結底修改了兩個地方，我們參見不帶頭結點的單連結清單實作方式2中插入函數的實作
①是修改結點本身的指向，需要傳入二重指針
// 不帶頭結點的單連結清單插入首元時，需要修改頭指針的指向
(*list) = newnode; // 此時修改指針本身的指向需要傳入linklistnode **
// 不帶頭結點的單項連結清單聲明
//函數聲明
linklistnode* insertnode(linklist *list, // linklist * == linklistnode**
int position,
elemtype data)
②是修改結點的指針域的指向，傳入指向結點的指針即可
// 将newnode插入pnode之後時，需要修改newnode和pnode指針域的指向
newnode->m_next = pnode->m_next; // 此時隻需要傳入linklistnode *即可, 因為指針域m_next是node的資料成員, 已經是個指針成員變量
pnode->m_next = newnode; // 傳入linklistnode *, m_next就成為一個指針的指針
// 函數聲明
linklistnode *addnode(linklist *list,
linklistnode *prevnode, // 傳入linklistnode *, 即可修改prevnode->m_next = @@@@@
elemtype data)
現在問題明了了，但是為什麼兩種方式定義的單連結清單結構體卻不一樣呢
這就是不帶頭結點的單連結清單和帶頭結點的單連結清單實作地方的差別了
我們很容易發現帶頭結點的單連結清單實作起來要比不帶頭結點的單連結清單要簡單，這個是為什麼呢
繼續接着上面的講，插入和删除時，要修改其前驅指針的指向，特别的插入和删除第一個元素（即首元結點）時，我們需要更改頭指針的指向，很明顯頭指針是沒有前驅的，這樣我們實作起來的時候
對于非頭結點，我們直接找到其前驅，然後修改其前驅結點的指針域的指向就好了(傳入指向結點的指針即可)
對于頭結點，沒有前驅結點，我們需要特殊判斷，而直接修改頭指針本身的指向(傳入指向頭結點的指針的指針)
怎麼規避這個問題呢，那就在連結清單頭的位置添加一個頭結點，初始化時候将頭結點建立好，這樣我們即使插入首元結點，首元結點也是有一個前驅（即頭結點的），這樣我們修改頭指針，也就變成了修改頭結點的指針域的指向，這樣我們傳參和插入删除的實作就統一了。實作起來也簡單
好了不帶頭結點和帶頭結點我麼明了了，接着來回答上面那個問題，為什麼，單連結清單的結構體不一樣呢。。
帶頭結點的時候，我們傳入參數其實已經不需要傳入二重指針了，統一傳入指向連結清單結點的指針即可，是以用下面的實作即可
而不帶頭結點的時候，實作起來插入删除時候，是需要傳入指向頭結點的指針的指針，那麼還用linklistnode作為list，傳入參數時，就需要list **list了，這樣我們幾種實作方式的函數定義就不統一了，這種編碼方式不是我們喜歡的，是以用
無獨有偶，上面帶頭節點的單連結清單也是可以用typedef struct linklistnode* linklist;，隻是傳參時候用list list即可，函數命名也不統一了，而若是将參數統一為list *list,那麼裡面代碼實作的時候，全部用(*list)表示指向頭結點的指針，實作起來不容易了解，是以我們選用了typedef struct linklistnode linklist
轉載：http://blog.csdn.net/gatieme/article/details/42673493