目录
一，前言二 ，有关链表的概念，结构和分类三，无头单向非循环链表（单链表）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 定义单链表结构体 注意：结构体中的struct SListNode * next 不能写成struct SListNode next，因为如果这样写就成了结构体无限嵌套了，这是不允许的！但是定义为 struct SListNode * next 可以，因为它只是一个结构体指针变量，并不会嵌套。
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 尾部插入数据
时间复杂度是O(N). 尾插分为两种情况： 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 尾部删除数据
时间复杂度是O(N). 尾删分为三种情况： 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位置前插入数据
时间复杂度是O(N). 这个函数包含两种情况： 1.当在第一个结点前插入时（pos指向第一个结点，pos是通过查找函数找到的），相当于头插； 2.当在其余结点前插入时，需要一个变量prev保存pos的前一个结点的地址，再把prev，pos，newnode这三个结点链接起来。 代码实现如下：
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x)
{
SLNode* newnode = BuySListNode(x);
//当在第一个结点前插入时，相当于头插
if (*pphead == pos)
{
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处的数据
时间复杂度是O(N). 相同的，这个函数也包含两种情况： 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
#include
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.双链表的功能
双链表是最优的链表结构，在任何位置插入删除数据时间复杂度都是O(1)。
双链表的功能一般有如下几个：
初始化链表打印数据动态申请新结点尾部插入数据头部插入数据尾部删除数据头部删除数据查找指定数据的位置在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);
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
#include
#include
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);
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;
}
参考阅读
发表评论