数据结构第三课 -----线性表之双向链表

简介: 数据结构第三课 -----线性表之双向链表

链表的差别

  1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。


带头双向循环链表的实现

我们需要的当这种链表为空时,

这个小知识一定要记住

链表初始化

DLists* plist = (DLists*)malloc(sizeof(DLists));
  plist->next = plist;
  plist->prev = plist;

一个节点要包含三部分分别是值,两个指针


节点创建

//创建节点
DLists* CreateNode(DLDataType elemest)
{
  DLists* newnode = (DLists*)malloc(sizeof(DLists));
  newnode->next = newnode;
  newnode->prev = newnode;
  newnode->val = elemest;
  return newnode;
}

链表的尾插

void DLPushBack(DLists* plist, DLDataType elelmest)
{
  assert(plist);
  //创建节点 
  DLists* newnode = CreateNode(elelmest);
  DLists* n = plist->prev;
  newnode->next = plist;
  newnode->prev = n;
  n->next = newnode;
  plist->prev = newnode;

}

这里我们只需要更改四个指针指向就可以,分别是哨兵位的 、prev 和新节点的prev 、next和旧节点的next

链表尾删

void DLPopBack(DLists* plist)
{
  assert(plist->next != plist && plist);
  //保存最后一个节点的地址
  DLists* p = plist->prev;
  plist->prev = p->prev;
  DLists* p1 = p->prev;
  p1->next = plist;
  free(p);
}

这样写可以防止只有一个节点的时候报错

我们可以创建两个指针,一个指向要free的节点,一个是要和哨兵位关联的节点也就是d2

打印链表

我们可以从d1这个节点开始打印,遇见头节点就结束

//打印
void DLPrint(DLists* plist)
{
  assert(plist);
  printf("哨兵位");
  DLists* tail = plist->next;
  while (tail != plist)
  {
    printf("<=>%d", tail->val);
    tail = tail->next;
  }
  printf("<=>哨兵位\n");
}

链表头插

我们可以创建一个指针用于存储d1的地址,然后把节点插入,这样可以简单快捷

//头插
void DLPushFront(DLists* plist, DLDataType elemest)
{
  assert(plist);
  DLists* n1 = plist->next;
  //创建节点
  DLists* newnode = CreateNode(elemest);
  plist->next = newnode;
  newnode->prev = plist;
  n1->prev = newnode;
  newnode->next = n1;
}

链表头删

当我们删除到哨兵位就不要删除了

//头删
void DLPopFront(DLists* plist)
{
  assert(plist->next != plist && plist);
  // 保存下一个节点
  DLists *nextnode = plist->next;
  DLists* nexnode_next = nextnode->next;
  plist->next = nexnode_next;
  nexnode_next->prev = plist;
  free(nextnode);
  
}

判断链表是否为空

// 判断链表是否为空
bool Empty(DLists* plist)
{
  assert(plist);
  return plist->next == plist;
}

链表pos前插入

//在pos前面插入
DLists* DLPushbefore(DLists* plist, DLists* pos, DLDataType elemest)
{
  assert(plist);
  //创建节点
  DLists* newnode = CreateNode(elemest);
  //pos的前一个节点
  DLists* node = pos->prev;
  pos->prev = newnode;
  newnode->next = pos;
  newnode->prev = node;
  node->next = newnode;

}

计算链表长度

// 长度
int DLSize(DLists* plist)
{
  assert(plist);
  DLists* tail = plist->next;
  int size = 0;
  while (tail != plist)
  {
    size++;
    tail = tail->next;
  }
  return size;


}

链表删除pos前一个节点

//删除pos前一个节点
DLists* DLPopbefore(DLists* plist, DLists* pos)
{
  assert(plist && pos);
  assert(pos->prev != plist);
  //前一个节点
  DLists* n2 = pos->prev;
  //前前一个节点
  DLists* n1 = n2->prev;
  n1->next = pos;
  pos->prev = n1;
  free(n2);
}

删除pos节点

// 删除 pos节点
DLists* DLPop(DLists* plist, DLists* pos)
{
  assert(plist && pos);
  assert(pos!= plist);
  //pos前一个节点
  DLists* n2 = pos->prev;
  //pos后一个节点
  DLists* n1 = pos->next;
  n2->next = n1;
  n1->prev = n2;
  free(pos);
}

释放链表

从d1开释放,遇见head停止

//释放链表
void DLDestroy(DLists** plist)
{
  assert(*plist && plist);
  DLists* tail = (*plist)->next;
  while (tail != *plist)
  {
    DLists* node = tail;
    tail = tail->next;
    free(node);
  }
  free(*plist);
  *plist = NULL;

}

顺序表和链表的差异

链表的优势

  1. 任意位置插入和删除都是O(1),前提是知道位置
  2. 按需申请和释放


缺点问题

3. 下标随机访问不方便,物理空间不连续,O(n)

4. 链表不好排序


顺序表的问题

5. 头部插入或者中间插入删除效率低下,要移动数据

6. 空间不够要扩容,扩容会有一定消耗且可能存在一定的空间浪费.

7. 只适合尾插尾删


优势

支持下标的随机访问

相关文章
|
3天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
24 4
|
4天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
4天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
23天前
|
算法 Java
数据结构与算法学习五:双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现,并通过实例演示了双向链表的优势和应用。
15 0
数据结构与算法学习五:双链表的增、删、改、查
|
3天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
13 0
|
4天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
17 0
|
23天前
|
存储
探索数据结构:便捷的双向链表
探索数据结构:便捷的双向链表
|
23天前
|
存储
探索数据结构:单链表的实践和应用
探索数据结构:单链表的实践和应用
|
23天前
|
算法 Java
数据结构与算法学习六:单向环形链表应用实例的约瑟夫环问题
这篇文章通过单向环形链表的应用实例,详细讲解了约瑟夫环问题的解决方案,并提供了Java代码实现。
15 0