线性表
LinkedList
线性表=数组+链表
线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。
顺序存储 | 链式存储 | |
---|---|---|
典型 | 数组 | 链表 |
物理连续性 | 连续 | 分开,靠指针桥接 |
插入、删除复杂度 | O(n) | O(1) |
查找复杂度 | O(1) | O(n) |
链表=单向链表+双向链表+循环链表等等(为了解决查找复杂度为O(n)的情况,即每次都要从头开始遍历,所以有了双向链表,进一步的把收尾连起来循环,是双向链表的一个进化,能更好的遍历以及利用空间)
1 | struct ListNode { |
Queue
队列(默认单队列)
循环队列(通过取余,形成逻辑上闭环)rear = (rear - size) % size
- 不以 front = rear 为放满标志,改为 (rear - front) % size = 1
Java-Collection=set+list+queue
Set(HashSet,TreeSet)
无重复元素的数组
HashSet 是哈希表结构,主要利用 HashMap 的 key 来存储元素,计算插入元素的 hashCode 来获取元素在集合中的位置;
TreeSet 是红黑树结构,每一个元素都是树中的一个节点,插入的元素都会进行排序;
##List
在 List 中,用户可以精确控制列表中每个元素的插入位置,另外用户可以通过整数索引(列表中的位置)访问元素,并搜索列表中的元素。 与 Set 不同,List 通常允许重复的元素。 另外 List 是有序集合而 Set 是无序集合。
- ArrayList:数组队列,动态,线程不安全
- vector:矢量队列,和数组类似,线程安全
- linkedList:双向链表
Tree
BST
二叉查找树:binary search tree
左子树上所有结点的值均小于或等于它的根结点的值
右子树上所有结点的值均大于或等于它的根结点的值
左、右子树也分别为二叉排序树(regression)
应用:二分查找O(logn),查找次数等于树的高度
缺点:新插入节点的时候,因为要旋转复杂度较高(引入红黑树的法则降低旋转)
RBT(red black tree)
原名:平衡二叉B树(symmetric binary B-trees)
feature:
- 每个节点都只能是红色或者黑色
- 根节点是黑色
- 每个叶节点(NIL节点,空节点)是黑色的。
- 如果一个结点是红的,则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树带来的优势:
红黑树根到椰子的最长路径不会超过最短路径的2倍
插入或删除,通过feature来调整结构(有的时候不需要调整)
插入默认是红色,调整包括变色和旋转
应用于JDK,Collection中的TreeMap和TreeSet,HashMap(JDK1.8之后用,且阈值大于8时候才切换到红黑树,之前用的是拉链法)