三种常见的链表结构

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