前言：
上次我们谈到了数据结构的一大特殊参数化类型——>泛型。
首先，我们要明确，数据结构中有三个重要组成： 逻辑结构、存储结构、数据运算 。
逻辑结构：指的是数据之间的逻辑关系，从逻辑关系上去描述数据。逻辑结构包括线性结构和非线性结构两种。其中包括集合、线性结构、树形结构、图形结构。
逻辑结构是一种“依赖关系”，描述的仅仅是数据元素之间的关系，除了描述数据元素之间的关系外，再也没有其他的含义了。
特别注意：逻辑结构与存储结构无关。
存储结构：也称为数据的物理结构，是数据元素及其关系在计算机中的存储方式，有：顺序存储、链式存储、散列存储和索引存储。
数据运算：是对数据依某种模式而建立起来的关系进行处理的过程。是指对数据实施的操作，数据运算最终需要在对立的存储结构上用算法实现，所以数据运算分为运算定义和运算实现两个层面。（这里我们暂不深究。
那么，逻辑结构中的线性表又是什么呐？
1、线性表
线性表：指的是N个具有相同特性的数据元素的有限序列。
线性表在逻辑结构中呈现线性结构，也就是说它是一条连续的直线。
但是，线性表在物理结构上（也就是说在存储结构上）并不一定是连续的，线性表在物理上存储时，通常会以数组和链式结构的形式进行存储。
2、顺序表
顺序表：是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
也就是说顺序表的底层其实是一个动态的数组。
ArrayList底层其实是一个动态的数组，称为顺序表。
2.1 接口的实现
public class MyArrayList {
public int[] elem;//数组
public int usedSize;//记录有效元素的个数
public static final int DEFAULT_SIZE=10;
public MyArrayList(){
this.elem=new int[DEFAULT_SIZE];
}
// 新增元素,默认在数组最后新增
public void add(int data) {
//考虑越界和扩容
//1.检查当前顺序表是不是满了
if(isFull()){
//2.如果满了就要进行扩容
this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
}
//3.
this.elem[this.usedSize]=data;
//4.
this.usedSize++;
}
public boolean isFull(){
if(size()>=this.elem.length){
return true;
}
return false;
}
// 在 pos 位置新增元素
public void add(int pos, int data) throws PosWrongfulException {
//1.下标为负数
//2.下标超过了数组的长度
//3.满
//4.不能隔着元素放 要存储的位置前面一定是有元素的
if(isFull()){
System.out.println("满了");
this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
}
if(pos<0||pos>this.usedSize){
System.out.println("注意：pos位置不合法!!!");
throw new PosWrongfulException("注意：pos位置不合法!!!");
}
//pos合法
//1.开始挪动数据
for (int i = this.usedSize-1; i >=pos ; i--) {
this.elem[i+1]=this.elem[i];
}
//2.插入数据
this.elem[pos]=data;
//3.usedSize++
this.usedSize++;
}
//判断是否包含某个元素
public boolean contains(int toFind) {
for (int i = 0; i < this.size(); i++) {
if(this.elem[i]==toFind){
return true;
}
}return false;
}
// 查找某个元素对应的位置
public int indexOf(int toFind) {
for (int i = 0; i < this.size(); i++) {
if(this.elem[i]==toFind){
return i;
}
}return -1;
}
// 获取 pos 位置的元素
public int get(int pos) {
if(isEmpty()){
throw new EmptyException("注意:当前顺序表为空!!!");
}
if(pos<0||pos>=this.usedSize){
throw new PosWrongfulException("注意:当前pos位置不合法！！！");
}
return this.elem[pos];
}
public boolean isEmpty(){
return size()==0;
}
// 给 pos 位置的元素更新为value
public void set(int pos, int value) {
//1.pos是否越界
if(isEmpty()){
throw new EmptyException("注意:当前顺序表为空!!!");
}
if(pos<0||pos>=this.usedSize){
throw new PosWrongfulException("注意:当前pos位置不合法！！！");
}
this.elem[pos]=value;
}
// 删除第一次出现的关键字key
public void remove(int key) {
//空的顺序表没有key
if(isEmpty()){
throw new EmptyException("注意:当前顺序表为空!!!");
}
//1.先找到key，知道下标
int num=this.indexOf(key);
if(num==-1){
System.out.println("没有这个数字");
return;
}//2.挪动数据
for (int i = num; i < size()-1; i++) {
this.elem[i]=this.elem[i+1];
}
//3.usedSize--
usedSize--;
}
// 获取顺序表长度
public int size() {
return this.usedSize;
}
// 清空顺序表
public void clear() {
this.usedSize=0;
}
// 打印顺序表
public void display() {
for (int i = 0; i < this.usedSize; i++) {
System.out.printf(this.elem[i]+" ");
}
System.out.println();
}
}3、ArrayList简介
上图说明以下几点：
1.ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问。（根据下标进行访问）
2.ArrayList实现了Cloneable接口，表明ArrayList是可以clone的。
3.ArrayList实现了Serializable接口，表明ArrayList是支持序列化的。
4.和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程下可以选择Vector或者CopyOnWriteArrayList。
5.ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表。
6.ArrayList 继承了 AbstractList ，并实现了 List 接口。
其中，ArrayList 类位于 java.util 包中，使用前需要引入它。
import java.util.Arrays;ArrayList是以泛型方式实现的，使用前必须要先进行实例化：
ArrayList<E> objectName =new ArrayList<>();
- E：表示泛型数据类型，用于设置 objectName 的数据类型，只能为引用数据类型。
- objectName： 对象名。
4.ArrayList使用
4.1 ArrayList的构造
ArrayList的构造在Java中有三种构造方法：
方法 |
解释 |
ArrayList() |
无参构造 |
ArrayList(Collection<? extends E> c) |
利用其他 Collection 构建 ArrayList |
ArrayList(int initialCapacity) |
指定顺序表初始容量 |
接下来，我们来实现一下
public static void main(String[] args) {
// ArrayList创建，推荐写法
// 构造一个空的列表
List<Integer> list1 = new ArrayList<>();
// 构造一个具有10个容量的列表
List<Integer> list2 = new ArrayList<>(10);
list2.add(1);
list2.add(2);
list2.add(3);
// list2.add("hello"); // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素
// list3构造好之后，与list中的元素一致
ArrayList<Integer> list3 = new ArrayList<>(list2);
// 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难
List list4 = new ArrayList();
list4.add("111");
list4.add(100);
}4.2 ArrayList常见操作
虽然ArrayList提供的方法比较多，但是在日常使用时，我们常用的方法并没有特别多。
方法 |
解释 |
boolean add(E e) |
尾插 e |
void add(int index, E element) |
将 e 插入到 index 位置 |
boolean addAll(Collection<? extends E> c) |
尾插 c 中的元素 |
E remove(int index) |
删除 index 位置元素 |
boolean remove(Object o) |
删除遇到的第一个 o |
E get(int index) |
获取下标 index 位置元素 |
E set(int index, E element) |
将下标 index 位置元素设置为 element |
void clear() |
清空 |
boolean contains(Object o) |
判断 o 是否在线性表中 |
int indexOf(Object o) |
返回第一个 o 所在下标 |
int lastIndexOf(Object o) |
返回最后一个 o 的下标 |
List<E> subList(int fromIndex, int toIndex) |
截取部分 list |
4.3 ArrayList的遍历
ArrayList的遍历可以使用三种方式，分别为：for循环、for-each、使用迭代器
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
// 使用下标+for遍历
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println();
// 借助foreach遍历
for (Integer integer : list) {
System.out.print(integer + " ");
}
System.out.println();
//使用迭代器
Iterator<Integer> it = list.listIterator();
while(it.hasNext()){
System.out.print(it.next() + " ");
}
System.out.println();
}4.4 ArrayList的扩容机制
一件事情肯定是有利有弊的，我们上面讲这么多arrayList的优势，现在来思考一下，它有哪些缺点呢？
我们来看一下，ArrayList的扩容机制。
Object[] elementData; // 存放元素的空间
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认空间
private static final int DEFAULT_CAPACITY = 10; // 默认容量大小
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// 获取旧空间大小
int oldCapacity = elementData.length;
// 预计按照1.5倍方式扩容
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果用户需要扩容大小 超过 原空间1.5倍，按照用户所需大小扩容
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 调用copyOf扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// 如果minCapacity小于0，抛出OutOfMemoryError异常
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}【总结】
- 检测是否真正需要扩容，如果是调用grow准备扩容
- 预估需要库容的大小
初步预估按照1.5倍大小扩容
如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
真正扩容之前检测是否能扩容成功，防止太大导致扩容失败- 使用copyOf进行扩容