本文主要是介绍双向链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
单双链表的对比:
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;
}
这篇关于双向链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!