当前位置:   article > 正文

数据结构要点总结——04 双链表、循环单链表、循环双链表、静态链表、比较顺序表和链表_数据结构单链表,双链表,单循环链表,双循环链表对于哪些操作效率更高

数据结构单链表,双链表,单循环链表,双循环链表对于哪些操作效率更高

上一小节中通过对线性表的链式存储的学习,我们认识到了单链表,或者叫做线性链表

接下来就让我们来学习一下除了单链表之外的其他链表,包括双链表、循环链表、静态链表。最后我还会详细的总结一下顺序表和链表的区别。

1.单链表

首先来回顾一下单链表,要知道,单链表的结点包含两个域,一个是存放数据的数据域(data),另一个就是存放指向后继节点指针的指针域(next)。

优点:

1. 插入和删除操作在特定位置时,时间复杂度较低,只需修改指针。
2. 存储空间按需分配,较为灵活。

缺点:

1. 只能单向遍历,查找特定元素的效率较低,最坏情况需要遍历整个链表。
2. 访问前驱节点较为困难。

2.双链表

如图,不同于单链表,双链表不仅仅具有一个指向后继指针的指针域,还有一个存放指向前驱结点的指针域(piror)。正因如此,双链表具有如下特性:

优点:

1. 可以双向遍历,查找、插入和删除操作在特定位置时更加灵活和高效。
2. 可以方便地获取前驱节点。

缺点:

1. 每个节点需要额外的空间来存储前驱指针,增加了存储空间的开销。

注意!!!因为结点的结构不同在操作代码方面,双链表也并不完全相同(相对于单链表)

1.在初始化双链表时需要将前后指针域都置空(展示使用的为类C语言代码)

  1. bool InitDLinkLis(Dlinklist &L){
  2. L =(DNode *)malloc(sizeof(DNode)); //分配一个头结点
  3. if (L==NULL)//内存不足,分配失败
  4. return false;
  5. L->prior = NULL;//头结点的 prior 永远指向 NULL
  6. L->next = NULL;//头结点之后暂时还没有节点
  7. return true;
  8. }

2.判断是否为空时考虑头节点的后继是否为空即可

  1. //判断双链表是否为空(带头结点)
  2. bool Empty(DLinklist L) {
  3. if (L->next == NULL)
  4. return true
  5. else
  6. return false;
  7. }

3.在插入和删除操作过程中还要考虑前驱指针的问题(以增加结点为例),尾结点位置例外(没有后继指针)

  1. //在p结点之后插入s结点
  2. bool InsertNextDNode(DNode *p,DNode *s){
  3. s->next=p->next;//将结点*S插入到结点*p之后
  4. p->next->prior=s;
  5. s->prior=p;
  6. p->next=s;
  7. return true;
  8. }

双链表总结:

3.循环单链表

循环单链表(有头节点)

循环单链表是单链表的一种变形,尾节点的指针指向头节点,形成一个环形结构。

优点:

1. 从任何一个节点出发都可以遍历整个链表。
2. 适用于需要循环处理链表元素的场景。

缺点:

1.在判断链表结束时需要特别处理,不能通过指针是否为空来判断。要通过头节点的next是否指向头节点来判断,如图:

4.循环双链表

循环双链表(无头结点)

循环双链表是双链表的循环形式,头节点的前驱指针指向尾节点,尾节点的后继指针指向头节点。

优点:

1. 结合了双链表和循环链表的优点,遍历、插入和删除操作都很方便。
2. 可以从任何一个节点开始双向循环遍历。

缺点:

1.存储空间开销相对较大。

2.判空操作和循环单链表一样。

5.静态链表(了解)

学到这,有的人开始发病,它想像顺序表一样为链表分配一片连续的物理地址空间,那么恭喜你发明了静态链表。

优点:

1. 可以在不使用指针的情况下实现链表的基本操作。
2. 便于在一些不支持指针操作的编程语言中模拟链表。

缺点:

1. 数组大小需要预先确定,可能造成空间浪费或不足。
2. 插入和删除操作可能相对复杂,需要移动大量元素来维护游标关系。

6.比较顺序表和链表

逻辑结构:

顺序表:逻辑上相邻的元素在物理存储位置上也相邻,元素之间的关系通过物理存储位置顺序体现。

链表:逻辑上相邻的元素在物理存储位置上不一定相邻,通过节点中的指针来表示元素之间的逻辑关系。

物理/存储结构:

顺序表:使用一组连续的存储单元来依次存储数据元素,存储位置是预先分配的,且容量固定。

 链表:节点可以分散存储在内存中的任意位置,通过指针将各个节点链接起来。

数据的运算/基本操作:

顺序表:

- 访问元素:可以通过下标直接访问,时间复杂度为 O(1)。

- 插入和删除:在中间位置进行插入和删除操作时,需要移动大量元素,平均时间复杂度为 O(n)。

链表:

- 访问元素:只能通过从头节点开始顺序遍历,平均时间复杂度为 O(n)。

- 插入和删除:只需修改指针,时间复杂度为 O(1)。

综上所述,顺序表适合频繁访问元素的操作,而链表适合频繁进行插入和删除操作的场景。!!具体使用哪种数据结构,需要根据具体的应用需求来决定。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/905825
推荐阅读
相关标签
  

闽ICP备14008679号