【数据结构】手撕双向链表-阿里云开发者社区

【数据结构】手撕双向链表

2023-11-27 37

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数据结构】手撕双向链表

前言

在上一期中我们介绍了单链表，也做了一些练习题，在一些题中使用单链表会十分繁琐。因为单链表只能正着走，不能倒着走，例如：回文、逆置。本期我们将学习带头双向循环链表。

1. 双向链表

带头双向循环链表的结构

特点：带头双向循环链表结构最复杂，一般用在单独存储数据。结构虽然结构复杂，但是使用代码实现以后会发现结构会带来多优势，实现反而简单了。

2. 链表的实现

2.1 初始化

LTNode* LTInit()
{
  LTNode* phead = CreateLTNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}

2.2 尾插

带哨兵位的链表尾插时不用判断是否有节点，两种情况的插入相同，而且还不用传递二级指针。

void LTPushBack(LTNode* phead, LTDateType x)
{
  assert(phead);
  LTNode* newnode = CreateLTNode(x);
  phead->prev->next = newnode;
  newnode->prev = phead->prev;
  newnode->next = phead;
  phead->prev = newnode;
}

2.3 尾删

在尾删时我们通过 assert(phead->next != phead); 判断链表是否有节点。同时这个代码就有普遍性，不用单独考虑剩一个节点的情况。

void LTPopBack(LTNode* phead)
{
  assert(phead);
  LTNode* tail = phead->prev;
  LTNode* tailprev = tail->prev;
  free(tail);
  phead->prev = tailprev;
  tailprev->next = phead;
}

2.4 头插

头删重要的是赋值的顺序，顺序错误会找不到后面的节点，导致内存泄漏。带哨兵位的链表不需要传递二级指针，因为改变的是结构体的变量。

void LTPushFront(LTNode* phead, LTDateType x)
{
  assert(phead);
  LTNode* newnode = CreateLTNode(x);
  newnode->next = phead->next;
  phead->next->prev = newnode;
  phead->next = newnode;
  newnode->prev = phead;
}

2.5 头删

我们可以多定义几个指针来保存后面节点的地址，这样就不会造成节点的丢失，不用考虑赋值的顺序，会更加方便。

void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  LTNode* tail = phead->next;
  LTNode* next = tail->next;
  phead->next = next;
  next->prev = phead;
  free(tail);
  tail = NULL;
}

2.6 在pos位置之前插入

void LTInsert(LTNode* pos, LTDateType x)
{
  assert(pos);
  LTNode* posprev = pos->prev;
  LTNode* newnode = CreateLTNode(x);
  posprev->next = newnode;
  newnode->prev = posprev;
  newnode->next = pos;
  pos->prev = newnode;
}

2.7 删除pos位置

void LTErase(LTNode* pos)
{
  assert(pos);
  LTNode* posprev = pos->prev;
  LTNode* posnext = pos->next;
  posprev->next = posnext;
  posnext->prev = posprev;
}

3.双向链表完整源码

List.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDateType;
typedef struct ListNode
{
  LTDateType val;
  struct ListNode* next;
  struct ListNode* prev;
}LTNode;
LTNode* LTInit();
void LTPrint(LTNode* phead);
void LTPushBack(LTNode* phead, LTDateType x);
void LTPushFront(LTNode* phead, LTDateType x);
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
LTNode* LTFind(LTNode* phead, LTDateType x);
void LTInsert(LTNode* pos, LTDateType x);
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);

List.c

#include"List.h"
LTNode* CreateLTNode(LTDateType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->val = x;
  newnode->next = NULL;
  newnode->prev = NULL;
}
LTNode* LTInit()
{
  LTNode* phead = CreateLTNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}
void LTPrint(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  printf("<=>哨兵位<=>");
  while (cur != phead)
  {
    printf("%d<=>", cur->val);
    cur = cur->next;
  }
  printf("\n");
}
void LTPushBack(LTNode* phead, LTDateType x)
{
  assert(phead);
  LTNode* newnode = CreateLTNode(x);
  phead->prev->next = newnode;
  newnode->prev = phead->prev;
  newnode->next = phead;
  phead->prev = newnode;
}
void LTPushFront(LTNode* phead, LTDateType x)
{
  assert(phead);
  LTNode* newnode = CreateLTNode(x);
  newnode->next = phead->next;
  phead->next->prev = newnode;
  phead->next = newnode;
  newnode->prev = phead;
}
void LTPopBack(LTNode* phead)
{
  assert(phead);
  LTNode* tail = phead->prev;
  LTNode* tailprev = tail->prev;
  free(tail);
  phead->prev = tailprev;
  tailprev->next = phead;
}
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  LTNode* tail = phead->next;
  LTNode* next = tail->next;
  phead->next = next;
  next->prev = phead;
  free(tail);
  tail = NULL;
}
LTNode* LTFind(LTNode* phead, LTDateType x)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->val == x)
    {
      return cur;
    }
      cur = cur->next;
  }
  return NULL;
}
void LTInsert(LTNode* pos, LTDateType x)
{
  assert(pos);
  LTNode* posprev = pos->prev;
  LTNode* newnode = CreateLTNode(x);
  posprev->next = newnode;
  newnode->prev = posprev;
  newnode->next = pos;
  pos->prev = newnode;
}
void LTErase(LTNode* pos)
{
  assert(pos);
  LTNode* posprev = pos->prev;
  LTNode* posnext = pos->next;
  posprev->next = posnext;
  posnext->prev = posprev;
}
void LTDestroy(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    LTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  free(phead);
  phead = NULL;
}

通过上面链表的实现，我们已经感受到了带头双向循环链表的方便和简单，它不需要去考虑链表是否有元素，还可以找到前一个元素，在我们使用中提供很大的便利。

本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。