数组
数组的存储空间在内存空间中是连续的,执行插入、删除操作需要移动后续元素,对应操作的时间复杂度:
-
prependO(1) -
appendO(1) -
lookupO(1) -
insertO(n) -
deleteO(n)
链表
链表中节点之间通过next或者pre指针关联,执行插入、删除操作比较方便,但是链表的查找不会想数组那么轻松
-
prependO(1) -
appendO(1) -
lookupO(n) -
insertO(1) -
deleteO(1)
跳表
- 建立在链表基础之上,并且链表元素必须要是有序的,跳表对应的是平衡树、二分查找
- 在有序的链表上,为了提高链表的查找效率,可以通过升维的方式,添加一级索引,二级索引..的方式提高查询效率
- 时间复杂度O(log n)
- 空间复杂度O(n)
树
链表的一个节点只有一个next指针,如果有两个next或者多个指针,那么就形成树,有两个next指针的称为二叉树
图
如果树状结构中存在环,那么就称为图,树是一种特殊的图
二叉搜索树
- 又称二叉搜索排序树,有序二叉树,
- 是一个
空树,或者中序遍历结果为升序 - 时间复杂度O(log n)
- 删除操作如果是删除的子树的根节点,那么一般把大于该节点的第一个节点拿上来填充
- 中序遍历为升序
