Python 数据结构

数组和单链表 单链表结构与顺序存储结构(数组)优缺点：我们分别从存储分配方式、时间性能、空间性能三方面来做对比。 数据结构存储分配方式时间性能空间性能数组数组结构用一段连续的存储单元依次存储线性表的数据元素。a.查找修改数组O(1) b.插入和删除 数组需要平均移动表长一半的元素，时间为O(n)数组需要预分配存储空间，分大了，容易造成空间浪费，分小了，容易发生溢出。链表单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。a.查找修改单链表O(n) b.插入和删除单链表在计算出某位置的指针后，插入和删除时间仅为O(1)单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。 结论： 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。 队列 队列的定义： 队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列是一种先进先出（First In First Out, FIFO）的线性表。 时间性能 循环队列和链队列的基本操作都需要常数时间O (1)。 空间性能 循环队列：必须预先确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题。链队列：没有队列满的问题，只有当内存没有可用空间时才会出现队列满，但是每个元素都需要一个指针域，从而产生了结构性开销。 栈 最开始栈中不含有任何数据，叫做空栈，此时栈顶就是栈底。然后数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大。数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小。 时间性能 无论是顺序栈还是链式栈，这两种栈在push和pop操作上均很比较简单，时间复杂度均为O(1)。 空间性能 顺序栈：必须预先确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题。链式栈：没有队列满的问题，只有当内存没有可用空间时才会出现队列满，但是每个元素都需要一个指针域，从而产生了结构性开销。 哈希表 哈希表（hash table）也叫作散列表，这种数据结构提供了键（key）和值（value）的映射关系。只要给出一个key，就可以高效查找到它所匹配的value。 在python语言中，哈希表对应的集合叫做字典（dict）。 时间性能 读写操作的时间复杂度接近O(1)。哈希冲突： 由于哈希算法被计算的数据是无限的，而计算后的结果范围有限，因此总会存在不同的数据经过计算后得到的值相同，这就是哈希冲突。 通过链表法来解决哈希冲突，链接地址法的思路是将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。