单链表

/* 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);
link delete(link p);
void traverse(void (*visit)(link));
void destroy(void);
void push(link p);
link pop(void);

#endif

/* linkedlist.c */

#include <stdlib.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;
	return p;}
void free_node(link p)
{ 
	free(p);
}
link search(unsigned char key)
{ 
	link p;
	for (p = head; p; p = p->next)      ///遍历链表，活动节点先指向head,然后判断,然后next,最后如果p为NULL,则遍历结束！
		if (p->item == key) 
		return p; 
	return NULL;}

void insert(link p)
{ 
	p->next = head; 
	head = p;
}

link delete(link p)
{ 
	link prev; 
	if (p == head) { 
		head = p->next; 
		return p; }
	for (prev = head; prev; prev = prev->next)
		if (prev->next == p) 
		{ prev->next = p->next; 
		return p; } 
	return NULL;
}

void traverse(void (*visit)(link))
{ 
	link p;
	for (p = head; p; p = p->next) 
		visit(p);
}

void destroy(void)
{ 
	link q, p = head; 
	head = NULL; 
	while (p) { 
		q = p; 
		p = p->next;
		free(q); }
}

void push(link p)
{ 
	insert(p);
}

link pop(void)
{ 
	if (head == NULL) 
	return NULL; 
	else 
	return delete(head);
}

/* main.c */

#include <stdio.h>
#include "linkedlist.h"

void print_item(link p)
{ 
	printf("%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); 
	delete(p); 
	free_node(p); 
	traverse(print_item); 
	destroy(); 
	p = make_node(100); 
	push(p); 
	p = make_node(200); 
	push(p); 
	p = make_node(250); 
	push(p); 
	while (p = pop()) 
	{ 
		print_item(p); 
		free_node(p); }
	return 0;
}

删除一个节点的图示:

从上图可以看出，要摘除一个节点需要首先找到它的前趋然后才能做摘除操作，而在单链表中通过某个节点只能找到它的后继而不能找到它的前趋，所以删除操作要麻烦一些，需要从第一个节点开始依次查找要摘除的节点的前趋。delete操作也要处理一种特殊情况，如果要摘除的节点是链表的第一个节点，它是没有前趋的，这种情况要用特殊的代码处理，而不能和一般情况用同样的代码处理。这样很不爽，能不能把这种特殊情况转化为一般情况呢？可以把delete函数改成这样：

link delete(link p)
{ 
	link *pnext; 
	for (pnext = &head; *pnext; pnext = &(*pnext)->next) 
		if (*pnext == p) { 
		*pnext = p->next; 
		return p; } 
	return NULL;
}