JAVA进阶知识学习-day03 数据结构&List集合&Set集合

一、数据结构

1.1 常见的数据结构——栈

1.1.1 栈的特点：先进后出（存进去的元素，要在后它后面的元素依次取出后，才能取出该元素）

1.1.2 栈的常用名词：

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

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

1.1.3 栈的图示：

1.2 常见的数据结构——队列

1.2.1 队列的特点：先进先出（存进去的元素，要在后它前面的元素依次取出后，才能取出该元素）

1.2.2 队列的图示：

1.3 常见的数据结构——数组

1.3.1 数组的特点：查询快，增删慢

1.4 常见的数据结构——链表

1.4.1 链表的特点：查询慢，增删快

1.4.2 链表的结构：链表由一系列结点node（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

1.5 常见的数据结构——红黑树

1.5.1 概念： 二叉树是每个结点不超过2的有序树，简单的理解，就是一种类似于我们生活中树的结构，只不过每个结点上都最多只能有两个子结点。 二叉树是每个节点最多有两个子树的树结构。顶上的叫根结点，两边被称作“左子树”和“右子树”，红黑树本身就是一颗二叉查找树。

1.5.2 二叉树图示：

1.5.3 红黑树的约束：

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

2. 根节点是黑色的

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

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

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

1.5.4 红黑树的特点：查询速度特别快,查找叶子元素最少和最多次数不多于二倍

二、 List集合

2.1 java.util.List接口继承自Collection接口，是单列集合的一个重要分支，习惯性地会将实现了List接口的对象称为List集合。

2.2 List接口特点：

1. 它是一个元素存取有序的集合。

2. 它是一个带有索引的集合，通过索引就可以精确的操作集合中的元素（与数组的索引是一个道理）

3. 集合中可以有重复的元素，通过元素的equals方法，来比较是否为重复的元素。

2.3 List接口常用方法：

public void add(int index, E element) : 将指定的元素，添加到该集合中的指定位置上。 public E get(int index) :返回集合中指定位置的元素。

public E remove(int index) : 移除列表中指定位置的元素, 返回的是被移除的元素。 public E set(int index, E element) :用指定元素替换集合中指定位置的元素,返回值的更新前的元素。

三、 List的子类

3.1 java.util.ArrayList集合数据存储的结构是数组结构。元素增删慢，查找快，由于日常开发中使用最多的功能为查询数据、遍历数据，所以ArrayList是最常用的集合。

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

3.2.1 LinkedList常用方法：

public void addFirst(E e) :将指定元素插入此列表的开头。

public void addLast(E e) :将指定元素添加到此列表的结尾。

public E getFirst() :返回此列表的第一个元素。

public E getLast() :返回此列表的最后一个元素。

public E removeFirst() :移除并返回此列表的第一个元素。

public E removeLast() :移除并返回此列表的最后一个元素。

public E pop() :从此列表所表示的堆栈处弹出一个元素。

public void push(E e) :将元素推入此列表所表示的堆栈。

public boolean isEmpty() ：如果列表不包含元素，则返回true。

四、Set接口

4.1 java.util.Set接口和java.util.List接口一样，同样继承自Collection 接口，它与 Collection 接口中的方 法基本一致，并没有对 Collection 接口进行功能上的扩充，只是比 Collection 接口更加严格了。

4.2 Set接口特点：

1、Set接口中元素无序

2、Set接口中元素不能重复

3、Set集合取出元素的方式可以采用迭代器和增强for

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

4.3.1 HashSet是根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存取和查找性能。保证元素唯一性的方式依赖于：hashCode与equals方法。

4.3.2 HashSet集合存储数据的结构（哈希表）：哈希表是由数组+链表+红黑树实现的，如下图所示：

保证HashSet集合元素的唯一， 其实就是根据对象的hashCode和equals方法来决定的。如果我们往集合中存放自定义的对象，那么保证其唯一， 就必须复写hashCode和equals方法建立属于当前对象的比较方式。

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

4.4.1 重写hashCode和equals方法代码实现如下：

4.5 可变参数：如果我们定义一个方法需要接受多个参数，并且多个参数类型一致，我们可以对其简化成如下格式：

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

... 用在参数上，称之为可变参数

4.5.1 使用举例：

public static int getSum(int... arr) {}

4.5.2 注意事项：如果在方法书写时，这个方法拥有多参数，参数中包含可变参数，可变参数一定要写在参数列表的末尾位置。

五、Collections

5.1 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> ) :将集合中元素按照指定规则排

序。