我并没有系统的学过数据结构,顶多也就是自己买了本严蔚敏的数据结构看了一下,所以在遇到一些这方面问题就是真的头大,今天看书时发现了Python中collentions.OrderedDict这个模块中有一种内部维持双向链路的有序字典对象,就忽然想去学习一下顺序表,链表的知识.
Python中有有序和无序的数据类型,像set,dict是无序的,而list,tuple是有序的.首先集合和字典是基于哈希表实现,对于这两个类型的理解,我认为集合就是只有键没有值的字典,因为翻阅了下资料,发现Python在最开始时是并没有set这个概念的,最早的set雏形就是{‘a’:None, ‘b’:None}这种字典.还有一个更为奇怪的是,字典本身是无序的,但是使用IDE去输出打印时总会按照我赋值的顺序输出字典,我只能归咎于IDE帮我处理了这个字典,在内存中,这个字典每一组键值对的排列都不是按照我赋值的顺序存储的.
对于有序的list和tuple来说,它们是由顺序表实现的,元组和列表最大的区别有两个,一是元组是不可变类型,即不变的顺序表,它不支持任何改变其内部状态的操作,而列表刚好相反,列表被定义为动态的顺序表,也就是说我可以对其进行appent,inset,pop等操作,另外一个区别是元组是可以去重的,而列表是可以允许有重复元素的.
由于在创建一个顺序表时,需要预先知道数据大小来申请连续的存储空间,而在进行扩充时又会使用copy来开辟一段新的内存空间,所有使用起来并不是很灵活,所以为了充分利用计算机内存空间,实现灵活的动态管理,就得使用到链表.
链表也是一种线性表,但是并不是连续的存储数据,而是每一个节点里存放下一个节点的位置信息,每个节点包含两个域.一个是信息域(用来存放数据),一个是链接域(用来查找下一个节点).
单向链路:
双向链路:
单向链路只能通过前一个节点查找后一节点并且不可逆,双向链路是可逆的,除此之外还有单向循环链路和双向循环链路,也就是tail的地址不再指向None而是head的地址.
但是需要明确的是,链路只是灵活的使用了内存,但付出的代价是增加了地址字段,开销增大,所以说并没有什么完美的算法能够保证又节约时间,又节省空间.