链表中的元素可存储在内存的任何地方。链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。在链表中添加元素很容易：只需将其放入内存，并将其地址存储到前一个元素中，删除也是如此。但是链表在读取上要明显弱于数组，要读取最后一个内存的内容必须要按顺序依次读到最后一个位置为止，数组可以随意读取中间任意位置的内容（因为知道第一块内存地址可以推出第几块地址的位置，他们是连续的）。
数组与链表的操作运行时间
数组和链表哪个用得更多呢？显然要看情况。但数组用得很多，因为它支持随机访问，很多情况都要求能够随机访问，而不是顺序访问。
选择排序比如网易云音乐要根据你听歌的次数排序你喜欢的音乐，可以每次都循环列表，每次取出最高次数的音乐放入新列表，直到原列表为空时结束。则总时间为1/2O（n**2），大O法省略常数，所以也就是时间为O（n**2）。
选择排序的代码：
#O(n**2) def low(arr): lowest=0 arrlow=arr[0] for i1 in range(1,len(arr)): if arr[i1] < arrlow: arrlow=arr[i1] lowest=i1 return lowest def sor(arr): new_arr=[] for i in range(len(arr)): smaller=low(arr) new_arr.append(arr.pop(smaller)) return new_arr print(sor([3,2,9,6,4])) 运行结果： [2, 3, 4, 6, 9]
注：同一数组的元素类型都必须相同。
递归递归指的是调用自己的函数，递归只是让解决方案更清晰，并 没有性能上的优势。实际上，在有些情况下，使用循环的性能更好。Leigh Caldwell在Stack Overflow上说的一句话：“如果使用循环，程序的性能可能更高；如果使用递归，程序可能 更容易理解。如何选择要看什么对你来说更重要。”
基线条件和递归条件编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分：基线 条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己的条件，从而避免形成无限循环。
#递归求阶乘 def fac(num): if num==1: return 1 else: return num*fac(num-1) print(fac(5)) 运行结果： 120
#递归叠加 def ad(lis): if lis==[]: return 0 else: return lis.pop(0)+ad(lis) print(ad([1,2,3])) 运行结果： 6
#递归计数 def num(lis): n=0 if lis ==[]: return n else: lis.pop() n+=1 n+=num(lis) return n print(num([1,2,3,4,5])) 运行结果： 5
#递归求最大值 def ma(lis): m=lis[0] if len(lis) ==1: return m else: tmp=ma(lis[1:]) if tmp > m: m=tmp return m print(ma([7,3,10,4,6])) 运行结果： 10 堆与栈
这个概念大家一定都比较清楚，这是经常使用的两种编程概念，堆也叫队列，指的是先进先出，栈则相反指的是后进先出，可以想一想Python中的嵌套函数的调用，里层的函数是后定义的但是却先执行完，执行完有返回外层函数，这个调用函数就是调用栈的概念。规范的说他们只有压入和弹出两种状态。