python中的 线性表_python线性表

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

一 数组（arryay）一段连续的内存空间

int arr[] = new int(10)  

数组有固定的顺序，有下标:arry[0],arry[9]，因此查询效率高，时间复杂度O（1）

更新（增加，删除）操作效率低：

                        增加：

                                   当需要在数组1中增加或删除元素时，需要创建一个新的数组2

                                  将数组1复制到数组2，再添加新的元素

                                  注：数组1有10个元素内存空间，当需要增加第11个元素时需要创建一                                            个11个元素的内存空间数组2，再将数组1复制到数组2，再添加

                                           第11个元素

                    删除：当删除第9号内存空间的元素时，会将元素以及内存空间一起删除

                                该数组会由连续的数组变为两个数组，为了保证数组的连续性的

                                 特性，需要将第9号内存空间后的内存空间前移

二 链表 

1、指向不bai同：单向链表只有du一个指向下一结点的指针，zhi双向链表除了有一个指dao向下一结点的指针外，还有一个指向前一结点的指针。

2、功能不同：单向链表只能next ，双向链表可以return。

3、单双向不同：单链表只能单向读取，双向链表可以通过prev()快速找到前一结点。

单向链表优缺点：

1、优点：单向链表增加删除节点简单。遍历时候不会死循环；

2、缺点：只能从头到尾遍历。只能找到后继，无法找到前驱，也就是只能前进。

双向链表优缺点：

1、优点：可以找到前驱和后继，可进可退；

2、缺点：增加删除节点复杂，多需要分配一个指针存储空间。

三 栈和队列

    https://blog.csdn.net/shangguanxiu/article/details/128488306?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168189205316800186542797%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=168189205316800186542797&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-2-128488306-null-null.142^v84^wechat,239^v2^insert_chatgpt&utm_term=%E6%A0%88%E7%89%B9%E7%82%B9&spm=1018.2226.3001.4187