[Python算法入门Day4]2.2-2.4 数组和链表 & 选择排序
2.2.4 在中间插入链表在插入元素时，只需要修改上一个元素指向的地址即可
数组在插入元素时，需要将后面的所有元素向后移动
2.2.5 删除
如果想要删除元素链表也是更好的选择,只需要修改上一个元素指向的地址即可
而数组需要把后面的所有元素向前移动
删除元素不同于插入元素.插入元素时如果内存中没有足够的空间，插入操作可能失败,
但任何情况下都可以删除元素
数组 链表
读取O(1) O(n)
插入O(n) O(1)
删除O(n) O(1)
需要指出的是，仅当能够立即访问要删除的元素时，删除操作的运行时间才为O(1)
通常我们会记录第一个元素和最后一个元素所以删除显示时间为O(1)
至于是使用数组还是链表还是要根据不同的情况来定
数组可以支持两种访问方式,第一种是按顺序访问,第二种是随机访问
因为我们知道每个元素的索引位置所以可以随意访问我们想要的元素
链表只有一种访问方式,顺序访问. 因为链表中如果我们想访问下一个元素
我们必须访问这个元素之前的一个元素来获取新的地址不然我们不能访问到新的元素
练习2.2
假设你要为饭店创建一个接受顾客点菜单的应用程序。这个应用
程序存储一系列点菜单。服务员添加点菜单，而厨师取出点菜单并制作
菜肴。这是一个点菜单队列：服务员在队尾添加点菜单，厨师取出队列 开头的点菜单并制作菜肴。
你使用数组还是链表来实现这个队列呢？（提示：链表擅长插入和删除，而数组擅长随机访问。在这个应用程序中，你要执行的是哪些操作 呢？）
我们应该使用链表,因为厨师取出菜单是按照顺序取出，但由于服务员要频繁的在菜单队尾加菜对于数组来说
一直添加新的元素会耗费很长的时间，所以我们选择使用更容易添加元素的链表
2.3 我们来做一个思考实验。假设Facebook记录一系列用户名，每当有用户试图登录Facebook时，都查找其用户名，如果找到就允许用户登
录。由于经常有用户登录Facebook，因此需要执行大量的用户名查找操作。假设Facebook使用二分查找算法，而这种算法要求能够随机访问
——立即获取中间的用户名。考虑到这一点，应使用数组还是链表来存储用户名呢？
我们需要使用数组来完成facebook的登录储存功能。因为大量用户查找的操作有时候需要使用随机访问，
如果只能一个一个挨着查找会慢很多
2.4 经常有用户在Facebook注册。假设你已决定使用数组来存储用户名，
在插入方面数组有何缺点呢？具体地说，在数组中添加新用户将出现什么情况？
如果我们使用数组来存储用户名，每当加入新用户时候我们要考虑内存的空间，如果内存空间不足
则所有数据要迁移到另外的地方。或者这些数据不是插入在队尾的，那么每当插入在中间的时候
所有后面的数据都要往后推移
2.5 实际上，Facebook存储用户信息时使用的既不是数组也不是链表。假设Facebook使用的是一种混合数据：链表数组。
这个数组包含26个元素，每个元素都指向一个链表。例如，该数组的第一个元素指向的链表包含所有以A打头的用户名，第二个元素指向的链表包含所有以B打头的用户名，以此类推。
假设Adit B在Facebook注册，而你需要将其加入前述数据结构中。因此，你访问数组的第一个元素，再访问该元素指向的链表，并将Adit B添加到这个链表末尾。现在假设你要查找Zakhir H。
因此你访问第26个元素，再在它指向的链表（该链表包含所有以z打头的用户名）中查找Zakhir H。
请问，相比于数组和链表，这种混合数据结构的查找和插入速度更慢还是更快？你不必给出大O运行时间，只需指出这种新数据结构的查找和插入速度更快还是更慢
以这种新数据结构查找速度是会变慢的，因为每个数组的元素是链表，假设我们要查询首字母为Z的名称，
那么我们首先要访问数组里面最后一个元素再从链表中去寻找;但是这种新的数据结构插入速度是会更快的
因为每个数据是插入在链表当中，我们只需要修改链表中上一个元素的地址即可
2.3 选择排序
选择排序的运行时间是O(n^2)
2.4 总结:
1.计算机内存犹如一大堆抽屉
2.需要存储多个元素时，可使用数组或链表。
3.数组的元素都在一起。
4.链表的元素是分开的，其中每个元素都存储了下一个元素的地址。
5.数组的读取速度很快。
6.链表的插入和删除速度很快。
7.在同一个数组中，所有元素的类型都必须相同（都为int、double等）。
每日leetcode: 374 Guess Number Higher to Lower
**** Hidden Message *****
{:10_254:} {:5_108:} {:5_108:} {:10_254:} {:10_256:} 停更几天有些事情要处理一下过两天就会恢复日常顺便补发一下福利！ {:5_106:} {:5_109:}
页:
[1]