数组

数组的存储空间在内存空间中是连续的,执行插入、删除操作需要移动后续元素,对应操作的时间复杂度:

• prepend O(1)
• append O(1)
• lookup O(1)
• insert O(n)
• delete O(n)

链表

链表中节点之间通过next或者pre指针关联,执行插入、删除操作比较方便,但是链表的查找不会想数组那么轻松

• prepend O(1)
• append O(1)
• lookup O(n)
• insert O(1)
• delete O(1)

跳表

• 建立在链表基础之上,并且链表元素必须要是有序的,跳表对应的是平衡树、二分查找
• 在有序的链表上,为了提高链表的查找效率,可以通过升维的方式,添加一级索引,二级索引..的方式提高查询效率
• 时间复杂度O(log n)
• 空间复杂度O(n)

树

链表的一个节点只有一个next指针,如果有两个next或者多个指针,那么就形成树,有两个next指针的称为二叉树

图

如果树状结构中存在环,那么就称为图,树是一种特殊的图

二叉搜索树

• 又称二叉搜索排序树,有序二叉树,
• 是一个空树,或者中序遍历结果为升序
• 时间复杂度O(log n)
• 删除操作如果是删除的子树的根节点,那么一般把大于该节点的第一个节点拿上来填充
• 中序遍历为升序