【成都校区】第三天小结 - 黑马程序员技术交流社区

数据存储的常用结构有：栈、队列、数组、链表和红黑树。

栈：stack,又称堆栈，先进后出。（压栈：就是存元素。弹栈：就是取元素。）

数组特点：查找元素快（通过索引，可以快速访问指定位置的元素），增删元素慢。

链表:linked list,由节点（链表中每一个元素称为结点）组成，每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。多个结点之间，通过地址进行连接。

链表特点：查找元素慢：想查找某个元素，需要通过连接的节点，依次向后查找指定元素。

增删元素快：增删元素只需要修改连接下个元素的地址即可。

红黑树：二叉树：binary tree ,是每个结点不超过2的有序树（tree）。红黑树本身就是一颗二叉查找树。

红黑树的约束: 1. 节点可以是红色的或者黑色的 2. 根节点是黑色的

3. 叶子节点(特指空节点)是黑色的 4. 每个红色节点的子节点都是黑色的 5. 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同。

速度特别快,趋近平衡树,查找叶子元素少和多次数不多于二倍。

List接口继承自 Collection接口，是单列集合的一个重要分支，。在List集合中允许出现重复的元素，，List集合还有一个特点就是元素有序，元素的存入顺序和取出顺序一致。

List集合的子类集合：ArrayList集合和 LinkedList集合

ArrayList集合数据存储的结构是数组结构。元素增删慢，查找快。

LinkedList 集合数据存储的结构是链表结构。方便元素添加、删除的集合。

Set接口也是继承于 Collection接口，Set接口中元素无序，并且都会以某种规则保证存入的元素不出现重复。

HashSet是根据对象的哈希值来确定元素在集合中的存储位置。

给HashSet中存放自定义类型元素时，需要重写对象中的hashCode和equals方法，才能保证HashSet集合中的对象唯一。

可以保证元素存放进去的顺序是有序的

Collection是集合工具类，用来对集合进行操作。Comparator 比较器

是将集合中元素按照默认规则排序，存贮的是的字符串类型。

Comparable：强行对实现它的每个类的对象进行整体排序。可以通过Collections.sort（和Arrays.sort）进行自动排序。。只能在类中实现compareTo()一次。

Comparator强行对某个对象进行整体排序。可以将Comparator 传递给sort方法（如Collections.sort或 Arrays.sort），从而允许在排序顺序上实现精确控制。