数据结构中的Linked list和Binary tree
2021/10/20 6:09:27
本文主要是介绍数据结构中的Linked list和Binary tree,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
接昨天,仍没有代码实现。
3.Linked list(链表)
在数组 (Array) 中,元素顺序是由数组索引决定。数组插、删元素的时候会移动很多元素,所以时间复杂度会更高;且数组占用的空间是连续的,必须声明足够的空间。
但在链表中,元素顺序由每个对象的指针决定。链表的存储是不连续的,可以节省很多空间。
如下图所示,链表中每一个object中,除了存储element的key外,还额外开辟出了两个内存空间,prev(ious)以及next。这个prev和next分别为访问前一个链表节点以及后一个链表节点。
如果x.prev为NULL,则这个节点中的element,即x,为首元素,或称为head;反之若x.next为NULL,则x为尾元素,或成为tail.
上图是一个双链表,即可以双向链接。除此之外还有单链表,即单向链接,只能寻找上一个或者下一个节点;还有循环单链表,即尾部tail可以去寻找head。
关于L.head的理解,(有点难)。L.head要理解为一个pointer,而不是一个对象。非空链表的第一个结点称为链表的head。要访问链表中的对象,需要有一个指向链表头的指针。从head开始,可以根据 .next 访问链表中的其余节点,也可以反过来通过 .prev访问前面的节点。
对链表的操作
Insert(简化程序为插在表头)
x.next = L.head #将原来.head,赋给新插入的对象x.next,就是把原来的头,和新插入x的屁股接在了一起(粗暴理解) if L.head != NULL #如果原来的.head不是NULL L.head.prev = x #则让原来.head的.prev指针 → x。目前新插入对象x与后面的正反向指针都有了。 L.head = x #让新插入的对象x 成为新的.head。 x.prev = NULL #此时让x的左侧指针(指向前方的)为NULL。新head诞生。
insert的时间复杂度为O(1)。
Delete
if x.prev !=NULL #若被删除对象.prev非NULL,也就是不是首个对象 x.prev.next = x.next#则可将 被删除对象.next指针,指向被删除对象.prev的对象.next指针,有点乱。下图中就是4.next → 16.next else L.head = x.next #若被删除对象.prev为NULL,是首个对象的话。则把x.next的指针赋给L.head,令x.next成为链表新的head(没head不行) if x.next != NULL #如果被删除对象.next非NULL,也就是不是最后一个对象 x.next.prev = x.prev#则可将 被删除对象.pre的指针,指向被删除对象.next的对象.prev的指针。下图就是4.prev → 1.prev
Delete的时间复杂度同上,O(1)。
写在最后,如果实在理解不了,去观看电影《人体蜈蚣》,会加深理解。
这篇关于数据结构中的Linked list和Binary tree的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南
- 2024-09-26Springboot微服务资料入门教程