2.1 链表
链表中的元素可以存储在内存的任何地方（列表或数组在内存中是相连的，紧靠在一起的），链表中每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起.就想寻宝游戏一样，前往第一个地址，上面写着下一个元素的地址，依次找一下。使用链表时，不需要移动元素，假设要为数组分配10000个位置，内存中有10000个位置，但都不靠在一起，这种情况下就无法为该数组分配内存。而链表则可以，相当于链表是分开坐，只要有位置就可以，不用挨在一起。
2.2 数组
在读取链表的最后一个元素时，不能直接读取，必须先访问元素#1，从中获取#2的地址，在访问元素#2从中获得元素#3的地址，以此类推，直到访问到最后一个元素。如果是同时读取所有元素，链表的效率很高，如果需要跳跃，链表的效率很低。数组与此不同：直到每个元素的地址，因为数组元素存储时地址都是连在一起的。
| 数组 | 链表 | |
|---|---|---|
| 读取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 删除 | O(n) | O(1) |
2.3 插入元素
需要在中间插入元素时，使用链表的话，只用修改它前面那个元素指向的地址，而使用数组时则必须将所有的元素都向后移。如果没有足够的存储空间，可能还得将整个数组复制到其他地方。因此，当需要在中间插入元素时，链表是更好的选择。
2.4 删除元素
删除元素时，链表只需要修改前面一个元素的指向地址即可，而使用数组时，删除元素后，必须将后面的元素都向前移。不同于插入，删除元素总能成功，如果内存中没有足够的空间，插入操作可能失败，但在任何情况下都能将元素删除。
简单排序
def find_small_index(x):
smaller = x[0]
smaller_index = 0
for i in range(1,len(x)):
if x[i]<smaller:
smaller=x[i]
smaller_index=i
return smaller_index
def selectionSort(arr):
newarr=[]
for i in range(len(arr)):
smallest_index = find_small_index(arr)
newarr.append(arr.pop(smallest_index)) #arr.pop会返回出栈后的值，且arr中会删掉出去的值
return newarr
print(selectionSort([1,5,2,9,4,3,11,312,43]))
[1, 2, 3, 4, 5, 9, 11, 43, 312]
- 小结
计算机内存犹如一大堆抽屉
需要存储多个元素时，可使用数组或链表
数组的元素都在一起
链表的元素是分开的，每个元素都存储了下一个元素的地址
数组的读取速度很快
链表的插入和删除速度很快
在同一个数组中，所有的元素类型都必须相同（都为int或double等）
