链表是一种常用的数据结构，每个节点通过链或者指针链接在一起，程序通过间接指针访问链表中的节点。
typedef struct Node {
//指向下一个节点的指针
struct Node *next;
int value;
}
单链表只可以单向遍历
单链表中插入：第一版
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0 typedef struct Node {
struct Node *next;
int value;
} LinkList; //假设链表从小到大排序
int linkInsert(LinkList * current, int value)
{
//保存前一个节点
LinkList *previous;
LinkList *new; //循环到合适的位置
while (current-> value < value) {
previous = current;
current = current->next;
} new = malloc(sizeof(LinkList));
if (new == NULL) {
return FALSE;
} new->value = value;
new->next = current;
previous->next = new; return TRUE;
}
当插入值到表头和表尾时，会出错，需要加上对特殊情况的判断，将传入的第一个参数由，指向链表头部节点的指针改为，指向 指向链表头部的指针的指针，这样就可以添加节点到链表的头部。
添加特殊情况处理的版本二：
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0 typedef struct Node {
struct Node *next;
int value;
} LinkList; //
int linkInsert(LinkList **rootPtr, int value)
{
//保存前一个节点
LinkList *previous;
LinkList *current;
LinkList *new; current = *rootPtr;
previous = NULL; //循环到达末尾和找到符合要求的节点
while (current != NULL && current-> value < value) {
previous = current;
current = current->next;
} new = malloc(sizeof(LinkList));
if (new == NULL) {
return FALSE;
} new->value = value;
new->next = current; //指向列表首页
if(previous == NULL){
*rootPtr = new;
}else{
previous -> next = new;
} return TRUE;
} int main()
{
LinkList third = {NULL, 4};
LinkList second = {&third, 2};
LinkList first = {&second, 1};
LinkList *head = &first;
LinkList **rootPtr = &head; linkInsert(rootPtr, 0); LinkList *pre = NULL;
LinkList *current = *rootPtr;
while(current != NULL){
printf("%d\t", current -> value);
pre = current;
current = current -> next;
} return 0;
}
优化：
版本二把一个节点插入到链表的起始位置当做一种特殊情况处理，对于新节点需要修改的是根节点，对于其他任何点，修改的是前一个节点的next字段，其实这个两个修改是相同的，即修改指向当前节点的指针，所以当我们移动到下一个节点时，需要保存的是指向下一个节点的next字段的指针，而不是保持指向下一个节点的指针
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0 typedef struct Node {
struct Node *next;
int value;
} LinkList; //
int linkInsert(LinkList **nextPtr, int value)
{
LinkList *current;
LinkList *new; //nextPtr为指向当前节点的next字段的指针
while ((current = *nextPtr) != NULL && value > current -> value) {
nextPtr = ¤t -> next;
} new = malloc(sizeof(LinkList));
if (new == NULL) {
return FALSE;
} new-> value = value;
new-> next = current;
//前一个节点指向最新的节点，即使是表头也可以正常处理
*nextPtr = new; return TRUE;
} int main()
{
LinkList third = {NULL, 4};
LinkList second = {&third, 2};
LinkList first = {&second, 1};
//把head当做next字段，指向第一个节点
LinkList *head = &first;
LinkList **nextPtr = &head; linkInsert(nextPtr, 3); LinkList *current = *nextPtr;
while(current != NULL){
printf("%d\t", current -> value);
current = current -> next;
} return 0;
}