在之前我们已经讲过< 单链表 >了,单链表查找上一个结点的时间复杂度为O(n),尾插时也要遍历一次链表也是O(n),因为我们每次都要从头开始遍历找,为了克服这单向性的缺点,我们就有了双向链表.
如果要提高链表的查找,尾插等效率,那双向链表(双链表)无疑是首选。
双向链表的概念及结构
双向链表是一种常用的数据结构,它允许我们在O(1)时间内对链表的头尾进行元素的添加和删除操作,同时也支持双向遍历。
双向链表是在单链表的每个结点中,再设置一个指向其前驱结点的指针域,所以在双向链表中的结点都有两个指针域,一个指向直接后继,另一个指向直接前驱。
双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。
双向链表的结构:双向链表的每个节点包含了三个基本元素,分别是元素值、指向前一个节点的指针和指向下一个节点的指针。
- 双向链表存储结构
struct SListNode { int data; //节点存储数据 struct SListNode* next; //指向前驱节点 struct SListNode* prev; //指向后驱节点 };
- 注意:
双向链表头指针是一个虚拟头节点,不存储任何有效数据,他的前驱节点与后驱节点都是指向自己的,头指针节点相当于是一个削兵。用来站岗的。方便链接前后指针.
双向链表接口的实现
申请节点空间
- 链表添加一个节点数据时候,每次都要写一段代码,这样做是不是太繁琐了,我们可以封
装一个函数来解决问题,每次添加一个节点时,将结点存放的数据置为需要存放的值,在将结构体存放节点的地址置为NULL, 需要增加节点时调用一下改函数即可。
//申请节点空间 LTNode* BuyList(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) //判断是否申请成功 { perror("malloc fail"); } else //申请成功 { newnode->data = x; //将结点存放的数据置为需要存放的值 newnode->next = NULL; //节点的地址置为NULL newnode->prev = NULL; //节点的地址置为NULL return newnode; } }
双向链表的初始化
- 其实在双向链表操作中,我们只需要一级指针接收就能修改链表的指向了,但在初始化时
候我们要修改头节点指针,需要二级指针来接收修改头节点,为了后面统一用一级指针,所以我们在初始化时候不传参,直接申请一个节点,然后返回,该指点的前驱指针与后驱指针都是指向自己。节点数据不存储有效数据
LTNode* LTInit() { LTNode* phead = BuyLTNode(-11111);//节点数据不存储有效数据 //前驱指针与后驱指针都是指向自己 phead->next = phead; phead->prev = phead; return phead; //返回该节点 }
双向链表打印数据
- 双向链表是通过结构体存储的头指针下一个指针开始遍历链表的,当遍历的指针指向头指
针则遍历完毕。
void LTPrint(LTNode* phead) { assert(phead); //断言:判断是否为空 printf("guard<==>"); LTNode* cur = phead->next; //从头指针的next开始遍历 while (cur != phead) { printf("%d<==>", cur->data); // 打印数据 cur = cur->next; //迭代指向下一个 } printf("\n"); }
双向链表是否为空
- 如果phead->next为自己,则链表为空,返回真,反之返回假.
bool LTEmpty(LTNode* phead) { assert(phead); //断言 判断是否为空指针 return phead->next == phead; }
双向链表尾插
- 双向链表尾插步骤
- 创建一个新节点 ,将新节点的数据填充为要插入的数据。
- 使用phead->prev找到当前双向链表的尾节点tail。
- 将tail节点的next指针指向新的待插入节点newnode
- 将待插入节点newnode的prev指针指向原尾节点tail
- 将待插入节点newnode的next指针指向链表的头节点phead。
- 将链表头节点phead的prev指针指向插入的新节点newnode。
// 双向链表尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); //断言:判断是否为空 LTNode* tail = phead->prev; //使用phead->prev找到当前双向链表的尾节点tail。 LTNode* newnode = BuyLTNode(x); //创建一个新节点 tail->next = newnode; //将tail节点的next指针指向新的待插入节点newnode newnode->prev = tail; //将待插入节点newnode的prev指针指向原尾节点tail newnode->next = phead; //将待插入节点newnode的next指针指向链表的头节点phead。 phead->prev = newnode; //将链表头节点phead的prev指针指向插入的新节点newnode。 }
双向链表头插
- 双向链表头插步骤
- 创建一个新节点 ,将新节点的数据填充为要插入的数据。
- 使用phead->next找到当前双向链表的头节点,用first保存.
- 将链表头节点phead的next指针指向新插入的节点newnode
- 将待插入节点newnode的prev指针指向链表的头节点phead。
- 将待插入节点newnode的next指针指向原头节点first。
- 将原头节点first的prev指针指向插入的新节点newnode。
void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); //断言 判断是否为空 LTNode* newnode = BuyLTNode(x); //创建一个新节点 ,将新节点的数据填充为要插入的数据 LTNode* first = phead->next; //使用phead->next找到当前双向链表的头节点 phead->next = newnode; //将链表头节点phead的next指针指向新插入的节点newnode newnode->prev = phead; //将待插入节点newnode的prev指针指向链表的头节点phead。 newnode->next = first; //将待插入节点newnode的next指针指向原头节点first。 first->prev = newnode; //将原头节点first的prev指针指向插入的新节点newnode。 }
双向链表尾删
- 双向链表尾删步骤
- 判断链表是否为空,如果为空,则无法进行删除操作
- 使用phead->prev找到当前双向链表的尾节点.(用一个临时变量tail来记录)
- 使用tail->prev找到当前尾节点的前一个节点。(用一个临时变量tailPrev来记录)
- 释放尾节点tail的内存空间
- 将tailPrev的next指针指向链表头节点phead。
- 将链表头节点phead的prev指向tailPrev
void LTPopBack(LTNode* phead) { assert(phead); //判断头指针是否为空 assert(!LTEmpty(phead)); //断言:判断链表是否为空,如果为空,则无法进行删除操作 LTNode* tail = phead->prev; //使用phead->prev找到当前双向链表的尾节点. LTNode* tailPrev = tail->prev; //使用tail->prev找到当前尾节点的前一个节点 free(tail); //释放尾节点tail的内存空间 tailPrev->next = phead; //将tailPrev的next指针指向链表头节点phead phead->prev = tailPrev; //将链表头节点phead的prev指向tailPrev }
双向链表头删
- 双向链表头删步骤
- 判断链表是否为空,如果为空,则无法进行删除操作
- 使用phead->next找到当前双向链表的头节点下一个。(用一个临时变量first来记录)
- 使用first->next找到当前头节点的下一个节点(用一个临时变量second来记录)
- 将链表头节点phead的next指针指向second节点。
- 将second节点的prev指针指向链表头节点phead。
- 释放头节点first的内存空间,进行头删.
void LTPopFront(LTNode* phead) { assert(phead); 判断头指针是否为空 assert(!LTEmpty(phead)); 断言:判断链表是否为空,如果为空,则无法进行删除操作 LTNode* first = phead->next; //使用phead->next找到当前双向链表的头节点的下一个 LTNode* second = first->next; //使用first->next找到当前头节点的下一个节点 phead->next = second; //将链表头节点phead的next指针指向second节点 second->prev = phead; //将second节点的prev指针指向链表头节点phead free(first); //进行头删 }
双向链表的查找
- 获得链表某个节点的数据思路也较简单
- 从头节点的下一个节点开始,依次遍历链表中的每个节点。
- 在每个节点的数据域中查找节点的值是否为x,如果是则返回该节点的指针
- 如果遍历完整个链表都没有找到节点的值为x,则返回NULL。
LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); ///判断头指针是否为空 LTNode* cur = phead->next; //从头节点的下一个节点开始,依次遍历链表中的每个节点。 while (cur != phead) { if (cur->data == x) //在每个节点的数据域中查找节点的值是否为x,如果是则返回该节点的指针 { return cur; } cur = cur->next; //迭代 指向下一个 } return NULL; //如果遍历完整个链表都没有找到节点的值为x,则返回NULL。 }
双向链表在指定位置前插入数据
双向链表插入数据不用像单链表一样从头查找,双向链表只需原地动数据就可。具体步骤如下:
- 获取pos节点的前一个节点(使用一个临时变量tmp来保存)
- 创建一个新的待插入节点newnode
- 将tmp节点的next指向待插入节点newnode
- 将待插入节点newnode的prev指针指向tmp节点
- 将待插入节点newnode的next指针指向pos节点
- 将pos节点的prev指针指向待插入节点newnode
// 在pos之前插入 void LTInsert(LTNode* pos, LTDataType x) { assert(pos);//节点pos不为空 LTNode* tmp = pos->prev; //获取pos节点的前一个节点 LTNode* newnode = BuyLTNode(x); //创建一个新的待插入节点newnode tmp->next = newnode; //将tmp节点的next指向待插入节点newnode newnode->prev = tmp; //将待插入节点newnode的prev指针指向tmp节点 newnode->next = pos; //将待插入节点newnode的next指针指向pos节点 pos->prev = newnode; //将pos节点的prev指针指向待插入节点newnode }
双向链表删除指定位置的值
- 删除指定位置的具体逻辑步骤
1.获取pos节点的前一个节点和后一个节点。(用posprev和posnext临时变量来记录)
2.将posPrev节点的next指向posNext节点
3.将posNext节点的prev指向posPrev节点
4..释放要删除的节点pos的内存空间。
void LTErase(LTNode* pos) { assert(pos); //节点pos不为空 //获取pos节点的前一个节点和后一个节点 LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; posPrev->next = posNext; //将posPrev节点的next指向posNext节点 posNext->prev = posPrev; //将posNext节点的prev指向posPrev节点 free(pos); //释放要删除的节点pos的内存空间。 }
双向链表的销毁
- 当我们不打算使用这个单链表时,我们需要把它销毁,其实也就是在内存中将它释放掉,
以便于留出空间给其他程序或软件使用。释放内存具体步骤如下:
1.使用一个指针变量遍历整个链表在循环中,对于当前遍历到的节点,将其保留下一个节点的指针,以便于在释放当前指针后,指向的节点时能够顺利找到下一个节点.
2.先从头指针的下一个节点开始释放,最后在释放头指针.
void LTDestroy(LTNode* phead) { assert(phead); //断言:头指针不能为空 LTNode* cur = phead->next;//先指向有效位置头指针的下一个节点 while (cur != phead) { LTNode* next = cur->next; //保存下一个指针 free(cur); //释放cur节点占用的内存空间, cur = next; //迭代 } free(phead); //释放头指针 }
总结
- 双向链表相对于单向链表的优点在于它可以支持双向遍历,即从链表头或尾部开始遍历,
因此它可以在某些情况下更加高效。同时,双向链表也支持在任意位置进行链表节点的插入和删除操作,这是单向链表不支持的。因此,双向链表更加灵活,可以满足更多场景下的需求。
- 相对于单链表,双向链表的节点需要额外存储一个指针,即指向前面节点的指针,因此相
对于单链表会占用更多的内存空间。
总之,双向链表是一种值得掌握的重要数据结构,掌握了它的基本操作和应用场景,可以大大提高算法和数据结构等领域的编程水平。