2.1 链表

  链表中的元素可以存储在内存的任何地方（列表或数组在内存中是相连的，紧靠在一起的），链表中每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起.就想寻宝游戏一样，前往第一个地址，上面写着下一个元素的地址，依次找一下。使用链表时，不需要移动元素，假设要为数组分配10000个位置，内存中有10000个位置，但都不靠在一起，这种情况下就无法为该数组分配内存。而链表则可以，相当于链表是分开坐，只要有位置就可以，不用挨在一起。

2.2 数组

  在读取链表的最后一个元素时，不能直接读取，必须先访问元素#1，从中获取#2的地址，在访问元素#2从中获得元素#3的地址，以此类推，直到访问到最后一个元素。如果是同时读取所有元素，链表的效率很高，如果需要跳跃，链表的效率很低。数组与此不同：直到每个元素的地址，因为数组元素存储时地址都是连在一起的。

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等）