双向链表

2024-09-05 01:12
文章标签 链表 双向

本文主要是介绍双向链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

单双链表的对比:  

 1.定义与结构
单向链表:是链表的一种,其特点是链表的链接方向是单向的,即每个节点只包含一个指向下一个节点的指针(或称为“链”)。访问链表中的元素需要从头部开始顺序读取。
双向链表:也叫双链表,同样是链表的一种,但每个数据节点中都有两个指针,一个指向直接后继,另一个指向直接前驱。这种结构使得双向链表中的节点可以方便地访问其前驱和后继节点。
2.操作复杂度
添加与删除操作:
单向链表在添加或删除节点时,通常需要遍历链表以找到操作位置的前一个节点,这导致操作的时间复杂度较高,特别是在链表较长时。
双向链表由于可以直接访问前驱节点,因此在添加或删除节点时,可以更快地定位到操作位置,减少遍历次数,提高操作效率。尤其是在链表头部或尾部频繁进行添加、删除操作时,双向链表的优势更为明显。
查找操作:
单向链表和双向链表在查找特定元素时的时间复杂度通常相同,都需要遍历链表中的每个节点进行比较。
3.空间复杂度
双向链表由于每个节点都需要额外存储一个指向前驱的指针,因此相比单向链表会占用更多的存储空间。在长度为n的链表中,双向链表需要多消耗n个指针的空间(每个节点一个)。
4.适用场景
单向链表:适用于对存储空间要求严格,且不需要频繁进行双向遍历的场景。
双向链表:适用于需要频繁进行双向遍历,或者对链表头部和尾部进行频繁添加、删除操作的场景。双向链表能够提供更灵活的操作方式,提高程序的运行效率。
5.总结
双向链表和单向链表各有优缺点,选择哪种链表结构取决于具体的应用场景和需求。在需要频繁进行双向遍历或头部、尾部操作较多的情况下,双向链表是更好的选择;而在对存储空间有严格要求,且不需要频繁进行双向遍历的场景下,单向链表则更为合适。

 双向链表的增删改查:

#include "link.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
//创建头
DLink_t* dlink_create()
{DLink_t* pdoulink = (DLink_t*)malloc(sizeof(DLink_t));if(NULL == pdoulink){return NULL;}pdoulink->phead = NULL;pdoulink->clen = 0;pthread_mutex_init(&(pdoulink->mutex), NULL);return pdoulink;
}
//判空
int is_empty_dlink(DLink_t* pdoulink)
{return NULL == pdoulink->phead;
}
//头增
int push_dlink_head(DLink_t* pdoulink, DataType data)
{DLink_Node_t* pdnode = (DLink_Node_t*)malloc(sizeof(DLink_Node_t));if(NULL == pdnode){return -1;}pdnode->data = data;pdnode->ppre = NULL;pdnode->pnext = NULL;if(is_empty_dlink(pdoulink)){pdoulink->phead = pdnode;    }else{pdnode->pnext = pdoulink->phead;pdoulink->phead->ppre = pdnode;pdoulink->phead = pdnode;}pdoulink->clen++;return 0;
}
//尾增
int push_dlink_tail(DLink_t* pdoulink, DataType data)
{if(is_empty_dlink(pdoulink)){push_dlink_head(pdoulink, data);}else{DLink_Node_t* pdnode = (DLink_Node_t*)malloc(sizeof(DLink_Node_t));if(NULL == pdnode){return -1;}pdnode->data = data;pdnode->ppre = NULL;pdnode->pnext = NULL;DLink_Node_t* p = pdoulink->phead;while(p->pnext != NULL){p = p->pnext;}p->pnext = pdnode;pdnode->ppre = p;}pdoulink->clen++;return 0;
}
//遍历
int print_dlink_all(DLink_t* pdoulink)
{if(is_empty_dlink(pdoulink)){printf("空\n");}else{DLink_Node_t* p = pdoulink->phead;while(p != NULL){printf("id = %d name = %s score = %d\n", p->data.id, p->data.name, p->data.score);p = p->pnext;}}putchar('\n');return 0;
}
//头删
int pop_dlink_head(DLink_t* pdoulink)
{if(is_empty_dlink(pdoulink)){return -1;}else{DLink_Node_t* p = pdoulink->phead;pdoulink->phead = p->pnext;p->ppre = NULL;free(p);}pdoulink->clen--;return 0;
}
//尾删
int pop_dlink_tail(DLink_t* pdoulink)
{if(is_empty_dlink(pdoulink)){return -1;}else{DLink_Node_t* p = pdoulink->phead;while(p->pnext != NULL){p = p->pnext;}p->ppre->pnext = NULL;free(p);}pdoulink->clen--;return 0;
}
//查找
DLink_Node_t* dfind_link(DLink_t* pdoulink, char *key)
{if(is_empty_dlink(pdoulink)){printf("空\n");return NULL;}DLink_Node_t* p = pdoulink->phead;while(p != NULL){if(!strcmp(p->data.name , key)){return p;}p = p->pnext;}return NULL;
}
//修改
int change_dlink(DLink_t* pdoulink, DataType *key, int new_score)
{if(is_empty_dlink(pdoulink)){printf("空\n");return -1;}DLink_Node_t* find = dfind_link(pdoulink, key->name);find->data.score = new_score;return 0;
}
//清空
int delall_dlink(DLink_t* pdoulink)
{while(1){if(is_empty_dlink(pdoulink)){free(pdoulink);return 0;}else{pop_dlink_head(pdoulink);}}return 0;
}

这篇关于双向链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1137549

相关文章

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-

建立升序链表

题目1181:遍历链表 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:2744 解决:1186 题目描述: 建立一个升序链表并遍历输出。 输入: 输入的每个案例中第一行包括1个整数:n(1<=n<=1000),接下来的一行包括n个整数。 输出: 可能有多组测试数据,对于每组数据, 将n个整数建立升序链表,之后遍历链表并输出。 样例输

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

react笔记 8-19 事件对象、获取dom元素、双向绑定

1、事件对象event 通过事件的event对象获取它的dom元素 run=(event)=>{event.target.style="background:yellowgreen" //event的父级为他本身event.target.getAttribute("aid") //这样便获取到了它的自定义属性aid}render() {return (<div><h2>{

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82, 237

总结,删除链表节点问题使用到列表,哈希表,递归比较容易超时,我觉得使用计数排序比较稳,处理起来也不是很难。 1. 力扣3217:从链表中移除在数组中的节点 1.1 题目: 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后,返回修改后的链表的头节点。 示例 1: 输入: nums = [1,2,3], head = [1,2,3,

c++ 链表详细介绍

链表是数据结构的一种,由节点组成,每个节点包含数据和指向下一个节点的指针。链表在C++中的实现可以是单链表、双链表或循环链表。以下是链表的详细介绍: 1. 单链表 结构: 节点(Node):每个节点包含数据和一个指针(next),指向链表中的下一个节点。 示例结构: struct Node {int data;Node* next;Node(int d) : data(d), next(

带头结点的线性链表的基本操作

持续了好久,终于有了这篇博客,链表的操作需要借助图像模型进行反复学习,这里尽可能的整理并记录下自己的思考,以备后面复习,和大家分享。需要说明的是,我们从实际应用角度出发重新定义了线性表。 一. 定义 从上一篇文章可以看到,由于链表在空间的合理利用上和插入、删除时不需要移动等优点,因此在很多场合下,它是线性表的首选存储结构。然而,它也存在某些实现的缺点,如求线性表的长度时不如顺序存储结构的

数据结构基础(栈,队列,数组,链表,树)

栈:后进先出,先进后出 队列:先进先出,后进后出 数组:查询速度快,通过地址值和索引定位,查询任意数据消耗时长相同,在内存中是连续存储的,删除效率低,要将原始数据删除,然后后面的数据前移,添加效率低,添加索引位置的元素,剩下的都需要向前后移动 链表:节点的存储位置(地址)里面存储本身的数据值,和下一个节点的地址值,链表中的节点是独立对象,在内存中是不连续的。查询速度慢,无论查询哪个数据都要从