单链表（易懂实用版）

开始学习数据结构时，还是很有必要自己手动撸一遍来实现各个功能的。

目录

增

删 

创建单链表

前插法

后插法

初始化

表的长度

改

查

打印表中元素

测试一下

---

这次记的是单链表，链表相对与顺序表有个很明显的优势是不会存在表的位置满的情况，随时可以向表中添加元素，且由于巧妙地使用指针，所以存储方式灵活，不易造成内存的浪费；当然不足之处是链表的一些操作总是从头结点开始依次往后寻找某个结点，若是元素较多的情况下，算法所需要的时间就比较久。

---

下面讲几个重要的点：

首先定义一个结点，包含一个数据域和指向下一结点的指针域。其别名为LNode或是指针型LinkList *.

typedef int ElemType;
typedef struct node{
	ElemType data;
	struct node *next;
}LNode,*LinkList;

---

链表的表头是一个特殊的结点即头结点(L)，头结点是在首元(a1)结点之前附设的一个结点，其指针域指向首元结点。头结点的数据域可以不存储任何信息，也可存储与数据元素类型相同的其他附加信息。则非空表特点L->next=a1;空表特点L->next=NULL;

---

增

 链表的插入主要思路在于借助一个结点q（跟图示不同），要存的数据赋值给q，再将s的指针域指向待插入位置的后一个结点，最后将待插入位置的前一个结点指向q，那么待插入位置上新的结点即为q。

Status ListInsert(LinkList L, int i, ElemType e){			//第i个位置插入结点e,1<=i<=len+1
	LNode *p, *q;
	p=L;
	q=(LNode*)malloc(sizeof(LNode));
	q->next=NULL;
	int j=0;
	if(i<1 || i>ListLength(L)+1){
		printf("插入位置不符合实际情况！");
		return ERROR;
	}
	while(p && j<i-1){
		p=p->next;
		j++;
	}//p移动到i-1个位置
	q->data=e;
	q->next=p->next;
	p->next=q;		//i-1指向q,q指向i+1 
	return OK;
}

---

删 

链表的删除主要思路在于将待删除位置的前一个结点指针域更改为指向待删除位置的后一个结点（即跳过该位置的结点），最后别忘对该位置结点free()一下释放内存。 

                                             

Status ListDelete(LinkList L, int i, ElemType *e){			//删除第i个位置结点e,1<=i<=len,数据保存在e里 
	LNode *p = L, *q;
	int j=0;
	if(i<1 || i>ListLength(L)){
		printf("删除位置不符合实际情况！");
		return ERROR;
	}
	while(p && j<i-1){
		p=p->next;
		j++;
	}//p移动到i-1个位置 
	q=p->next;		//q在i位置 
	*e=q->data;
	p->next=q->next;	//i-1指向i+1 
	free(q);
	return OK;
}

---

创建单链表

前插法

前插法主要思路在于头结点总是指向每次新增的结点，换个角度理解就是将新结点插入到第1个位置，于是后面的要做的就是一个插入操作。

 

LinkList CreateList_R(LinkList L, int n){			//正位序输入n个元素的值，建立带表头结点的单链表
	int i;
	LNode *p, *r;		//中间结点p 
	L=(LinkList)malloc(sizeof(LNode));
	if(!L){
	printf("内存分配失败！");
	return NULL;
	}
	else{
	L->next=NULL;
	r=L;
	for(i=0;i<n;i++){
		p=(LNode *)malloc(sizeof(LNode));
		printf("请输入第%d个数据（正序）:\n", i+1);
		scanf("%d", &p->data);
		p->next=NULL;
		r->next=p; 
		r=p;
	}
	printf("创建成功！\n");
	return L;
	}
}

注意这里是将L创建好后返回，若不想返回值可将参数修改为LinkList *L(等效于LNode **)后，再是对(*L)的一些操作，下面后插法、初始化等同理。

---

后插法

后插法主要思路是定义尾结点r(最后一个元素)，使r总是指向每次新增的结点，也就是将新增结点连接到r后，再更新r指向新增结点。

LinkList CreateList_R(LinkList L, int n){			//正位序输入n个元素的值，建立带表头结点的单链表
	int i;
	LNode *p, *r;		//中间结点p 
	L=(LinkList)malloc(sizeof(LNode));
	if(!L){
	printf("内存分配失败！");
	return NULL;
	}
	else{
	L->next=NULL;
	r=L;
	for(i=0;i<n;i++){
		p=(LNode *)malloc(sizeof(LNode));
		printf("请输入第%d个数据（正序）:\n", i+1);
		scanf("%d", &p->data);
		p->next=NULL;
		r->next=p; 
		r=p;
	}
	printf("创建成功！\n");
	return L;
	}
}

---

其他操作：

初始化

LinkList InitList(LinkList L){
	L=(LinkList )malloc(sizeof(LNode));
	if(!L){
	printf("内存分配失败！");
	return NULL;
	}
	else{
	L->next=NULL;		//头结点指针域置空 
	return L;
	}	
}

---

表的长度

int ListLength(LinkList L){
	LNode *p = L;		//引入动态结点p从头结点开始 
	int len=0;
	while(p->next){
		p=p->next;
		len++;
	}
	return len;
}

---

改

Status AlterElem(LinkList L, int i, ElemType e){			//修改第i个位置结点数据,1<=i<=len 
	LNode *p = L;
	int j=0;
	if(i<1 || i>ListLength(L)){
		printf("修改位置不符合实际情况！");
		return ERROR;
	}
	while(p && j<i-1){
		p=p->next;
		j++;
	}//p移动到i-1个位置 
	p=p->next;		//p在i位置 
	p->data=e;
	return OK;
}

---

查

int LocateElem(LinkList L, ElemType e){			//查找e是否位于链表里,若找到就返回其位置 
	LNode *p;
	p = L->next;
	int j=1;
	while(p){
		if(p->data == e){
			return j;
		}
		p=p->next;
		j++;
	}//p移动到i-1个位置 
	return ERROR;
}

---

打印表中元素

void Display(LinkList L){
	printf("表中元素：");
	LinkList p;
	p=L->next;		//p从第1个结点开始 
	while(p){
		printf("%-3d", p->data);
		p=p->next;
	}
	putchar('\n');
} 

---

测试一下

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;
typedef struct node{
	ElemType data;
	struct node *next;
}LNode,*LinkList;
 
//初始化单链表
LinkList InitList(LinkList L){
	L=(LinkList )malloc(sizeof(LNode));
	if(!L){
	printf("内存分配失败！");
	return NULL;
	}
	else{
	L->next=NULL;		//头结点指针域置空 
	return L;
	}	
}
 
//前插法创建单链表 
LinkList CreateList_H(LinkList L, int n){			//逆位序输入n个元素的值，建立带表头结点的单链表
	int i;
	LNode *p;		//中间结点p 
	L=(LinkList )malloc(sizeof(LNode));
	if(!L){
	printf("内存分配失败！");
	return NULL;
	}
	else{
	L->next=NULL;
	for(i=0;i<n;i++){
		p=(LinkList)malloc(sizeof(LNode));
		printf("请输入第%d个数据（逆序）:\n", i+1);
		scanf("%d", &p->data);
		p->next=L->next;
		L->next=p;		//新元素与表头连接 
	}
	printf("创建成功！\n");
	return L;
	}
}
 
//后插法创建单链表 
LinkList CreateList_R(LinkList L, int n){			//正位序输入n个元素的值，建立带表头结点的单链表
	int i;
	LNode *p, *r;		//中间结点p 
	L=(LinkList)malloc(sizeof(LNode));
	if(!L){
	printf("内存分配失败！");
	return NULL;
	}
	else{
	L->next=NULL;
	r=L;
	for(i=0;i<n;i++){
		p=(LNode *)malloc(sizeof(LNode));
		printf("请输入第%d个数据（正序）:\n", i+1);
		scanf("%d", &p->data);
		p->next=NULL;
		r->next=p; 
		r=p;
	}
	printf("创建成功！\n");
	return L;
	}
}
 
//求表长 
int ListLength(LinkList L){
	LNode *p = L;		//引入动态结点p从头结点开始 
	int len=0;
	while(p->next){
		p=p->next;
		len++;
	}
	return len;
}
 
//增
Status ListInsert(LinkList L, int i, ElemType e){			//第i个位置插入结点e,1<=i<=len+1
	LNode *p, *q;
	p=L;
	q=(LNode*)malloc(sizeof(LNode));
	q->next=NULL;
	int j=0;
	if(i<1 || i>ListLength(L)+1){
		printf("插入位置不符合实际情况！");
		return ERROR;
	}
	while(p && j<i-1){
		p=p->next;
		j++;
	}//p移动到i-1个位置
	q->data=e;
	q->next=p->next;
	p->next=q;		//i-1指向q,q指向i+1 
	return OK;
}
 
//删
Status ListDelete(LinkList L, int i, ElemType *e){			//删除第i个位置结点e,1<=i<=len,数据保存在e里 
	LNode *p = L, *q;
	int j=0;
	if(i<1 || i>ListLength(L)){
		printf("删除位置不符合实际情况！");
		return ERROR;
	}
	while(p && j<i-1){
		p=p->next;
		j++;
	}//p移动到i-1个位置 
	q=p->next;		//q在i位置 
	*e=q->data;
	p->next=q->next;	//i-1指向i+1 
	free(q);
	return OK;
}
 
//改
Status AlterElem(LinkList L, int i, ElemType e){			//修改第i个位置结点数据,1<=i<=len 
	LNode *p = L;
	int j=0;
	if(i<1 || i>ListLength(L)){
		printf("修改位置不符合实际情况！");
		return ERROR;
	}
	while(p && j<i-1){
		p=p->next;
		j++;
	}//p移动到i-1个位置 
	p=p->next;		//p在i位置 
	p->data=e;
	return OK;
}
 
//查
int LocateElem(LinkList L, ElemType e){			//查找e是否位于链表里,若找到就返回其位置 
	LNode *p;
	p = L->next;
	int j=1;
	while(p){
		if(p->data == e){
			return j;
		}
		p=p->next;
		j++;
	}//p移动到i-1个位置 
	return ERROR;
} 
 
//遍历（打印）表
void Display(LinkList L){
	printf("表中元素：");
	LinkList p;
	p=L->next;		//p从第1个结点开始 
	while(p){
		printf("%-3d", p->data);
		p=p->next;
	}
	putchar('\n');
} 
 
void main(){
	LinkList L;
	int n, e, pos;
	char ch;
	printf("正序还是逆序输入元素？（R/H）\n");
	ch=getchar();
	printf("输入创建链表的元素个数：\n");
	scanf("%d", &n);
	if(ch=='H')	L=CreateList_H(L,n);
	else		L=CreateList_R(L,n);
	if(!L)		exit(0);		//链表未创建成功直接退出 
	Display(L);
	printf("输入要插入的位置和数据（空格隔开）：\n");
	scanf("%d %d", &pos, &e);
	ListInsert(L,pos,e);
	Display(L);
	printf("输入要删除的位置\n");
	scanf("%d", &pos);
	ListDelete(L,pos,&e);
	Display(L);
	printf("表长为%d", ListLength(L));
	printf("输入要修改的位置和数据（空格隔开）：\n");
	scanf("%d %d", &pos, &e);
	AlterElem(L,pos,e);
	Display(L);
	printf("要查找的元素：\n");
	scanf("%d", &e);
	if(LocateElem(L,e)){
		printf("在第%d个位置", LocateElem(L,e));
	}
	else{
		printf("未找到该元素！");
	}
}

得到结果