常见数据结构:

栈：stack,又称堆栈，它是运算受限的线性表，其限制是仅允许在标的一端进行插入和删除操作，不                允许在其他任何位置进行添加、查找、删除等操作.

    该结构的集合，对元素的存取有如下的特点:

先进后出

压站:就是存元素,把元素存储到栈的顶端位置，栈中已有元素依次向栈底方向移动一个位置

弹栈:就是取出元素,把栈的顶端位置元素取出，栈中已有元素依次向栈顶方向移动一个位置

      栈的入口、出口的都是栈的顶端位置

队列：queue,简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入， 而在表的另一端进行删除

    特点：

先进先出--存进去的元素，要在后它前面的元素依次取出后，才能取出该元素

队列的入口、出口各占一侧

数组:Array,是有序的元素序列，数组是在内存中开辟一段连续的空间，并在此空间存放元素。就像是一排出租屋,有100个房间,从001到100每个房间都有固定编号，通过编号就可以快速找到租房子的人.

查找元素快：通过索引，可以快速访问指定位置的元素

增删元素慢:需要创建一个新数组，将指定新元素存储在指定索引位置，再把原数组元素根 据索引，复制到新数组对应索引的位置

链表:linked list,由一系列节点node（链表中每一个元素称为节点）组成，节点可以在运行时动态生成.每 个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域. 链表结构有单向链表与双向链表.

多个节点之间,通过地址进行连接.例如,多个人手拉手,每个人使用自己的右手拉住下个人的左手,依次类推,这样多个人就连在一起了

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

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

红黑树:

红黑树的特点:

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

红黑树的约束:

1. 节点可以是红色的或者黑色的

2. 根节点是黑色的

3. 叶子节点(特指空节点)是黑色的

4. 每个红色节点的子节点都是黑色的

5. 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同

List接口的特点:

·有序的集合,存储元素和取出元素的顺序是一致的 (存2,1,3  取2,1,3)

·有索引,包含了一些带索引的方法

·允许存储重复的元素

List接口中带元素索引的方法(特有方法):(操作的时候注意索引越界异常)

public void add(int index, E element): 将制定的元素,添加到该集合中的指定位置上(讲内容 element 添加在索引 index 前面)

public E get(int indext): 返回集合中指定位置的元素

public  E remove(int  index): 移除列表中指定位置的元素,返回被移除的元素(在遍历集合中移除元素的时候,被移除元素之后的索引都会改变-1)

public E set(int index, E element): 用指定元素替换集合中指定位置的元素,返回值为更新前的元素

HashSet:

      java.util.HashSet 是 Set 接口的一个实现类，它所存储的元素是不可重复的，并且元素都是无序的(即存取顺序 不一致)

      java.util.HashSet 底层的实现其实是一个 java.util.HashMap 支持，由于我们暂时还未学习，先做了 解

      HashSet 是根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存取和查找性能.

      保证元素唯一性的方式依赖于： hashCode 与 equals 方法

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

LinkedHashSet:

      在HashSet下面有一个子类 java.util.LinkedHashSet ，它是链表和哈希表组合的一个数据存储结构

HashSet集合保证添加元素不重复的原理:

      调用 add(E e) 添加元素时, 先调用 hashCode() 获取哈希值, 和当前HashSet集合中的元素比较

        如果哈希值不同, 则认为元素不重复, 添加, 并返回true

        如果哈希值相同, 则可能是哈希冲突, 所以继续调用元素的 equals() 方法和所有哈希值相同的元素比较

        如果 equals() 比较所有元素都没有相同的, 则认为元素不重复, 添加, 并返回true

        如果 equals() 比较出有相同的元素, 则认为元素重复, 不添加, 并返回false

可变参数:

        JDK 5 出现. 指同一个类型的参数, "个数可变"

        可变参数的本质就是一个"数组"

修饰符 返回值类型 方法名(参数类型... 形参名){  }

||

        修饰符 返回值类型 方法名(参数类型[] 形参名){  }

后面这种定义，在调用时必须传递数组，而前者可以直接传递数据即可

        格式: 用在方法的参数中

            修饰符 返回值类型 方法名(int... 变量名) {

                    // 可以直接将 变量名 当作 数组名 使用

            }

            方法名();

注意事项:

        1. 可变参数可以传递的参数个数, 可以是 0个, 1个, 多个

        2. 一个方法的参数列表中, 只能有一个可变参数

        3. 如果方法的参数有多个, 可变参数必须写在参数列表的最后

4.可变参数可以当做一个数组

java.utils.Collections 是集合工具类，用来对集合进行操作.部分方法如下：

public static <T> boolean addAll(Collection<T> c, T... elements) :往集合中添加一些元素  参数可以是多态对象

public static void shuffle(List<?> list) 打乱顺序 :打乱集合顺序

public static <T> void sort(List<T> list) :将集合中元素按照默认规则排序 升序

public static <T> void sort(List<T> list，Comparator<? super T> ) :将集合中元素按照指定规则排 序

Comparable：强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序，类的compareTo方法 被称为它的自然比较方法。只能在类中实现compareTo()一次，不能经常修改类的代码实现自己想要的排序。实现 此接口的对象列表（和数组）可以通过Collections.sort（和Arrays.sort）进行自动排序，对象可以用作有序映射中 的键或有序集合中的元素，无需指定比较器。

Comparator:强行对某个对象进行整体排序。可以将Comparator 传递给sort方法（如Collections.sort或 Arrays.sort），从而允许在排序顺序上实现精确控制。还可以使用Comparator来控制某些数据结构（如有序set或 有序映射）的顺序，或者为那些没有自然顺序的对象collection提供排序

常见数据结构:

栈：stack,又称堆栈，它是运算受限的线性表，其限制是仅允许在标的一端进行插入和删除操作，不                允许在其他任何位置进行添加、查找、删除等操作.

    该结构的集合，对元素的存取有如下的特点:

先进后出

压站:就是存元素,把元素存储到栈的顶端位置，栈中已有元素依次向栈底方向移动一个位置

弹栈:就是取出元素,把栈的顶端位置元素取出，栈中已有元素依次向栈顶方向移动一个位置

      栈的入口、出口的都是栈的顶端位置

队列：queue,简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入， 而在表的另一端进行删除

    特点：

先进先出--存进去的元素，要在后它前面的元素依次取出后，才能取出该元素

队列的入口、出口各占一侧

数组:Array,是有序的元素序列，数组是在内存中开辟一段连续的空间，并在此空间存放元素。就像是一排出租屋,有100个房间,从001到100每个房间都有固定编号，通过编号就可以快速找到租房子的人.

查找元素快：通过索引，可以快速访问指定位置的元素

增删元素慢:需要创建一个新数组，将指定新元素存储在指定索引位置，再把原数组元素根 据索引，复制到新数组对应索引的位置

链表:linked list,由一系列节点node（链表中每一个元素称为节点）组成，节点可以在运行时动态生成.每 个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域. 链表结构有单向链表与双向链表.

多个节点之间,通过地址进行连接.例如,多个人手拉手,每个人使用自己的右手拉住下个人的左手,依次类推,这样多个人就连在一起了

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

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

红黑树:

红黑树的特点:

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

红黑树的约束:

1. 节点可以是红色的或者黑色的

2. 根节点是黑色的

3. 叶子节点(特指空节点)是黑色的

4. 每个红色节点的子节点都是黑色的

5. 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同

List接口的特点:

·有序的集合,存储元素和取出元素的顺序是一致的 (存2,1,3  取2,1,3)

·有索引,包含了一些带索引的方法

·允许存储重复的元素

List接口中带元素索引的方法(特有方法):(操作的时候注意索引越界异常)

public void add(int index, E element): 将制定的元素,添加到该集合中的指定位置上(讲内容 element 添加在索引 index 前面)

public E get(int indext): 返回集合中指定位置的元素

public  E remove(int  index): 移除列表中指定位置的元素,返回被移除的元素(在遍历集合中移除元素的时候,被移除元素之后的索引都会改变-1)

public E set(int index, E element): 用指定元素替换集合中指定位置的元素,返回值为更新前的元素

HashSet:

      java.util.HashSet 是 Set 接口的一个实现类，它所存储的元素是不可重复的，并且元素都是无序的(即存取顺序 不一致)

      java.util.HashSet 底层的实现其实是一个 java.util.HashMap 支持，由于我们暂时还未学习，先做了 解

      HashSet 是根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存取和查找性能.

      保证元素唯一性的方式依赖于： hashCode 与 equals 方法

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

LinkedHashSet:

      在HashSet下面有一个子类 java.util.LinkedHashSet ，它是链表和哈希表组合的一个数据存储结构

HashSet集合保证添加元素不重复的原理:

      调用 add(E e) 添加元素时, 先调用 hashCode() 获取哈希值, 和当前HashSet集合中的元素比较

        如果哈希值不同, 则认为元素不重复, 添加, 并返回true

        如果哈希值相同, 则可能是哈希冲突, 所以继续调用元素的 equals() 方法和所有哈希值相同的元素比较

        如果 equals() 比较所有元素都没有相同的, 则认为元素不重复, 添加, 并返回true

        如果 equals() 比较出有相同的元素, 则认为元素重复, 不添加, 并返回false

可变参数:

        JDK 5 出现. 指同一个类型的参数, "个数可变"

        可变参数的本质就是一个"数组"

修饰符 返回值类型 方法名(参数类型... 形参名){  }

||

        修饰符 返回值类型 方法名(参数类型[] 形参名){  }

后面这种定义，在调用时必须传递数组，而前者可以直接传递数据即可

        格式: 用在方法的参数中

            修饰符 返回值类型 方法名(int... 变量名) {

                    // 可以直接将 变量名 当作 数组名 使用

            }

            方法名();

注意事项:

        1. 可变参数可以传递的参数个数, 可以是 0个, 1个, 多个

        2. 一个方法的参数列表中, 只能有一个可变参数

        3. 如果方法的参数有多个, 可变参数必须写在参数列表的最后

4.可变参数可以当做一个数组

java.utils.Collections 是集合工具类，用来对集合进行操作.部分方法如下：

public static <T> boolean addAll(Collection<T> c, T... elements) :往集合中添加一些元素  参数可以是多态对象

public static void shuffle(List<?> list) 打乱顺序 :打乱集合顺序

public static <T> void sort(List<T> list) :将集合中元素按照默认规则排序 升序

public static <T> void sort(List<T> list，Comparator<? super T> ) :将集合中元素按照指定规则排 序

Comparable：强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序，类的compareTo方法 被称为它的自然比较方法。只能在类中实现compareTo()一次，不能经常修改类的代码实现自己想要的排序。实现 此接口的对象列表（和数组）可以通过Collections.sort（和Arrays.sort）进行自动排序，对象可以用作有序映射中 的键或有序集合中的元素，无需指定比较器。

Comparator:强行对某个对象进行整体排序。可以将Comparator 传递给sort方法（如Collections.sort或 Arrays.sort），从而允许在排序顺序上实现精确控制。还可以使用Comparator来控制某些数据结构（如有序set或 有序映射）的顺序，或者为那些没有自然顺序的对象collection提供排序