目录
目录
一、链表种类
链表分为带头（不带头）、单向（双向）和循环（不循环）这几个分类。
二、单链表概念
单链表是⼀种物理存储结构（不一定连续）上非连续、非顺序的存储结构，数据元素的逻辑顺序（连续）是通过链表中的指针链接次序实现的。他是不带头单向不循环链表，底层是结构体。
三、单链表实现
3.1 单链表创建结点
创建结点时先写出单链表的结构体,如下：
//结构体
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
创建结点
//创造节点
SLTNode* SLTbuyNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}3.2 单链表销毁
//销毁
void SListDestroy(SLTNode** pphead)//这里用二级指针是通过修改*phead这个指针地址来修改内部值（不带头）
{
assert(*pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}3.3 单链表尾插
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* ptail = *pphead;
//创建节点
SLTNode* newnode = SLTbuyNode(x);
//考虑没节点
if (ptail == NULL)
{
*pphead = newnode;
}
//找尾节点
else
{
while (ptail->next)
{
ptail = ptail->next;
}
ptail->next = newnode;
}
}
3.4 单链表尾删
//尾删
void SLTPopBack(SLTNode** pphead)
{
assert(*pphead);
SLTNode* pcur = *pphead;
SLTNode* prev = NULL;
SLTNode* ptail = pcur;
//考虑只有一个尾项删除
if (ptail->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
free(ptail);
ptail = NULL;
}
}
3.5 单链表头插
//头插
void SLTPushFront(SLTNode** pphead,SLTDataType x)
{
assert(pphead);
//创造节点
SLTNode* newnode = SLTbuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
3.6 单链表头删
//头删
void SLTPopFront(SLTNode** pphead)
{
assert(*pphead);
SLTNode* pcur = *pphead;
SLTNode* next = (*pphead)->next;
free(pcur);
pcur = NULL;
*pphead = next;
}
3.7 单链表寻找值
//查询
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
assert(phead);
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}3.8 单链表任意插（之前、之后）
//任意位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(*pphead);
SLTNode* pcur = *pphead;
SLTNode* newnode = SLTbuyNode(x);
//考虑重回时pcur和pos
if (pcur == pos)
{
SLTPushFront(pphead, x);
}
//不重合时
else
{
while (pcur->next != pos)
{
pcur = pcur->next;
}
newnode->next = pcur->next;
pcur->next = newnode;
}
}
//任意位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTbuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}3.9 单链表任意删（当前、后面）
//任意删
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(*pphead);
SLTNode* pcur = *pphead;
SLTNode* next = pos->next;
//头删
if (pcur == pos)
{
*pphead = pcur->next;
}
else
{
while (pcur->next != pos)
{
pcur = pcur->next;
}
pcur->next = next;
free(pos);
pos = NULL;
}
}
//任意删pos后面
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{
assert(*pphead && pos->next != NULL);
SLTNode* pcur = *pphead;
SLTNode* next = pos->next;
while (pcur != pos)
{
pcur = pcur->next;
}
pcur->next = next->next;
free(next);
next = NULL;
}四、双向链表概念
双向链表是一种数据结构，每个节点包含三个部分：数据、指向前一个节点的指针（prev）和指向下一个节点的指针（next）。双向链表是带头的双向循环链表，底层是结构体。
五、双向链表实现
4.1 双向链表创建结点
定义双向链表
//双向链表结构定义
typedef int LTDataType;
typedef struct ListNode
{
LTDataType Data;//数据
struct ListNode* prev;
struct ListNode* next;
}ListNode;
创建头结点
//创建头结点
ListNode* ListCreate()
{
ListNode* pHead = (ListNode*)malloc(sizeof(ListNode));
if (pHead == NULL)
{
perror("malloc1");
exit(1);
}
pHead->Data = -1;
pHead->next = pHead->prev = pHead;
return pHead;
}
创建结点
//创造新节点
ListNode* ListbuyNode(LTDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("malloc2");
exit(1);
}
newnode->Data = x;
newnode->prev = newnode->next = newnode;
return newnode;
}4.2 双向链表销毁
//销毁
void ListDestory(ListNode* pHead)//这里不用二级指针是由于不需要改变pHead这个头结点，只要通过pHead这个指针去访问并可修改下个指针即可
{
ListNode* del = pHead->next;
while (del != pHead)
{
ListNode* next = del->next;
free(del);
del = next;
}
pHead = NULL;
}4.3 双向链表尾插
//尾插
void ListPushBack(ListNode* pHead,LTDataType x)
{
assert(pHead);
ListNode* newnode = ListbuyNode(x);
//newnode
newnode->next = pHead;
newnode->prev = pHead->prev;
//pHead pHead->prev
pHead->prev->next = newnode;
pHead->prev = newnode;
}4.4 双向链表尾删
//尾删
void ListPopBack(ListNode* pHead)
{
assert(!LTEmpty(pHead));
ListNode* del = pHead->prev;
//pHead del->prev del
del->prev->next = pHead;
pHead->prev = del->prev;
//释放
free(del);
del = NULL;
}4.5 双向链表头插
//头插
void ListPushFront(ListNode* pHead,LTDataType x)
{
ListNode* newnode = ListbuyNode(x);
//newnode
newnode->next = pHead->next;
newnode->prev = pHead;
//pHead newnode pHead->next
pHead->next->prev = newnode;
pHead->next = newnode;
}4.6 双向链表头删
//头删
void ListPopFront(ListNode* pHead)
{
assert(!LTEmpty(pHead));
ListNode* del = pHead->next;
//pHead->del
pHead->next = del->next;
//del-pHead
del->prev = pHead;
free(del);
del = NULL;
}
4.7 双向链表寻找值
//查询
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* pcur = pHead->next;
while (pcur != pHead)
{
if (pcur->Data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}4.8 双向链表任意插（之前、之后）
//任意之前插
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* mid = ListbuyNode(x);
//mid
mid->prev = pos->prev;
mid->next = pos;
//pos->prev mid pos
pos->next->prev = mid;
pos->prev->next = mid;
}
//任意之后插
void ListAfter(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* mid = ListbuyNode(x);
//mid
mid->prev = pos;
mid->next = pos->next;
//pos mid pos->next
pos->next->prev = mid;
pos->next = mid;
}4.9 双向链表任意删
//任意删
void ListErase(ListNode* pos)
{
assert(!LTEmpty(pos));
ListNode* del = pos;
//del->prev --- del->next
del->prev->next = del->next;
//del->next->prev --- del->prev
del->next->prev = del->prev;
free(pos);
pos = NULL;
}六、总结与反思（单双链表优缺点）
对于单链表的优缺点
对于双向链表优缺点
| 双向链表优点 | 缺点 |
| 查询比单链表效率高，虽然都是o（N），但是可以利用双向特性，进行左右开始查询（类似二分法） | 内存占用大（两个指针和一个数据，3个元素） |
| 双向遍历 | 代码实现向较为单链表复杂 |
| 插入删除方便 |
总结：对于双向链表和单链表，当需要频繁存入大量数据并查询时，可以首先考虑单链表（内存和代码实现）。当需要频繁插入和删除并频繁遍历时，可以考虑双向链表（时间效率高）。