摘自《C和指针》中关于单链表的描述

在单链表中，每个节点包含一个指向链表下一个节点的指针。链表最后一个节点的指针字段的值为NULL，提示链表后面不再有其它节点。在你找到链表的第一个节点后，指针就可以带你访问剩下的所有节点。为了记住链表的起始位置，可以使用一个根指针（root pointer）。根指针指向链表的第一个节点。注意根指针只是一个指针，它不包含任何数据。

下面是一张单链表的图：

假设链表是以升序进行排练的。首先定义链表的数据结构和一个打印链表的辅助函数。

sll_node.h

#ifndef _SLL_NODE
#define _SLL_NODE

typedef struct NODE{
	struct NODE *link;
	int value;
}Node;

#endif

#include "sll_node.h"
#include <stdio.h>
#include <stdlib.h>

void printSll(Node * root){
	while(root!=NULL){
		printf("%d ",root->value);
		root=root->link;
	}
}

下面是insert1.c的代码

#include <stdlib.h>
#include <stdio.h>
#include "sll_node.h"

#define FALSE 0
#define TRUE 1

/*插入到一个有序的单链表，函数的参数是一个指向链表的第一个节点的指针以及需要插入的值*/
int sll_insert(Node *current,int new_value){

	Node * previous;
	Node *new;

	/*寻找正确的插入值，方法是按顺序访问链表，直到到达其值大于或等于新插入值的节点*/
	while(current->value<new_value){
		previous=current;
		current=current->link;
	}

	/*为新节点分配内存，并把新值存储到新节点中，如果内存分配失败，函数返回FALSE*/
	new=(Node *)malloc(sizeof(Node));
	if(new==NULL)
		return FALSE;
	new->value=http://www.mamicode.com/new_value;>这段代码在插入大于5小于15的数值时不会有问题，但是插入小于5或者大于15的数字时会出错，表现就是程序直接崩溃。因为这段代码的逻辑对于插入的节点在根节点之前或者在尾节点之后这两种情况的处理并不正确。
插入值大于15时，在while循环内会出错，此时current为NULL，对它进行解引用操作会失败，修改方法是将while循环改成：
while(current!=NULL&&current->value<new_value)
当插入值小于5时，此次while循环会直接跳出，一次都不执行。此时就只剩下这两行代码修改节点之前的关系:
new->link=current;
previous->link=new;
注意到这两行代码其实都是无效的了，第一行代码虽然把新插入的几点指向了根节点，但是它并没有修改调用函数外面的根节点的指针，因为此时它是根节点了，第二行代码就更错了，此时previous还没有初始化。
它的解决办法就是把一个指向root节点的指针作为参数传递给函数。然后，使用解引用，函数不仅可以获得root（指向链表第一个节点的指针，也就是根指针）的值，还可以向它存储一个新的指针值。
下面是修改后的代码：
insert2.c
#include <stdio.h>
#include <stdlib.h>
#include "sll_node.h"

#define FALSE 0;
#define TRUE 1

/*插入到一个有序的单链表，函数的参数是一个指向链表根指针的指针，以及一个需要插入的新值*/
int sll_insert(Node **rootp,int new_value){
	Node *current;
	Node *previous;
	Node *new;

	/* 得到指向第一个节点的指针*/
	current=*rootp;
	previous=NULL;

	/*寻找正确的插入位置，方法是按序访问链表，知道到达一个大于或等于新值的节点*/
	while(current!=NULL&&current->value<new_value){
		previous=current;
		current=current->link;
	}

	/*为新节点分配内存，并把新值存储到新节点中，如果内存分配失败，函数返回FALSE*/
	new=(Node *)malloc(sizeof(Node));
	if(new==NULL){
		return FALSE;
	}
	new->value=http://www.mamicode.com/new_value;>
上面的代码中main函数中链表的创建和insert1.c中链表的创建是一样的，但是传递给函数的参数在insert1.c是root，也就是链表中第一个节点的地址，在insert2.c中传递给函数的地址是&root，就是这个地址的地址，理解了C中函数是传值调用这个观点后，很容易明白传递&root的好处，就是可以在函数内修改root的内容，使root始终指向链表的第一个节点。
对上面的main.c稍作修改，打印出插入几个值后root变量的值看看就很容易理解了:
int main(){
	Node * root;
	Node first,second,third;
	first.value=http://www.mamicode.com/5;>
上面往创建的链表里分别依次插入了3,7,20,这三个数，创建完链表或者每次插入一个新的数据都都打印出root变量的地址（也就是传递给sll_insert函数的参数），root变量的值，还有链表的数据。在输出结果之前可以先猜想，四次输出中&root的值应该是不变的，因为传递给函数的只是实参的副本（c中传值调用），第一次输出的root是一个值，第二次输出的root和第一次不同，因为插入了3，此时值为3的那个节点才是根节点，第三次和第四次输出的root值和第二次相同，因为插入7和插入20不会更改指向根节点的指针的值。
下面是输出的结果：与上面的猜想是一致的。


上面的代码其实已经是一种正确的处理方法了，但是其实还有一种更优的方法。上面的代码把第一个节点插入到链表的起始位置作为一种特殊的情况在处理，因为此时修改的是根指针。对于任何其它节点，对指针的修改实际上修改的是前一个节点的link字段。这两个看上去不同的操作实际上是一样的。
消除特殊情况的关键在于：必须认识到，链表中的每一个节点都有一个指向它的指针。对于第一个节点，这个指针是根指针；对于其它节点，这个指针是前一个节点的link字段。重点在于每个节点都有一个指针指向它。至于该指针是不是位于一个节点内部则无关紧要。
再次观察这个链表，为了弄清这个概念。这是第一个节点和指向它的指针。


如果新值插入到第一个节点之前，这个指针就必须进行修改。
下面是2个节点和指向它的指针：

如果新值需要插入到第2个节点之前，那么这个指针必须进行修改。注意我们只考虑指向这个节点的指针，至于那个节点包含这个指针则无关紧要。对于链表中的其它节点，都可以应用这个模式。
现在看看修改之后的函数（当它开始执行时）。羡慕显示了第1条赋值语句之后各个变量的情况：

我们拥有一个指向当前节点的指针(即current指针)，以及一个“指向当前节点的link字段的”指针（即rootp指针），后面半句话感觉有点歧义，意思就是指向当前节点的指针的指针，从图中很容易看出它的含义。除此之外，我们就不需要别的了！如果当前节点的值大于新值，那么rootp指针就会告诉我们那个link字段必须进行修改，以便让新节点链接到链表中。如果在链表其它位置的插入也可以用同样的方式进行表示，就不存在前面提到的特殊情况了。其关键在于我们看到的指针/节点关系。
当移动到下一个节点时，我们保存一个“指向”下一个节点的link字段的“指针，而不是保存一个指向前一个节点的指针。很容易画出描述这种情况的图：

注意，这里rootp并不是指向节点本身，而是指向节点内部的link字段。这是简化插入函数的关键所在，但我们必须能够取得当前节点的link字段的地址，使用&current->link就可以达到目的。rootp参数现在称为linkp，因为它现在指向的是不同的link字段，而不仅仅是根指针。我们不再需要previous指针，因为linkp指针可以负责找寻需要修改的link字段。insert2.c中用于处理特殊情况的代码也不见了，因为我们始终拥有一个指向需要修改的link字段的指针，我们用一种和修改节点的link字段完全相同的方式修改root变量。
下面是执行代码：
insert3.c
#include <stdio.h>
#include <stdlib.h>
#include "sll_node.h"

#define FALSE 0
#define TRUE 1

int sll_insert(register Node ** linkp,int new_value){
	register Node *current;
	register Node *new;

	/*寻找正确的插入位置，方法是按序访问链表，知道到达一个其值大于或等于新值的节点*/
	while((current=*linkp)!=NULL&¤t->value<new_value){
		linkp=&current->link;
	}

	/*为新节点分配内存，并把新值存储到新节点中，如果内存分配失败，函数返回FALSE*/
	new=(Node *)malloc(sizeof(Node));
	if(new==NULL)
		return FALSE;
	new->value=http://www.mamicode.com/new_value;>




单链表操作