java、python之动态数组、链表与列表

126 2024-02-28 10:38

三种常见的链表结构

1、单链表
2、循环链表
3、双向链表
单链表

链表通过指针将一组零散的内存块串联在一起。把内存块称为链表的“结点”。为了将所有的结点串起来,每个链表的结点除了存储数据之外,还需要记录链上的下一个结点的地址。把这个记录下个结点地址的指针叫做后继指针next。第一个结点叫做头结点,最后一个结点叫做尾结点。头结点用来记录链表的基地址,有了头结点,就可以遍历整条链表,而尾结点特殊的地方是:指针不是指向下一个结点,而是指向一个空地址NULL,表示这是链表上最后一个结点。


单链表的插入和删除操作,只需要考虑相邻结点的指针改变,所以对应的时间复杂度是O(1)。链表随机访问的时间复杂度为O(n)。
循环链表

循环链表和单链表的区别就是尾结点。循环链表的最后一个结点指向链表的头结点。
循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时,就适合采用循环链表。


双向链表

单链表只有一个方向,结点只有一个后继指针next指向后面的结点。而双向链表支持两个方向,每个结点不止有一个后继指针next指向后面的结点,还有一个前驱指针prev指向前面的结点。
双向链表需要额外两个空间存储后继结点和前驱结点的地址。所以存储同样多的数据,双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间,但可以支持双向遍历,这样也带来了双向链表操作的灵活性。

双向链表可以支持O(1)时间复杂度的情况下找到前驱结点,所以双向链表在某些情况下的插入,删除等操作都要比单链表简单高效。
 

尽管双向链表占用内存空间要比单链表要大,实际应用却比单链表更广泛。采用了空间换时间的思想。当内存空间充足 的时候,如果追求代码的执行速度,就可以选择空间复杂度相对较高,时间复杂度相对较低的数据结构。相反,如果内存比较紧缺,比如代码跑在手机或单片机上,这个时候,就要反过来用时间换空间的设计思路。

缓存就是利用了空间换时间的设计思想。如果把数据存储在硬盘上,会比较节省内存,但每次查找数据都要进行一次磁盘的IO操作,会比较慢。如果通过缓存技术,事先将数据加载到内存中,虽然会比较耗费内存空间,但是每次数据查询的速度就大大提高了。
 

双向链表和循环链表相结合就是双向循环链表。
在这里插入图片描述
链表和数组的对比

数组和链表是两种不同的内存组织方式,因为内存存储的区别,所以插入,删除,随机访问操作的时间复杂度正好相反。


1、数组是连续的内存空间,可以借助CPU的缓存机制,预读数组中的数据,所以访问效率更高,而链表在内存中并不是连续存储,所以对CPU缓存不友好,没有办法有效预读。
数组的缺点是大小固定,声明时就需要指定大小。如果声明的数组过大,系统可能没有足够的连续内存空间分配给它,导致内存不足。如果声明的数组过小,可能会出现不够用的情况,只能再申请一个更大的内存空间把原数据拷贝进去,非常耗时。

2、链表本身没有大小的限制,支持动态扩容。虽然java中有ArrayList容器也支持扩容,但是当我们往支持动态扩容的数组中插入一个数据时,如果数组中没有空闲空间了,会申请一个更大的空间,将数据拷贝进去,拷贝数据的过程也是非常耗时的。
————————————————

                            版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
                        
原文链接:https://blog.csdn.net/Sophia_0331/article/details/106382844

 

 

Python list的底层原理是使用动态数组实现的。动态数组是一种数组类型,它可以在运行时动态分配内存空间,以容纳不断增长的元素。当数组的容量不足时,动态数组会自动分配更多的内存空间,以容纳更多的元素。由于动态数组的实现,Python list可以快速访问数据,时间复杂度为O(1)。
————————————————

                            版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
                        
原文链接:https://blog.csdn.net/zhouruifu2015/article/details/130751590

全部评论

·