数据结构：程序加图示分析单链表的插入和删除操作
下图展示了单链表的基本结构：
head指针是链表的头指针，指向第一个节点，每个节点的next指针域指向下一个节点，最后一个节点的next指针域为NULL，在图中用0表示。
下面先来看程序（栈的链式存储实现，另外一个实现点这里）和对应的输出（注意输出前进行了链表反转（见《单链表反转》，否则程序后面的while循环输出的顺序是250，200，100），接着来分析程序：
/* linkedlist.h */
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
typedef struct node *link;
struct node
{
unsigned char item;
link next;
};
link make_node(unsigned char item);
void free_node(link p);
link search(unsigned char key);
void insert(link p);
void deletep(link p);
void traverse(void (*visit)(link));
void reverse(void);
void destroy(void);
void push(link p);
link pop(void);
#endif/* linkedlist.c */
#include <stdlib.h>
#include <stdio.h>
#include "linkedlist.h"
static link head = NULL;
link make_node(unsigned char item)
{
link p = malloc(sizeof(*p));
p->item = item;
p->next = NULL;
printf("make node from Item %d\n", item);
return p;
}
void free_node(link p)
{
printf("free node ...\n");
free(p);
}
link search(unsigned char key)
{
link p;
printf("search by key %d\n", key);
for (p = head; p; p = p->next)
if (p->item == key)
return p;
return NULL;
}
void insert(link p)
{
printf("insert node from head ...\n");
p->next = head;
head = p;
}
/*
void delete(link p)
{
link pre;
printf("delete node from ptr ...\n");
if (p == head) {
head = p->next;
return;
}
for (pre = head; pre; pre = pre->next)
if (pre->next == p) {
pre->next = p->next;
return;
}
}
*/
void deletep(link p)
{
link *pnext;
printf("delete node from ptr ...\n");
for (pnext = &head; *pnext; pnext = &(*pnext)->next)
if (*pnext == p)
{
*pnext = p->next;
return;
}
}
void traverse(void (*visit) (link))
{
link p;
printf("linkedlist traverse ...\n");
for (p = head; p; p = p->next)
visit(p);
}
void reverse(void)
{
link pnode = head;
link pprev = NULL;
printf("reverse linkedlist ...\n");
while (pnode != NULL)
{
// get the next node, and save it at pNext
link pnext = pnode->next;
// reverse the linkage between nodes
pnode->next = pprev;
// move forward on the the list
pprev = pnode;
pnode = pnext;
}
head = pprev;
}
void destroy(void)
{
link q, p = head;
printf("destory linkedlist ...\n");
head = NULL;
while (p)
{
q = p;
p = p->next;
free_node(q);
}
}
void push(link p)
{
printf("push item from head ...\n");
insert(p);
}
link pop(void)
{
if (head == NULL)
return NULL;
else
{
link p = head;
printf("pop item from head ...\n");
head = head->next;
return p;
}
}/*************************************************************************
> File Name: main.c
> Author: Simba
> Mail: dameng34@163.com
> Created Time: Fri 28 Dec 2012 01:22:24 PM CST
************************************************************************/
#include<stdio.h>
#include "linkedlist.h"
void print_item(link p)
{
printf("print item %d \n", p->item);
}
int main(void)
{
link p = make_node(10);
insert(p);
p = make_node(5);
insert(p);
p = make_node(90);
insert(p);
p = search(5);
deletep(p);
free_node(p);
traverse(print_item);
destroy();
printf("..................\n");
p = make_node(100);
push(p);
p = make_node(200);
push(p);
p = make_node(250);
push(p);
reverse();//链表反转
while ((p = pop()))
{
print_item(p);
free_node(p);
}
return 0;
}输出为：
分析：
在初始化时把头指针head初始化为NULL，表示空链表（不带头结点）。然后main函数调用make_node创建几个节点，分别调用insert插入到链表中。
链表的插入操作如下图：
正如上图所示，insert函数虽然简单，其中也隐含了一种特殊情况（Special Case）的处理，当head为NULL时，执行insert操作插入第一个节点之后，head指向第一个节点，而第一个节点的next指针域成为NULL，这很合理，因为它也是最后一个节点。所以空链表虽然是一种特殊情况，却不需要特殊的代码来处理，和一般情况用同样的代码处理即可，这样写出来的代码更简洁，但是在读代码时要想到可能存在的特殊情况。当然，insert函数传进来的参数p也可能有特殊情况，传进来的p可能是NULL，甚至是野指针，本章的函数代码都假定调用者的传进来的参数是合法的，不对参数做特别检查。事实上，对指针参数做检查是不现实的，如果传进来的是NULL还可以检查一下，如果传进来的是野指针，根本无法检查它指向的内存单元是不是合法的，C标准库的函数通常也不做这种检查，例如strcpy(p, NULL)就会引起段错误。
接下来main函数调用search在链表中查找某个节点，如果找到就返回指向该节点的指针，找不到就返回NULL。
search函数其实也隐含了对于空链表这种特殊情况的处理，如果是空链表则循环体一次都不执行，直接返回NULL。
然后main函数调用delete从链表中摘除用search找到的节点，最后调用free_node释放它的存储空间。
链表的删除操作如下图：
从上图可以看出，要摘除一个节点需要首先找到它的前趋然后才能做摘除操作，而在单链表中通过某个节点只能找到它的后继而不能找到它的前趋，所以删除操作要麻烦一些，需要从第一个节点开始依次查找要摘除的节点的前趋。delete操作也要处理一种特殊情况，如果要摘除的节点是链表的第一个节点，它是没有前趋的，这种情况要用特殊的代码处理，而不能和一般情况用同样的代码处理。这样很不爽，能不能把这种特殊情况转化为一般情况呢？可以把delete函数改成上述程序那样：
消除特殊情况的链表删除操作如下图：
定义一个指向指针的指针pnext，在for循环中pnext遍历的是指向链表中各节点的指针域，这样就把head指针和各节点的next指针统一起来了，可以在一个循环中处理。（其实增加一个头节点也可以消除delete的特殊情况《线性表的链式存储结构》） 然后main函数调用traverse函数遍历整个链表，调用destroy函数销毁整个链表。
参考：《linux c 编程一站式学习》