• array
  • 链表
  • hash map
  • set
  • 红黑树

array

数组又叫顺序表,在内存中存储空间是连续的,允许用户对其进行插入,删除,访问和替换等等。Python中的列表是由对其它对象的引用组成的连续数组。

append复杂度为O(1),insert复杂度为O(n),sort复杂度:O(nlogn)。

链表

链表数据存储空间未必是连续的,在插入或删除的时候,只需要改变指针的指向,其他都是不变的。链表的空间不需要提前分配,链表只能顺序访问,无法实现随机访问。

hash map

哈希表的关键思路在于建立存储对象和地址之间的联系,这个联系即哈希函数。通过哈希函数算出对象的地址。dict类似对key进行了hash,然后再对hash生成一个红黑树进行查找,其查找复杂其实是O(logn),O(1)是理想情况。

建立hash map的过程哈希值可能存在冲突,可用的解决方案是:链式地址法,开放定址法,线行探查法,平方探查法等。

set

set本质上是一颗红黑树

红黑树

红黑树是一棵自平衡二叉查找树,二叉查找树满足左子树节点小于根节点,右子树节点大于根节点。

红黑树的定义和性质:

  • 红黑树每个节点要么是红色,要么是黑色
  • 根节点是黑色
  • 子节点是黑色
  • 红色节点两个子节点都是黑色的
  • 如果一个节点存在一个子黑节点,那么一定会有两个黑色子节点