structure

线性表

LinkedList

线性表=数组+链表

线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。

顺序存储 链式存储
典型 数组 链表
物理连续性 连续 分开,靠指针桥接
插入、删除复杂度 O(n) O(1)
查找复杂度 O(1) O(n)

链表=单向链表+双向链表+循环链表等等(为了解决查找复杂度为O(n)的情况,即每次都要从头开始遍历,所以有了双向链表,进一步的把收尾连起来循环,是双向链表的一个进化,能更好的遍历以及利用空间)

1
2
3
4
5
struct ListNode {
int val;
ListNode *next;
ListNode(int val,ListNode *next=NULL):val(val),next(next){}
};

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时候才切换到红黑树,之前用的是拉链法)