一、容器、集合
二、数据结构
计算机存储和管理数据的方式
增、删、改、查数据
三、不同数据结构管理数据性能分析
1、数组
image.png
（1）增加
在最后位置，操作1次
在第一个位置，操作n次
（2）删除
在最后位置，操作1次
在第一个位置，操作n次
（3）修改
给定索引，操作1次
（4）查询
根据索引查询，操作1次
根据内容查询，操作n次
2、链表
image.png
（1）增加
只需把元素加到某个地方，让上一个元素存储该元素地址，在该元素地址区域存储下一个元素的地址即可
（2）删除
让存储要删除元素地址的上一个元素，直接存储下一个元素的地址即可
（3）修改
没有索引，只能从头依次寻找再修改，比较复杂
（4）查询
没有索引，只能从头依次寻找，比较复杂
image.png
3、栈
image.png
栈有栈顶和栈底
压栈和出栈都从栈顶
数据存储的特点是先进后出或后进先出
4、队列
image.png
队列有队列头和队列尾
从队列尾进，从队列头出
数据存储的特点是先进先出
四、集合体系树
image.png
数组与集合的不同
1、数组在创建时，必须指定长度
集合在创建时，不用指定长度
2、数组长度一旦确定，就不能更改，更改了长度，就产生了新数组
集合长度可更改，不会产生新的集合
3、数组既可以存储基本数据类型，也可以存引用数据类型
集合只能存引用数据类型（存储基本数据类型不报错，是因为发生了自动装箱）
五、Collection
线性表集合，是个接口
有两个子接口，List和Set
六、List
有序可重复的线性集合，是个接口
有很多实现类，我们着重讲ArrayList和LinkedList
七、ArrayList
底层是数组，有一个兄弟是Vector（底层是数组，线程安全，效率低，因此不太常用）
八、ArrayList源码
1、无参构造方法，为elementData属性赋一个长度为0的数组，即EMPTY_ELEMENTDATA（166行）
2、add方法，调用ensureCapacityInternal方法，并传递值1进去（464行），
3、在ensureCapacityInternal方法内部，先调用calculateCapacity(elementData, minCapacity)方法，再把结果作为参数调用ensureExplicitCapacity方法，此时elementData指向长度为0的数组，minCapacity值是1（233行）
4、在calculateCapacity方法内部判断接收到的elementData是不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个长度为0的数组，如果是，比较DEFAULT_CAPACITY（即10）和minCapacity（即1）哪个是较大的值，得到10，并返回（227行）
5、调用ensureExplicitCapacity方法，并传递10进去（233行）
6、在ensureExplicitCapacity方法内部，让modCount自增1（第一次变为1），判断形参minCapacity与elementData长度是不是大于0，如果是，就调用grow方法，并把minCapacity（即10）传递给grow方法（237行）
7、在grow方法内部，把elementData长度赋给oldCapacity，把1.5倍的数值给了newCapacity变量，判断newCapacity（0）和minCapacity（10）的大小，
如果newCapacity小于minCapacity，newCapacity接收minCapacity的值
如果newCapacity大于2的31次方-9，调用hugeCapacity方法，把minCapacity传进去（258行）
生成新数组，长度为newCapacity（即10），把原有的数组元素复制到从新数组中，并把该数组的地址送到elementData成员变量中
8、以上方法调用完，回到464行，继续执行add方法，此时elementData已经指向了一个长度为10的新数组，把接受的e对象放到数组中，并且成员变量size增加1（464行）
九、遍历集合
1、普通for循环
for(int i = 0;i < list.size();i++) {
System.out.println(list.get(i));
}
2、迭代器
Iterator it = list.iterator();
//判断游标右侧有没有元素
//it.hasNext();
//游标向右移动一次，并且返回跨越的元素
//Object o = it.next();
while(it.hasNext()) {
Object o = it.next();
System.out.println(o);
}
3、增强for循环
for(Object o : list) {
System.out.println(o);
}
4、兰姆达表达式
list.forEach(a -> {
System.out.println(a);
});
以上都是查询，如果在遍历过程中想修改元素，只能通过普通for循环
十、
List集合特点：有序可重复
有序：在集合中存放的顺序和当时存入的顺序一致
可重复：可以存放重复数据
十一、泛型
泛型限定可以放入集合的元素类型
十二、ArrayList存储对象内存图
image.png
十三、如何选择List集合的实现类
对于查询比较多的数据，建议用ArrayList
对于增删比较多的数据，建议用LinkedList
十四、使用集合的习惯
List<User> list = new ArrayList<User>();
作业
1、教务管理系统用list改写
2、用LinkedList模拟栈
3、用LinkedList模拟队列
网友评论