【数据结构】双向链表

2023-06-20 42

版权

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

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

前言

在前面的博客中，我们学习了单链表的实现与操作。然而单链表在进行找尾等操作时，会导致时间复杂度很低。下面我来介绍一下双向链表的相关知识。

一.双向循环链表的实现

由下面的图我们可以看出，双向链表在创建时会建立两个指针，此时链表就不仅可以往后链接，还可以向前链接。

我们来看看他们的区别：

之前写的单链表是没有头节点的，但是双向循环链表是有头节点的

双向循环链表的头和尾也要建立联系，这样就可以快速找尾

因为之前写过单链表，下面我们就快速的实现双链表了，不细细介绍了。

创建新节点：

LTNode* BuyListNode(LTDataType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
  perror("malloc::newnode");
  return NULL;
  }
  newnode->next = NULL;
  newnode->prev = NULL;
  newnode->data = x;
  return newnode;
}

创建返回链表的头结点.

LTNode* LTInit()
{
  LTNode* newnode = BuyListNode(-1);
  newnode->next = newnode;
  newnode->prev = newnode;
  return newnode;
}

该头节点在初始化说要自行成环，方便后面拼接。

打印链表

void LTPrint(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur!=phead)
  {
  printf("%d<==>", cur->data);
  cur = cur->next;
  }
  printf("\n");
}

判断链表是否只有头节点

bool LTEmpty(LTNode* phead)
{
  assert(phead);
  return phead->next == phead;
}

这个判断十分重要，因为只剩头节点的话就不能删除了。

双向链表尾插

void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = BuyListNode(x);
  LTNode* tail = phead->prev;
  tail->next = newnode;
  newnode->next = phead;
  newnode->prev = tail;
  phead->prev = newnode;
}

双向链表尾删

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

删除了要记得和头节点重新形成联系。

双向链表头插

void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = BuyListNode(x);
  LTNode* first = phead->next;
  phead->next = newnode;
  newnode->next = first;
  newnode->prev = phead;
  first->prev = newnode;
}

在pos位置后面插入

void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* newnode = BuyListNode(x);
  LTNode* cur = pos->next;
  pos->next = newnode;
  newnode->prev = pos;
  newnode->next = cur;
  cur->prev = newnode；
}

二.顺序表和链表的区别

总结

这就是今天对双向循环链表的简要介绍，对于链表的学习就先告一段落了，接下来我们将开始学习栈与队列的知识了！