目录
- 一，前言
- 二 ，有关链表的概念，结构和分类
- 三，无头单向非循环链表（单链表）
- 1.单链表的功能
- 2.单链表功能的实现
- 3.完整代码
- 四，带头双向循环链表（双链表）
- 1.单链表与双链表的结构区别
- 2.双链表的功能
- 3.双链表功能的实现
- 4. 完整代码
一，前言
1.顺序表的问题和思考
问题：
- 中间/头部的插入删除，时间复杂度为O(N)。
- 增容需要申请新空间，拷贝数据，释放旧空间,会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考：
如何解决以上问题呢？下面给出了链表的结构来看看。
二 ，有关链表的概念，结构和分类
1. 链表的概念和结构
链表是一种物理存储结构上非连续、非顺序的存储构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
1.1 逻辑结构（就是我们想象的，数据元素依次链接）：
1.2 物理结构（实实在在的在内存中真实存储的结构，数据元素不一定是连续存储的）：
1. 每个结点（一块空间）都是随机在内存中动态开辟（malloc)出来的,都有它们的地址（第一个字节的地址），这些地址也是随机的。
2. 每个新结点都包含两个区域——数据域和指针域。数据域存放我们要操作的数据，指针域存放着下一个结点的地址。我们就是通过这个地址和下一个结点建立联系。
3. 最后一个结点的指针域中存放的是NULL。
2. 链表的分类
实际中的链表种类非常多，以下情况组合起来就有8种链表构：
比如：
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构，下面也只对这两种结构进行代码实现：
- 无头单向非循环链表： 结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表： 结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
三，无头单向非循环链表（单链表）
1.单链表的功能
单链表的功能一般有如下几个：
- 打印数据
- 动态申请新结点
- 尾部插入数据
- 头部插入数据
- 尾部删除数据
- 头部删除数据
- 查找指定数据的位置
- 在pos位置前插入数据
- 删除pos处的数据
2.单链表功能的实现
2.1 建立单链表
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;//要操作的数据
struct SListNode * next;//指向下一个结点的指针
}SLNode;
2.2 打印数据
首先定义一个指针cur指向第一个结点（头指针phead)，使用循环进行遍历，当cur != NULL时，打印数据，再让cur指向下一个结点，直至跳出循环。
代码实现如下：
void SListPrint(SLNode* phead)
{
SLNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
2.3 动态申请新结点
由于链表在内存中不是一块连续的空间，所以每次进行插入（增加）数据的操作时，都要在内存中创建新结点，即动态开辟（malloc)一块空间。
//这个函数是每次在增加数据时进行调用的
SLNode* BuySListNode(SLTDataType x)
{
//随机开辟一块空间（结点）
SLNode* newnode =(SLNode*)malloc(sizeof(SLNode));
if (newnode == NULL)
{
printf("malloc fail!\n");
return;
}
newnode->data = x;//存入要插入的数据
newnode->next = NULL;//把最后一个结点指向空
return newnode;
}
2.4 尾部插入数据
尾插分为两种情况：
1.如果链表中没有结点时，直接让新结点指向头指针；
2.链表中至少有一个结点时，需要循环找到链表的尾结点的指针，再链接上新结点。
代码实现如下：
void SListPushBack(SLNode** pphead, SLTDataType x)
{
SLNode* newnode = BuySListNode(x);
//1.如果表中没有一个节点
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//2.有两个节点以上，找尾，
SLNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
//链接新节点
tail->next = newnode;
}
}
2.5 头部插入数据
头插，首先在内存中开辟一个结点，把链表内原来第一个结点的地址存入新结点中，使两者建立联系，再把新结点的地址存入头指针即可。
代码实现如下：
void SListPushFront(SLNode** pphead, SLTDataType x)
{
SLNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
2.6 尾部删除数据
尾删分为三种情况：
1.如果链表中没有数据（链表为空），则不需要删除，略作提示终止程序即可；
2.如果表中只有一个结点，直接free释放，再置空即可；
3.如果表中多于一个结点，不能直接循环找到尾结点删除，这样前一个结点会形成野指针，而是要先保存倒数第二个结点的地址，再把尾结点释放置空。
代码实现如下：
void SListPopBack(SLNode** pphead)
{
//1.链表内无数据
if (*pphead == NULL)
{
printf("链表为空!\n");
return;
}
//2.如果只有一个结点
else if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLNode* prev = NULL;
SLNode* tail = *pphead;
//3.记住前一个位置
while (tail->next != NULL)
{
prev= tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
2.7 头部删除数据
头删，相同的道理，不能直接把第一个结点free释放，这样就找不到后面的数据了，而是先要定义一个指针变量保存第二个结点的地址，再把第一个结点free释放，置空。最后让头指针指向这个变量。
代码实现如下：
void SListPopFront(SLNode** pphead)
{
SLNode* cur = NULL;
cur = (*pphead)->next;
free(*pphead);
*pphead = cur;
}
2.8 查找指定数据的位置
循环遍历链表，查找出指定数字的位置，用指针pos保存，这个函数一般配合下面两个函数一起使用。
代码实现如下：
SLNode* SListFind(SLNode* phead, SLTDataType x)
{
SLNode* cur = phead;
while (cur!=NULL)
{
if (cur->data == x)
{
//找到了发回地址
return cur;
}
cur = cur->next;
}
//没有找到，返回空
return NULL;
}
2.9 在pos位置前插入数据
这个函数包含两种情况：
1.当在第一个结点前插入时（pos指向第一个结点，pos是通过查找函数找到的），相当于头插；
2.当在其余结点前插入时，需要一个变量prev保存pos的前一个结点的地址，再把prev，pos，newnode这三个结点链接起来。
代码实现如下：
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x)
{
SLNode* newnode = BuySListNode(x);
//当在第一个结点前插入时，相当于头插
if ((*pphead)->next == NULL)
{
SListPushFront(pphead, x);
}
else
{
SLNode* prev = NULL;
SLNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
prev = cur;//保存到了pos前一个结点的地址
prev->next = newnode;
newnode->next = pos;
}
}
2.10 删除pos处的数据
相同的，这个函数也包含两种情况：
1.当要删除第一个结点时（此时pos指向第一个结点），相当于头删；
2.当pos指向其他位置时，不能直接free释放掉pos，而是要先找到pos前一个结点的位置，把它与pos的后一个结点进行链接，最后free释放掉pos。
代码实现如下：
void SListErase(SLNode** pphead, SLNode* pos)
{
//当要删除第一个结点时，相当于头删
if (pos == *pphead)
{
SListPopFront(pphead);
}
else
{
SLNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
3.完整代码
SList.h
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);
//打印数据
void SListPrint(SLTNode* phead);
//尾删
void SListPopBack(SLTNode** pphead);
//头删
void SListPopFront(SLTNode** pphead);
//查找
SLTNode* SListFind(SLTNode* pphead, SLTDataType x);
//在pos位置前插入数据
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos位置处删除数据
void SListEarse(SLTNode** pphead, SLTNode* pos);
SList.c
#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
void SListPrint(SLTNode* phead)
{
SLTNode* cur =phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
SLTNode* BuySListNode(SLTDataType x)
{
//开辟新节点
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
printf("malloc fail!\n");
return;
}
newnode->data = x;
newnode->next = NULL;
}
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
//判断刚开始是否有节点,若没有，则直接开辟
SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//若已经存在节点 则找到尾结点，链接新节点
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SListPopFront(SLTNode** pphead)
{
if (*pphead == NULL)
{
printf("链表无数据！\n");
}
//注意不能直接free，要先记住第二个节点的地址，再释放第一个节点
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
void SListPopBack(SLTNode** pphead)
{
//1.当链表为空时
if (*pphead == NULL)
{
printf("链表无数据!\n");
return;
}
//2.只有一个节点时,直接释放掉，再置空
else if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
//让prev记住倒数第二个节点，此时tail指向最后一个节点
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
//释放最后一个空间
free(tail);
//这时prev是最后一个节点，要置空，避免野指针
prev->next = NULL;
}
}
SLTNode* SListFind(SLTNode* pphead, SLTDataType x)
{
SLTNode* cur = pphead;
//遍历链表，找数
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
//要在第一个节点前插入数据时，相当于头插
if (pos == *pphead)
{
SListPushFront(pphead, x);
}
else
{
SLTNode* newnode = BuySListNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}
void SListEarse(SLTNode** pphead, SLTNode* pos)
{
//1.当pos为第一个节点时，没有前一个节点，删除时相当于头删
if (pos == *pphead)
{
SListPopFront(pphead);
}
else
{
//2.Pos不是第一个节点，找到pos的前一个位置，再释放空间
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
//在这里对那些函数接口进行测试，例如：
void SListTest()
{
//定义一个头指针，置空
SLTNode* plist = NULL;
//这里传地址的原因是我们要对链表中的数据进行修改，
//由于形参是实参的一份临时拷贝，改变形参不影响实参
//所以只有传地址，对内存进行修改
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
//在3前面插入有一个30，先找到3的前一个的位置，再插入
SLTNode* pos = SListFind(plist, 3);
if (pos)
{
SListInsert(&plist,pos，30);
}
SListPrint(plist);
}
int main()
{
SListTest();
return 0;
}
四，带头双向循环链表（双链表）
虽然单链表是我们要掌握基础链表之一，但是它并不完美，比如它不能从后往前操作，不容易找到前驱，每次尾插，尾删都要进行遍历，使得时间复杂度为O（N）等，使用起来其实并不是那么方便。
下面介绍的双链表虽然结构更复杂，但是它完美解决了单链表的缺陷，使用起来十分方便，丝滑。
1.单链表与双链表的结构区别
- 双链表的"带头"是指需要在链表的最前端动态申请一个特殊的结点，这第一个结点不存储有效数据，这种结点也称为带哨兵位的头结点。 它的好处是在进行增删查改等操作时，不需要改变传过来的指针了，也就意味着不需要传二级指针了。
而且，与单链表相比，它不仅有存放下一个结点地址的next指针（也可叫后驱指针），还会增加一个前驱指针prev，用来存放上一个节点的地址。这样就使得每个节点都能快速找到自己的前一个结点，也能找到自己的下一个结点。 最终会形成"循环"。
双链表的这两点结构对我们增删查改的实现有极大的方便，使它能够完美解决单链表的缺陷。- 单链表的结构就更简单了，它没有带头，也没有循环，只能从头到尾前一个结点指向后一个结点。
2.双链表的功能
双链表的功能一般有如下几个：
- 初始化链表
- 打印数据
- 动态申请新结点
- 尾部插入数据
- 头部插入数据
- 尾部删除数据
- 头部删除数据
- 查找指定数据的位置
- 在pos位置前插入数据
- 删除pos处的数据
- 销毁链表
3.双链表功能的实现
3.1 建立双链表
typedef int SLTDataType;
typedef struct ListNode
{
SLTDataType data;//要操作的数据
struct ListNode* next;//后驱指针
struct ListNode* prev;//前驱指针
}ListNode;
3.2 初始化链表
首先要申请一个带哨兵位的头结点，并且让它的前驱和后驱都指向自己。
代码实现如下：
//注意：这个函数并没有进行传参，而是通过返回值的方式
//把申请空间的地址返回。这就避免了使用二级指针。
ListNode* ListInit()
{
ListNode* phead = BuyListNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}
3.3 动态申请新结点
在初始化链表和插入数据时，都需要在内存中动态申请新结点。
ListNode* BuyListNode(SLTDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
printf("malloc fail!\n");
return;
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
3.4 打印数据
首先定义一个指针cur指向第二个结点（头节点不存放数据），由于是循环链表，所以通过循环，当cur != phead时，打印出数据即可。
代码实现如下：
void ListPrint(ListNode* phead)
{
ListNode* cur = phead->next;
if (cur == phead)
{
printf("链表为空!\n");
return;
}
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
3.5 尾部插入数据
尾插，申请新结点newnode，定义变量tail指向最后一个结点（其实就是phead的前驱，这就避免了要向单链表那样通过遍历找到尾节点，体现出了双链表的优越性。），再链接起phead，newnode，tail
代码实现如下：
void ListPushBcck(ListNode* phead, SLTDataType x)
{
assert(phead);//断言
ListNode* newnode = BuyListNode(x);
ListNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
phead->prev = newnode;
newnode->next = phead；
}
3.6 头部插入数据
头插，就是在头结点phead和和第二个结点之间插入，申请新结点newnode，再定义变量first指向第二个结点，再链接起三者即可。
代码实现如下：
void ListPushFront(ListNode* phead, SLTDataType x)
{
assert(phead);
ListNode* first = phead->next;
ListNode* newnode = BuyListNode(x);
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
}
3.7 尾部删除数据
尾删，与单链表类似，不能直接把最后一个结点free释放。定义一个变量tail指向尾结点（其实就是phead->prev)，再定义一个变量prev保存倒数第二个结点的地址（其实就是tail->prev)，再进行三者链接，最后释放，置空。
代码实现如下：
void ListPopBcck(ListNode* phead)
{
assert(phead);
//此时链表一个结点都没有
assert(phead->next != phead);
ListNode* tail = phead->prev;
ListNode* prev = tail->prev;
phead->prev = prev;
prev->next = phead;
free(tail);
tail = NULL;
}
3.8 头部删除数据
头删，是删除第二个结点，不能直接释放第二个结点。定义变量first指向第二个结点（就是phead->next)，再定义变量second指向第三个结点（就是first->next)，再进行三者链接，最后释放，置空。
代码实现如下：
void ListPopFront(ListNode* phead)
{
assert(phead);
//此时链表一个结点都没有
assert(phead->next != phead);
ListNode* first = phead->next;
ListNode* second = first->next;
phead->next = second;
second->prev = phead;
free(first);
first = NULL;
}
3.9 查找指定数据的位置
定义变量cur指向第二个结点，直接循环遍历，直至cur指向phead。若找到了，则直接返回该结点的地址，用pos接收，否则返回NULL。这个函数一般与下面两个函数配合使用。
ListNode* ListFind(ListNode* phead, SLTDataType x)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
3.10 在pos位置前插入数据
pos是查找函数找到的位置，申请新结点newnode，定义变量prev指向pos的前一个结点，再链接三者即可。
代码实现如下：
void ListInsert(ListNode* pos, SLTDataType x)
{
assert(pos);//断言，pos不能为空
ListNode* prev = pos->prev;
ListNode* newnode = BuyListNode(x);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
3.11 删除pos处的数据
与前面类似，不能直接free释放pos处的空间。定义变量prev指向（保存）pos前一个结点的（地址），定义变量next指向（保存）pos后一个结点（地址），再把两者进行链接，最后释放，置空。
代码实现如下：
void ListEarse(ListNode* pos)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);//释放
pos = NULL;
}
3.12 销毁链表
销毁链表是从第二个结点开始，循环依次释放。定义变量cur指向第二个结点，与前面类似，不能直接释放cur处的空间，而是要先保存到下一个结点的空间，再把当前节点空间释放。最后再释放头结点（phead)，置空。
代码实现如下：
void ListDestory(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
ListNode* next = cur->next;//保存下一个结点的地址
free(cur);//先释放有数据的结点
cur = next;
}
free(phead);//释放哨兵位头结点
phead = NULL;
}
4. 完整代码
List.h
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct ListNode
{
SLTDataType data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
//初始化链表
ListNode* ListInit();
//销毁链表
void ListDestory(ListNode* phead);
//打印数据
void ListPrint(ListNode* phead);
//尾插
void ListPushBcck(ListNode* phead, SLTDataType x);
//头插
void ListPushFront(ListNode* phead, SLTDataType x);
//尾删
void ListPopBcck(ListNode* phead);
//头删
void ListPopFront(ListNode* phead);
//查找
ListNode* ListFind(ListNode* phead, SLTDataType x);
//在pos前插入数据
void ListInsert( ListNode* pos, SLTDataType x);
//删除pos处的数据
void ListEarse( ListNode* pos);
List.c
#define _CRT_SECURE_NO_WARNINGS
#include "List.h"
ListNode* BuyListNode(SLTDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
printf("malloc fail!\n");
return;
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
ListNode* ListInit()
{
ListNode* phead = BuyListNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}
void ListPrint(ListNode* phead)
{
ListNode* cur = phead->next;
if (cur == phead)
{
printf("链表为空!\n");
return;
}
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
void ListDestory(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}
void ListPushBcck(ListNode* phead, SLTDataType x)
{
assert(phead);
ListNode* newnode = BuyListNode(x);
ListNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
phead->prev = newnode;
newnode->next = phead;
}
void ListPushFront(ListNode* phead, SLTDataType x)
{
assert(phead);
ListNode* first = phead->next;
ListNode* newnode = BuyListNode(x);
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
}
void ListPopFront(ListNode* phead)
{
assert(phead);
//此时链表一个结点都没有
assert(phead->next != phead);
ListNode* first = phead->next;
ListNode* second = first->next;
phead->next = second;
second->prev = phead;
free(first);
first = NULL;
}
void ListPopBcck(ListNode* phead)
{
assert(phead);
//此时链表一个结点都没有
assert(phead->next != phead);
ListNode* tail = phead->prev;
ListNode* prev = tail->prev;
phead->prev = prev;
prev->next = phead;
free(tail);
tail = NULL;
}
ListNode* ListFind(ListNode* phead, SLTDataType x)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void ListInsert(ListNode* pos, SLTDataType x)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* newnode = BuyListNode(x);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
void ListEarse(ListNode* pos)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include "List.h"
//在这个函数中进行各函数接口的测试：
ListNode* ListTest()
{
ListNode* plist = ListInit();
ListPushBcck(plist, 1);
ListPushBcck(plist, 2);
ListPushBcck(plist, 3);
ListPushBcck(plist, 4);
ListPrint(plist);
ListDestory(plist);
return 0;
}
int main()
{
ListTest();
return;
}
