概念:
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
以单链表为例:
可以看出:
1.链式结构在逻辑上是连续的,但是在物理上不一定连续 2.现实中的节点一般都是从堆上申请出来的 3.从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续
虽然说有8种链表结构,但是现实中主要使用的只有两种结构:
这里需要注意的是,插入时可能头节点为空,要改变指针,所以要传二级指针
//尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{
assert(pphead);
SLNode* node = SLBuyNode(x);
if (*pphead == NULL)
{
*pphead = node;//改变结构体指针,即指向结构体的指针
return;
}
//说明链表不为空,找尾
SLNode* pcur = *pphead;
while (pcur->next)
{
pcur = pcur->next;
}
pcur->next = node;//改变结构体成员,pcur->next通过指针结构体的pcur指针访问结构体的next成员
}
//头插
void SLPushFront(SLNode** pphead, SLDataType x)
{
assert(pphead);
SLNode* node = SLBuyNode(x);
//新节点跟头节点连起来
node->next = *pphead;
//让新的节点称为头节点
*pphead = node;
}
删除时因为要释放空间,所以要传递二级指针
//尾删
void SLPopBack(SLNode** pphead)
{
assert(pphead);
//第一个节点不能为空
assert(*pphead);
//只有第一个节点的情况
if ((*pphead)->next == NULL)
{
//直接把头节点删除
free(*pphead);
*pphead = NULL;
}
else
{
//有多个节点的情况
//找尾节点和尾节点的前一个节点
SLNode* prev = NULL;
SLNode* ptail = *pphead;
while (ptail->next != NULL)
{
prev = ptail;
ptail = ptail->next;
}
//prev的指针不再指向ptail,而是指向ptail的下一个节点
prev->next = ptail->next;
free(ptail);
//打印链表的函数里会判断是否为NULL
ptail = NULL;
}
}
//头删
void SLPopFront(SLNode** pphead)
{
assert(*pphead);
assert(pphead);
SLNode* del = *pphead;
*pphead = (*pphead)->next;
free(del);
del = NULL;
}
//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{
assert(pphead);
//约定链表不能为空,pos也不能为空
assert(pos);
assert(*pphead);
SLNode* node = SLBuyNode(x);
//pos是头节点,头插
if (pos == *pphead)
{
node->next = *pphead;
*pphead = node;
return;
}
//找pos的前一个节点
SLNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
// prev->node->pos
node->next = pos;
prev->next = node;
}
//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x)
{
assert(pos);
SLNode* node = SLBuyNode(x);
//pos node pos->next
node->next = pos->next;
pos->next = node;
return;
}
//删除pos节点
void SLErase(SLNode** pphead, SLNode* pos)
{
assert(pphead);
assert(*pphead);
assert(pos);
//如果pos是头节点
if (pos == *pphead)
{
*pphead = (*pphead)->next;
free(pos);
return;
}
SLNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev pos pos->next
prev->next = pos->next;
free(pos);
pos = NULL;
}
//销毁链表
void SLDesTroy(SLNode** pphead)
{
assert(pphead);
assert(*pphead);
SLNode* pcur = *pphead;
while (pcur->next != NULL)
{
SLNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
slist.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void SLPrint(SLNode* phead)
{
//循环打印
SLNode* pcur = phead;
while (pcur != NULL)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
//创建的新节点
SLNode* SLBuyNode(SLDataType x) {
SLNode* node = (SLNode*)malloc(sizeof(SLNode));
node->data = x;
node->next = NULL;
return node;
}
//尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{
assert(pphead);
SLNode* node = SLBuyNode(x);
if (*pphead == NULL)
{
*pphead = node;//改变结构体指针,即指向结构体的指针
return;
}
//说明链表不为空,找尾
SLNode* pcur = *pphead;
while (pcur->next)
{
pcur = pcur->next;
}
pcur->next = node;//改变结构体成员,pcur->next通过指针结构体的pcur指针访问结构体的next成员
}
//头插
void SLPushFront(SLNode** pphead, SLDataType x)
{
assert(pphead);
SLNode* node = SLBuyNode(x);
//新节点跟头节点连起来
node->next = *pphead;
//让新的节点称为头节点
*pphead = node;
}
//尾删
void SLPopBack(SLNode** pphead)
{
assert(pphead);
//第一个节点不能为空
assert(*pphead);
//只有第一个节点的情况
if ((*pphead)->next == NULL)
{
//直接把头节点删除
free(*pphead);
*pphead = NULL;
}
else
{
//有多个节点的情况
//找尾节点和尾节点的前一个节点
SLNode* prev = NULL;
SLNode* ptail = *pphead;
while (ptail->next != NULL)
{
prev = ptail;
ptail = ptail->next;
}
//prev的指针不再指向ptail,而是指向ptail的下一个节点
prev->next = ptail->next;
free(ptail);
//打印链表的函数里会判断是否为NULL
ptail = NULL;
}
}
//头删
void SLPopFront(SLNode** pphead)
{
assert(*pphead);
assert(pphead);
SLNode* del = *pphead;
*pphead = (*pphead)->next;
free(del);
del = NULL;
}
//查找第一个为x的节点
SLNode* SLFind(SLNode** pphead, SLDataType x)
{
assert(pphead);
SLNode* pcur = *pphead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{
assert(pphead);
//约定链表不能为空,pos也不能为空
assert(pos);
assert(*pphead);
SLNode* node = SLBuyNode(x);
//pos是头节点,头插
if (pos == *pphead)
{
node->next = *pphead;
*pphead = node;
return;
}
//找pos的前一个节点
SLNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
// prev->node->pos
node->next = pos;
prev->next = node;
}
//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x)
{
assert(pos);
SLNode* node = SLBuyNode(x);
//pos node pos->next
node->next = pos->next;
pos->next = node;
return;
}
//删除pos节点
void SLErase(SLNode** pphead, SLNode* pos)
{
assert(pphead);
assert(*pphead);
assert(pos);
//如果pos是头节点
if (pos == *pphead)
{
*pphead = (*pphead)->next;
free(pos);
return;
}
SLNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev pos pos->next
prev->next = pos->next;
free(pos);
pos = NULL;
}
//删除pos之后节点
void SLEraseAfter(SLNode* pos)
{
assert(pos&&pos->next);
//pos pos->next pos->next->next
SLNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}
//销毁链表
void SLDesTroy(SLNode** pphead)
{
assert(pphead);
assert(*pphead);
SLNode* pcur = *pphead;
while (pcur->next != NULL)
{
SLNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
list.h
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
LTDataType _data;
struct ListNode* _next;
struct ListNode* _prev;
}ListNode;
//创建的新节点
ListNode* SLBuyNode(LTDataType x);
//链表的初始化
void InitList(ListNode** pHead);
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
list.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//创建新节点
ListNode* SLBuyNode(LTDataType x) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->_data = x;
node->_next = NULL;
node->_prev = NULL;
return node;
}
//初始化
void InitList(ListNode** pHead)
{
*pHead = SLBuyNode(-1);
(*pHead)->_next = (*pHead);
(*pHead)->_prev = (*pHead);
}
// 双向链表打印
void ListPrint(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->_next;
printf("哨兵位");
while (cur!=pHead)
{
printf("%d<=>", cur->_data);
cur = cur->_next;
}
printf("\n");
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* node = SLBuyNode(x);
//方法一
//ListNode* tail = pHead->_prev;
//tail->_next = node;
//node->_prev = tail;
//pHead->_prev = node;
//node->_next = pHead;
//方法二
node->_prev = pHead->_prev;
pHead->_prev->_next = node;
node->_next = pHead;
pHead->_prev = node;
}
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
assert(pHead);
assert(pHead->_next != pHead);
ListNode* del = pHead->_prev;
ListNode* next = pHead->_prev->_prev;
pHead->_prev = next;
next->_next = pHead;
free(del);
del = NULL;
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* node = SLBuyNode(x);
node->_next = pHead->_next;
pHead->_next->_prev = node;
pHead->_next = node;
node->_prev = pHead;
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
assert(pHead);
assert(pHead->_next != pHead);
ListNode* del = pHead->_next;
ListNode* next = del->_next;
pHead->_next = next;
next->_prev = pHead;
free(del);
del = NULL;
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* cur = pHead->_next;
while (cur != pHead)
{
if (cur->_data == x)
{
return cur;
}
cur = cur->_next;
}
return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* node = SLBuyNode(x);
ListNode* prev = pos->_prev;
prev->_next = node;
node->_prev = prev;
node->_next = pos;
pos->_prev = node;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* del = pos;
ListNode* prev = pos->_prev;
prev->_next = pos->_next;
pos->_next->_prev = prev;
free(del);
del = NULL;
}
void ListDestory(ListNode* pHead)
{
ListNode* cur = pHead->next;
while (cur != pHead)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
free(pHead);
}
不同点 | 顺序表 | 链表 |
---|---|---|
存储空间上 | 物理上一定连续 | 逻辑上连续,但物理上不一定连续 |
随机访问 | 支持O(1) | 不支持:O(N) |
任意位置插入或者删除元素 | 可能需要移动元素,效率低,O(N) | 只需修改指针指向 |
插入 | 动态顺序表,空间不够时需要 扩容 | 没有容量的概念 |
应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
缓存利用率 | 高 | 低 |
备注:缓存利用率参考存储体系结构以及局部原理性。