本文介绍: 双向链表相关操作的介绍,以及顺序表与链表的区别
文章目录
1. 双向带头循环链表的结构
与单链表不同的是:
- 双向链表有一个“哨兵位”作为单独的头节点
- 每个节点都可以指向其前驱和后继节点
- 链表是循环的
带头链表里的头节点,实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这里“放哨的”
“哨兵位”存在的意义:遍历循环链表避免死循环。
typedef int ListDataType;
typedef struct List
{
ListDataType data;
struct List* prev;//指向前驱节点
struct List* next;//指向后继节点
}List;
2. 相关操作
2.1 创建节点
- 创建的每个节点应该自己成环
List* BuyNode(ListDataType x)
{
List* newnode = (List*)malloc(sizeof(List));
if (newnode == NULL)
{
perror(malloc);
return NULL;
}
newnode->data = x;
newnode->next = newnode;
newnode->prev = newnode;
}
创建哨兵位:
int main()
{
//哨兵位
List* head = BuyNode(-1);
return 0;
}
2.2 尾插
void ListPushBack(List* phead, ListDataType x)
{
assert(phead);
List* newnode = BuyNode(x);
newnode->next = phead;
newnode->prev = phead->prev;
//尾节点指向新节点
phead->prev->next = newnode;
phead->prev = newnode;
}
2.3 头插
void ListPushFront(List* phead, ListDataType x)
{
assert(phead);
List* newnode = BuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next = newnode;
//只有头节点时,就是头节点的prev
phead->next->prev = newnode;
}
2.4 打印
由于是循环链表,所以循环停止的条件应该是:cur != head
void ListPrint(List* phead)
{
assert(phead);
List* cur = phead->next;
while (cur != phead)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULLn");
}
2.5 尾删
- 不能没有节点
- 尾节点的前驱节点指向头节点
- 头节点指向尾节点的前驱节点
- 释放尾节点
void ListPopBack(List* phead)
{
assert(phead);
//只有头节点
assert(phead->next != phead);
List* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
free(del);
}
2.6 头删
- 不能没有节点
- 待删除节点的后继节点的prev指向头节点
- 头节点指向待删除节点的后继节点
void ListPopFront(List* phead)
{
assert(phead);
assert(phead->next != phead);
List* del = phead->next;
del->next->prev = phead;
phead->next = del->next;
free(del);
}
2.7 查找
List* ListFind(List* phead, ListDataType x)
{
assert(phead);
assert(phead->next != phead);
List* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
2.8 指定位置前/后插入
- 将新节点与指定位置相连即可
指定位置前
void ListPosFrontInsert(List* pos, ListDataType x)
{
assert(pos);
List* newnode = BuyNode(x);
List* prev = pos->prev;
newnode->prev = prev;
newnode->next = pos;
prev->next = newnode;
pos->prev = newnode;
}
指定位置后
void ListPosBackInsert(List* pos, ListDataType x)
{
assert(pos);
List* newnode = BuyNode(x);
List* next = pos->next;
newnode->next = next;
newnode->prev = pos;
next->prev = newnode;
pos->next = newnode;
}
2.9 删除指定位置的节点
- 将指定位置的前驱节点、后继节点连接即可
void ListPosDel(List* pos)
{
assert(pos);
List* prev = pos->prev;
List* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}
2.10 删除指定位置后的节点
- 若指定位置是尾节点,则应该执行头删
void ListPosAfterDel(List* phead, List* pos)
{
assert(phead);
assert(pos);
if (pos->next == phead)
{
ListPopFront(phead);
}
else
{
List* del = pos->next;
del->next->prev = pos;
pos->next = del->next;
free(del);
}
}
2.11 销毁链表
- 此接口的参数是一级指针,所以并不能将哨兵位销毁;因此需要再调用处再将哨兵位置为空
void ListDestroy(List* phead)
{
assert(phead);
assert(phead->next != phead);
List* cur = phead->next;
while (cur != phead)
{
List* next = cur->next;
free(cur);
cur = next;
}
cur = NULL;
free(phead);
phead = NULL;
}
3.顺序表与链表区别
不同点 | 顺序表 | 链表 |
---|---|---|
存储空间上 | 物理上一定连续 | 逻辑上连续,物理上不一定连续 |
随机访问 | O(1) | O(N) |
任意位置插入或删除 | 可能需要搬运元素,效率低O(N) | 只需修改指针指向 |
插入 | 动态顺序表,空间不够需要扩容 | 没有容量的概念 |
应用场景 | 元素高效存储,频繁访问 | 任意位置频繁插入/删除 |
缓存利用率 | 高 | 低 |
原文地址:https://blog.csdn.net/weixin_69380220/article/details/136071250
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_67923.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。