目录

1、链表的定义

2、链表的分类

1、不带头结点的单向不循环链表

2、带头结点的单向不循环链表

3、不带头结点单向循环链表

4、带头结点的单向循环链表

5、不带头结点的双向不循环链表

6、带头结点的双向不循环链表

7、不带头结点的双向循环链表

8、带头节点的双向循环链表

链表的结构

1、结构

2、创造一个节点

3、初始化链表

4、求链表长度

5、打印链表

6、查找元素

根据数值查找

根据下标查找

7、插入

根据下标插入

头插

尾插

8、删除

根据下标删除

头删

尾删

9、销毁

前言：

上次介绍了一种数据的存储结构——顺序表，但是他会有缺陷：当我们要插入元素和申请空间的时候一般情况下后扩容原来的2倍，但是不一定每一个空间都装数据，这样会造成空间的浪费，而且进行插入和删除的时候，对应实现的接口的时间复杂的位O（N），效率第，因此一些大佬有发明了一个链表。下面是单链表的介绍。

1、链表的定义

链表（Linked List）是一种线性表，由一系列节点（Node）组成，每个节点包含数据域和指针域，节点之间通过指针链接在一起。

2、链表的分类

链表的分类有很多种，如下：

主要看他三个方面：是否单向，是否带头结点，是否循环，这样就有了八种链表。

注意：节点（现代）和结点（偏传统）这两种叫法都可以。

下面是链表的具体情况，在介绍链表的具体情况之前先区分一下头结点和头指针

头结点（也称为哨兵位）：他和普通的节点在结构上是一样的，也分为数值域和指针域，只不过他的数值域不存储有效数据，然后他的指针域指向的是第一个有效节点的地址。

头指针：他仅仅是一个结构体类型的指针用于存储节点的地址，他是链表最开始的部分。

1、不带头结点的单向不循环链表

2、带头结点的单向不循环链表

3、不带头结点单向循环链表

4、带头结点的单向循环链表

5、不带头结点的双向不循环链表

6、带头结点的双向不循环链表

7、不带头结点的双向循环链表

8、带头节点的双向循环链表

链表的结构

下面是对有头结点的不循环单链表的介绍

1、结构

//List.h #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> typedef int LDataType; //定义数值域存放的是int的类型的变量，利用LDataType代替，方便对数值域的类型进行修改 typedef struct ListNode { LDataType data; // 存储数据 struct ListNode* next; // 存放后继结点地址， }LNode, *LinkList;

这里对LDataType进行重命名，以至于对链表数值的存储方便修改，更具有普适性。

定义结构体变量，需要注意这里的struct ListNode* next不能写成LNode*或者是*LinkList，因为这里next是在重命名之前的。

还要知道这里有一个typedef和结构体的知识，

struct ListNode==LNode; struct ListNode*==*LinkList

2、创造一个节点

List.h //创造一个新的节点，节点的数值域是data LNode* BuyListNode(int data); //List.c //创造一个新的节点，节点的数值域是data LNode* BuyListNode(int data) { LNode* newNode = (LNode*)malloc(sizeof(LNode*)); if (newNode == NULL) { printf("malloc创建空间失败"); exit(-1); } newNode->data = data; newNode->next = NULL; return newNode; }

这里创造完节点之后要判空，而且要把节点的next置为空，防止野指针，还要返回节点的地址是为了能让链表之间的节点连起来。

3、初始化链表

//List.h LNode* ListInit(); //List.c LNode* ListInit() { LNode* node = BuyListNode(-1);//头结点,初始化完了之后只有他一个 return node; }

这里初始化的是有头结点的链表，随便给他一个-1的值

4、求链表长度

int ListSize(LNode* L) { assert(L);//L是头结点 int size = 0; LNode* cur = L->next;//第一个有效节点 while (cur)//从第一个有效节点开始，这样也是遍历有头结点单链表的代码 { size++; cur = cur->next; } return size; }

这里涉及到一个遍历链表的循环，cur是第一个有效节点0开始。

5、打印链表

//List.h void ListPrint(LNode* L)； //List.c //打印链表 void ListPrint(LNode* L) { assert(L); LNode* cur = L->next;//第一个有效节点,这里的L是哨兵位头结点，数值域不放东西 while (cur) { printf("%d->",cur->data); cur = cur->next; } printf("NULL\n"); }

6、查找元素

根据数值查找

//获取第一个节点为x的链表，并返回其地址 LNode* ListLocateElem(LNode* L, LDataType x) { assert(L); LNode* cur = L->next; while (cur)//遍历，一个一个比较 { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }

通过一个一个的比对查找

根据下标查找

//获取下标是i的节点，并且返回其地址 LNode* ListGetElem(LNode* L, int i) { assert(L); assert(i >= 0); int j = 0; LNode* iNode = L->next; while (iNode&&j<i) { j++; iNode = iNode->next; } return iNode; }

7、插入

根据下标插入

//在下标为i的节点处插入一个节点 LNode* ListInsert(LNode* L, int i) { assert(L); assert(i >= 0); int j = -1;//从头结点开始，不然头插不了 LNode* i_1Node = L; while (i_1Node && j < i-1) { i_1Node = i_1Node->next; j++; } assert(i_1Node);//先判断是否符合是空的 LNode* newNode = BuyListNode(30);//再来创造新的节点，如果顺序打乱可能创造了节点没有连接，形成野指针 newNode->next= i_1Node->next; i_1Node->next = newNode; return newNode; }

链表的插入很容易错，因为进行头插的时候要从头结点开始遍历而不是从第一个有效节点开始，不然覆盖不了所有节点。

还有当插入链表的时候，一定要先修改新节点的next,也就是从后面开始修改，再将i_1Node的next和newNode进行连接，防止找不到后面的节点。

头插

//头插,数值是x void ListPushFront(LNode* L, LDataType x) { assert(L); LNode* newNode = BuyListNode(x); newNode->next = L->next; L->next=newNode; }

尾插

//尾插,数值是x void ListPushBack(LNode* L, LDataType x) { assert(L); LNode* newNode = BuyListNode(x); newNode->next = NULL; // 情况1：空链表 if (L->next == NULL) { L->next = newNode; return; } // 情况2：非空链表 LNode* cur = L->next; while (cur->next != NULL) { cur = cur->next; } cur->next = newNode; }

这里要判断一下是否是空表

8、删除

根据下标删除

//在下标为i的节点处删除一个节点,返回该节点处的值 LDataType ListDelete(LNode* L, int i) { assert(L); assert(i>=0); int j = -1; LNode* i_1Node = L; while (i_1Node && j < i-1 ) { i_1Node = i_1Node->next; j++; } assert(i_1Node&& i_1Node->next); LNode* iNode = i_1Node->next; LDataType x = iNode->data; i_1Node->next = iNode->next; free(iNode); return x; }

这里同理的要注意一下头指针，在进行删除第一个有效节点的时候，同样从头结点开始

头删

//头删，并且返回删除的值 LDataType ListPopFront(LNode* L) { assert(L); assert(L->next); LNode* first = L->next; LDataType x = first->data; L->next = first->next; free(first); first = NULL; return x; }

尾删

//尾删,返回删除的值 LDataType ListPopBack(LNode* L) { assert(L); assert(L->next); LNode* prev = L; LNode* cur = L->next; while (cur->next) { prev = cur; cur = cur->next; } LDataType x = cur->data; free(cur); prev->next = NULL; return x; }

9、销毁

//销毁链表 void ListDestroy(LNode* L) { assert(L); LNode* cur = L; while (cur) { LNode* next = cur->next; free(cur); cur = next; } }

这里不用置空是因为是局部变量，会销毁的。