01类集概述

为了方便用户操作各种类型的数据结构，Java提供了可以直接拿来使用的类。
类集中最大的也是最重要的三个接口：Collection（单值）、Map（双值）、Iterator（迭代器）。
所有类集操作的类或接口都在java.util包里。
Java类集结构图：

02常见数据结构

一、栈

概念

栈是限定仅在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。

特点

1.先进后出：最先进去的最后出来。
2.入口和出口都是栈顶位置。

名词

1.压栈：存元素
2.弹栈：取元素

概念图

二、 队列

概念

队列简称队，是一种特殊的（运算受限制）线性表，只允许在表的一端进行插入，另一端进行删除。
队尾（rear）是允许插入的一端，队头（front）是允许删除的一端，不含任何数据元素的队列称为空队列。
包含单端队列和双端队列两种。

特点

1.先进先出：谁先进来，谁先出去。
2.队列的入口和出口各占一侧。

概念图

三、数组

概念

数组是占用了一块连续内存空间的有序的存放元素的序列。

特点

1.查找元素快：通过索引可以快速访问指定位置的元素。
2.增删元素慢：需要创建新的数组根据索引进行覆盖。

四、链表

概念

链表由一系列结点（链表中的每一个元素叫做结点）组成，结点可以在运动时动态生成，每个结点包括两部分：数据域和指针域（指向下一个结点的位置）。

特点（主要介绍单向链表）

1.多个结点之间通过地址进行连接
2.查找元素慢：想找某个元素需要通过连接的结点依次往后寻找。
3.增删元素快：直接将指针域修改为需要连接下个元素的地址。

拓展（作为详细了解）

戳链接:https://www.cnblogs.com/qianguyihao/p/4761593.html

五、二叉树

概念

二叉树指每个结点不超过2个的有序树。顶上的结点叫作根节点，两边被称作“左子树”和“右子树”。

拓展（红黑树）

戳链接:https://www.cnblogs.com/tiancai/p/9072813.html

03Collection接口

概念

Collection是在整个Java类集中保存单值的最大操作父接口，里面每次操作的时候都只能保存一个对象的数据，此接口定义在java.util包中。
开发中使用其操作的子接口List（允许存放重复元素）、Set（不允许存放重复元素）

定义

public interface Collection extends Iterable（使用了泛型技术）

常用方法（详见API）

04Collection子接口一之List接口

定义

public interface List extends Collection

相继Collection接口的扩充方法

05List集合下的实现类一之ArrayList

概念

ArrayList使用的是数组结构存储数据，增删慢，查找快。

定义

ArrayList 对象名 = new ArrayList<>();（无参构造时）

解析

1.ArrayList的三种构造方法
–ArrayList() //默认无参的构造容量为10，实际最开始的长度为0，每次扩容是变成1.5倍的容量
–ArrayList​(int initialCapacity)：当需要存储的数据较多，建议用一参构造方法来设置初始化容量值，否则频繁扩容会浪费大量的内存
–ArrayList​(Collection<? extends E> c)
2.每次扩容变成1.5倍的容量？
源码查看：写一个add方法点击源码add查看–>add(,)–>grow()–>grow(带参)–>newCapacity

常见面试题

1.ArrayList通过无参构造的集合对象在开始时长度为多少？

答：0（并非10）
解析：源码查看：无参构造–>DEFAULTCAPACITY_EMPTY_ELEMENTDATA–>此数组为空，即长度为0 无参构造里的this.elementData（存数据的数组）

2.ArrayList对象的添加方法返回值是什么？

答：只能是True
解析：写一个add方法点击源码查看