C语言实现的单向链表

头文件 List.h

#ifndef _List_H

struct Node;
typedef struct Node * PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
// typedef void * ElementType;
typedef int ElementType;

List MakeEmpty(List L);
int IsEmpty(List L);
int IsLast(Position P, List L);
Position Find(ElementType X, List L);
Position FindPrevious(ElementType X, List L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);
Position Header(List L);
Position First(List L);
Position Advance(Position P);
ElementType Retrieve(Position P);

#endif


struct Node
{
	ElementType element;
	Position next;
};

List.c

#include "List.h"
#include <stdlib.h>
#include <assert.h>

int IsEmpty(List L) 
{
	return L->next == NULL;
}

int IsLast(Position P, List L)
{
	return P->next == NULL;
}


Position Find(ElementType X, List L)
{
	Position P = NULL;
	P = L->next;
	// if element is not primitive, should compare by user defined compare function
	while (P != NULL && P->element != X)
	{
		P = P->next;
	}

	return P;
}

void Delete(ElementType X, List L) 
{
	Position P, TmpCell;
	P = FindPrevious(X, L);

	if (!IsLast(P, L))
	{
		TmpCell = P->next;
		P->next = TmpCell->next;
		free(TmpCell);
		// if element is not primitive type, should free TmpCell->element first
	}

}


Position FindPrevious(ElementType X, List L)
{
	Position P;
	P = L;
	if (P->next != NULL && P->next->element != X)
	{
		P = P->next;
	}
	return P;
}

void Insert(ElementType X, List L, Position P)
{
	Position TmpCell;

	TmpCell = malloc(sizeof(struct Node));
	assert(TmpCell != NULL);
	TmpCell->element = X;
	TmpCell->next = P->next;
	P->next = TmpCell;
}

void Print(List L) {
	Position P;
	P = L;
	while(P->next != NULL)
	{
		printf("%p %d\n", L->next, L->next->element);
		P = P->next;
	}
}

参考内容:《数据结构与算法分析:C语言描述》 第3章 表、栈和队列