1.线性表
线性表是n个具有相同类型的数据元素所组成的有限序列，当n=0时，线性表为一个空表。
常见的线性表：顺序表，链表，栈和队列...
线性表在逻辑上是线性结构，可以说是连续的一条直线。但是在物理结构上并不一定是线性的，线性表在物理上存储，通常以数组和链表的形式存储。
2.顺序表
2.1 什么是顺序表
顺序表是一段连续的存储单元来依次存储线性表中的数据元素。一般情况下采用数组存储。
2.2 顺序表的特点
1.存储连续：顺序表的存储单元在内存中是连续的，这意味着每个元素的地址都是相邻连续的
2.随机访问：由于存储单元是连续的，可以通过元素的下标直接访问该位置的元素，时间复杂度为O(1)
3.存储密度高：顺序表的存储单元只存储数据元素本身，没有额外的存储开销
2.3 实现一个顺序表
public class MySequentialList{
private int[] array;
private int size;
//默认构造方法
MySequentialList(){}
//将顺序表的容量设为initCapacity
MySequentialList(int initCapacity){}
//在数组末尾新增一个元素
public void add(int data){}
//在pos位置新增一个元素
public void add(int pos,int data){}
//判断是否包含某个元素
public boolean contains(int toFind){}
//查找某个元素对应的位置
public int indexOf(int toFind){}
//获取pos位置上的元素
public int get(int pos){}
//给pos位置上的元素设置为value
public void set(int pos,int value){}
//删除第一次出现的关键字key
public void remove(int toRemove){}
//获取顺序表的长度
public int size(){}
//清空顺序表
public void clear(){}
}实现的思路：
1.MySequentialList(int initCapacity)
只需要将数组初始化大小为initCapacity即可
2.add(int data)
在数组最后的位置新增元素，要注意数组是否已满，如果已满，就要对数组进行扩容操作
3.add(int pos,int data)
首先要判断插入位置pos是否合法，如果pos小于0或pos大于数组的长度，则位置不合法要进行异常处理。如果位置合法，还要判断数组是否已满，进行插入操作时，要注意先将原pos以及pos后面的元素全都向后移动一位，再进行插入操作，如果直接插入，则只是单纯的元素覆盖。插入后，数组的长度加1
4.contains(int toFind)
判断是否包含某个元素，只需要遍历数组并进行比较，看数组中是否有存在要查找的元素，如果有，则返回true，没有则返回false
5.indexOf(int toFind)
遍历数组，看数组中是否存在要查找的元素，如果存在，则返回给元素位置的下标，如果不存在，则返回-1
6.get(int pos)
获取pos位置的元素，首先要判断pos位置是否合法，如果pos小于0或者pos大于数组的长度，则pos不合法，返回-1。如果合法，直接返回下标为pos的元素
7.set(int pos,int value)
给pos位置的元素设置为value，单纯的进行对应下标元素覆盖即可
8.remove(int toRemove)
删除第一次出现关键字key，遍历数组，看key是否存在。如果不存在，则返回-1。如果存在，只需要将该位置后面的所有元素先前移动一位即可
9.size()
直接返回数组的有效长度，有效长度指的是数组中有效元素的个数，不是单纯的数组长度
10.clear()
清空顺序表，重新初始化数组，并将数组的长度置为0
我们后续以ArrayList的实现为例。
3.ArrayList
3.1 什么是ArrayList
在集合框架中，ArrayList是 Java 标准库中的一个非常常用的类，它实现了 List接口，提供了动态数组的功能。 ArrayList内部使用数组来存储元素，因此它具备顺序表的所有特点，是顺序表的一种实现。
说明：
1.ArrayList 是以泛型的方式实现的，使用时必须要先实例化
2.ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
3.ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
4.ArrayList实现了Serializable接口，表面ArrayList是支持序列化的
5.ArrayList是线程不安全的，在单线程下可以使用
6.ArrayList是通过动态的数组实现的，是一段连续的空间，并且可以进行扩容
3.2 ArrayList的构造方法
| 方法 | 解释 |
| ArrayList() | 无参构造 |
| ArrayList(Collection<? extends E> c) | 利用其他Collection构建ArrayList |
| ArrayList(int initialCapacity) | 指定顺序表初始容量 |
代码演示：
public class Test {
public static void main(String[] args) {
//无参构造
List<Integer> list1=new ArrayList<>();
//利用其他Collection构建ArrayList
ArrayList<Integer> arrayList=new ArrayList<>();
List<Integer> list2=new ArrayList<>(arrayList);
//指定顺序表容量
List<Integer> list3=new ArrayList<>(10);
}
}3.3 ArrayList的常见操作
ArrayList常见的方法
| 方法 | 解释 |
| boolean add(E,e) | 在尾部插入元素e |
| void add(int index,E e) | 将元素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 e) | 将下表为index位置的元素设置为e |
| 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 |
代码演示：
import java.util.ArrayList;
import java.util.List;
public class Test {
public static void main(String[] args) {
List<Integer> list=new ArrayList<>();
System.out.println(list);
//在尾部插入元素
list.add(1);
list.add(5);
list.add(3);
list.add(5);
list.add(10);
System.out.println(list);
//在下标为2的位置增加元素
list.add(2,4);
System.out.println(list);
//删除下标为2的元素
list.remove(2);
System.out.println(list);
//删除遇到的第一个5元素
Integer a=5;
list.remove(a);
System.out.println(list);
//获取下标为1的元素
int e=list.get(1);
System.out.println(e);
//将下标为1的元素设置为99
list.set(1,99);
System.out.println(list);
//判断5是否在线性表中
System.out.println(list.contains(5));
//返回第一个5所在的下标
e=list.indexOf(5);
System.out.println(e);
//返回最后一个5所在的下标
e= list.lastIndexOf(5);
System.out.println(e);
//截取部分list,左闭右开
List<Integer> newList=new ArrayList<>();
newList=list.subList(1,3);
System.out.println(newList);
//将newList中的元素全部添加入list中
list.addAll(newList);
System.out.println(list);
//清空list
list.clear();
System.out.println(list);
}
}
3.4 ArrayList的遍历
ArrayList的遍历方式主要分为3种：
1.for循环搭配下标
2.foreach
3.使用迭代器
public class Test {
public static void main(String[] args) {
List<String> list=new ArrayList<>();
list.add("hajimi");
list.add("is");
list.add("a");
list.add("cat");
//使用for循环搭配下标
for(int i=0;i<list.size();i++){
System.out.print(list.get(i)+" ");
}
System.out.println();
//使用foreach遍历
for(String s:list){
System.out.print(s+" ");
}
System.out.println();
//使用迭代器遍历
Iterator<String> it=list.listIterator();
while(it.hasNext()){
System.out.print(it.next()+" ");
}
}
}4.深度理解ArrayList 的扩容机制
观察原码：
int DEFAULT_CAPACITY表示默认的容量大小
Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA表示默认的空间
Object[] elementData表示存放元素的空间
ArrayList的无参构造函数，将elementData初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，这是一个空数组，用于创建一个具有默认容量为 10的空ArrayList
ArrayList的add方法首先调用ensureCapacityInternal(size+1)，size表示当前顺序表的有效长度，size+1表示添加元素后应有的长度
size+1的值传递给ensureCapacityInternal的形参minCapacity，ensureCapacityInternal先调用calculateCapacity(Object[] element,int minCapacity)传入存放元素的空间elementData和minCapacity
calculateCapacity(Object[] elementData,int minCapacity)用来计算ArrayList需要增长到的最小容量。判断elementData是否等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA，如果相等则意味着ArrayList当前没有分配任何容量，是空的。在这种情况下，方法返回DEFAULT_CAPACITY(10)和minCapacity中的较大值。如果element不是空数组，则意味着ArrayList已经有了一些容量，这种情况下，直接返回minCapacity，可以保证它至少增长到minCapacity即可
calculateCapacity的返回值传递给ensureExplicitCapacity的形参minCapacity，判断当前是否需要扩容，如果minCapacity大于数组的长度，则表示需要进行扩充
ArrayList的扩容函数grow(int minCapacity)用于增加ArrayList的内部数组elementData的容量，使其至少容纳minCapacity个元素。
int newCapacity=oldCapacity+(oldCapacity >> 1)计算新的容量，通常是当前容量的1.5倍
if(newCapacity - minCapacity < 0)判断新容量是否满足最小的需求，如果计算出的容量仍然小于最小的容量，则将newCapacity设置为minCapacity
if(newCapacity-MAX_ARRAY_SIZE > 0)检查新容量是否超出最大数组的大小，如果超过了调用hugeCapacity处理这种情况(将新容量设为Integer.MAX_VALUES)
elementData = Arrays.copyOf(elementData,newCapacity)使用copyOf创建一个新的数组，并将就数组中的元素复制到新数组中。
总结：
1.首先判断是否需要进行扩容，如果需要进行扩容，调用grow方法
2.计算扩容所需的最小的容量
初步预估按照1.5倍大小进行扩容
如果用户所需大小大于预估的1.5倍，则按照用户所需大小进行扩容
扩容前检查是否可以扩容成功，防止太大导致扩容失败
3.使用Arrays.copyOf进行扩容
5.实现一个ArrayList
package datastructure;
import java.util.Arrays;
public class MyArrayList {
public int[] elem;
public int usedSize;//0
//默认容量
private static final int DEFAULT_SIZE = 2;
public MyArrayList() {
this.elem = new int[DEFAULT_SIZE];
}
/**
* 打印顺序表:
* 根据usedSize判断即可
*/
public void display() {
for(int i=0;i<this.usedSize;i++){
System.out.print(elem[i]+" ");
}
System.out.println();
}
// 新增元素,默认在数组最后新增
public void add(int data) {
if(isFull()){
//扩容
this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
}
this.elem[this.usedSize]=data;
this.usedSize++;
}
/**
* 判断当前的顺序表是不是满的！
* true:满 false代表空
*/
public boolean isFull() {
if(this.usedSize==this.elem.length){
return true;
}
return false;
}
private boolean checkPosInAdd(int pos) {
if(pos<0||pos>usedSize){
System.out.println("位置不合法");
return false;
}
return true;//合法
}
// 在 pos 位置新增元素
//移动数据，从后向前防止数值被覆盖
public void add(int pos, int data) {
if(pos<0||pos>this.usedSize){
System.out.println("位置不合法");
return;
}
if(isFull()){
//扩容
this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
}
for(int i=this.usedSize-1;i>=pos;i--){
this.elem[i+1]=this.elem[i];
}
this.elem[pos]=data;
usedSize++;
}
// 判定是否包含某个元素
public boolean contains(int toFind) {
for(int i=0;i<this.usedSize;i++){
if(elem[i]==toFind){
return true;
}
}
return false;
}
// 查找某个元素对应的位置
public int indexOf(int toFind) {
if(isEmpty()){
System.out.println("表中没有元素");
return -1;
}
for(int i=0;i<usedSize;i++){
if(elem[i]==toFind){
return i;
}
}
System.out.println("没找到");
return -1;
}
// 获取 pos 位置的元素
public int get(int pos) {
if(pos<0&&pos>=usedSize){
System.out.println("输入不合法！");
return -1;
}
if(!isEmpty()){
return elem[pos];
}
return -1;
}
private boolean isEmpty() {
if(usedSize==0){
return true;
}
return false;
}
// 给 pos 位置的元素设为【更新为】 value
public void set(int pos, int value) {
if(pos<0||pos>=usedSize)
return;
elem[pos]=value;
}
/**
* 删除第一次出现的关键字key
* @param key
*/
public void remove(int key) {
int index=indexOf(key);
if(index==-1){
return;
}
for(int i=index;i<usedSize-1;i++){
this.elem[i]=this.elem[i+1];
}
this.usedSize--;
}
// 获取顺序表长度
public int size() {
return this.usedSize;
}
// 清空顺序表
public void clear() {
this.usedSize=0;
}
}
6.ArrayList的特点
1.基于数组实现：
ArrayList使用一个动态数组来存储元素
2.动态数组容量
ArrayList可以根据添加元素的情况进行自动扩容，默认情况下是按照当前容量的1.5倍进行扩容
3.随机访问效率高，时间复杂度为O(1)
ArrayList基于数组实现，支持随机访问，时间复杂度为O(1)
4.插入和删除操作时间复杂度为O(n)
在ArrayList的中间位置插入或删除元素效率不高，这些操作会移动插入点之后的所有元素，时间复杂度为O(n)，但是在末尾插入或删除元素的时间复杂度为O(1)
5.允许有重复的元素
6.允许存储null元素
7.ArrayList是线程不安全的
