Zehai's Blog

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

0%