1. 线性表的概念
线性表（Linear List）是一种基本的数据结构，它是由相同类型的元素组成的有限序列。线性表中的元素具有一对一的线性关系，即除了第一个元素和最后一个元素外，每个元素都有且仅有一个直接前驱和一个直接后驱。
线性表：零个或者多个数据元素的有限序列注意：
线性表可以根据其存储结构的不同分为两种类型：
顺序存储结构：使用一段连续的存储空间来存储线性表的元素，例如数组。
链式存储结构：使用链表来存储线性表的元素，每个元素包含数据和指向下一个元素的指针（在双向链表中还会有指向前一个元素的指针）。
常见的线性表实现有数组、链表、栈、队列等。
2. 顺序表的概念
顺序表是通过连续的存储单元来存储线性表的数据元素，从而实现线性表的操作。
注意：
顺序表底层结构就是一个数组.
3. 顺序表使用
3.1 初始化
创建一个顺序表，通常需要指定初始容量
public class MySeqList {
private int[] array;
public MySeqList(int initCapacity) {
array = new int[initCapacity];//初始化顺序表的大小
}
}
注意： 在创建一个MySeqList类的实例的时候，指定一个初始容量
3.2 判满
判断顺序表的容量是否已满
//判断数组满了没有
public boolean isFull(){
if(usedSize>=array.length){
return true;
}else {
return false;
}
}
注意：判满方法返回布尔值
3.2 增加
3.2.1 默认最后增加
//增加
public void add(int data){
if(isFull()) {
//扩容
this.array = Arrays.copyOf(this.array, this.array.length + 1);
}
this.array[this.usedSize] = data;
usedSize++;
}
注意：
1. 在进行增加操作前，需要进行顺序表的判满；
2. 如果顺序表没有剩余空间,则需要进行扩容操作
3. 增加成功后，不要忘记顺序表元素+1
3.2.2 指定位置增加
//在某个位置增加
public void add(int pos ,int data){
if(pos<0||pos> array.length){
System.out.println("位置不合适");
return ;
}
if(isFull()){
//扩容
this.array = Arrays.copyOf(this.array,this.array.length+1);
}
if(pos<usedSize){
//必须倒着诺数据
for (int i = usedSize-1; i >=pos; i--) {
array[i+1] = array[i];
}
}
this.array[pos] = data;
usedSize++;
}注意：
1. 判断增加的位置是否合法；
2. 增加位置合法，进行顺序表的判满；
3. 如果顺序表没有剩余空间,则需要进行扩容操作；
4.进行倒着诺数组元素
3.3 删
删除某个位置内的元素
1. 判断删除的位置是否合法；
2. 进行诺顺序表元素
//删除
public void del(int pos ){
if(pos<0||pos>=usedSize){
System.out.println("位置不合法");
return;
}
for (int i = pos; i <usedSize-1; i++) {
this.array[i] = this.array[i+1];
}
// this.array[usedSize-1]=null;//若为引用类型
usedSize--;
}注意：
如果为引用数据类型，最好将最后一个元素指向null（避免空间的浪费）
3.4 改
设置某个位置的元素
public void set(int pos ,int data){
if(pos<0||pos>=usedSize){
throw new IndexOutOfBoundsException("不合法");
}
array[pos] = data;
}判断修改的位置是否合法；如果位置合法返回对应位置的元素，反之报错；
3.5 查
3.5.1 查看某个元素是否存在
//查找
public boolean contains(int toFind){
for (int i = 0; i < usedSize; i++) {
if(array[i]==toFind){
return true;
}
}
return false;
}如果存在返回true，否则返回false
3.5.2 查看某个元素的下标
//查找返回下标
public int indexOf(int toFind){
for (int i = 0; i < usedSize; i++) {
if(array[i]==toFind){
return i;
}
}
return -1;
}3.5.3 获取某个下标的元素
//获得某个下标的元素
public int get(int pos){
if(pos<0||pos>=usedSize){
throw new IndexOutOfBoundsException("不合法");
}
return array[pos];
}判断查找的位置是否合法；如果位置合法返回对应位置的元素，反之报错；
3.6 清空顺序表
3.6.1 元素为基础数据类型
public void clear(){
this.usedSize = 0;
}
3.6.2 元素为引用数据类型
public void clear(){
for (int i = 0; i < usedSize; i++) {
array[i] = null;
}
this.usedSize = 0;
}注意：将下标指向null (避免空间的浪费)
3.7 获取顺序表的长度
//获取顺序表的长度
public int size() {
return this.usedSize;
}返回元素个数即可
4. ArrayList
4.1 初始ArrayList
ArrayList 是 Java 中的一种可以动态调整大小的数组实现，用于存储一系列的对象。它允许插入重复元素和 null 值，提供了方便的添加、删除、访问元素的方法，而且它还能自动扩展内部数组的容量，给用户提供更方便的服务。
ArrayList类其实本质上是一个普通的类，继承自 AbstractList，实现了 List、RandomAccess、Cloneable 和 Serializable 接口。
由图可以清晰的得到：
1. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
2. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
3. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
注意：ArrayList 的实现原理是围绕一个动态数组展开的，它通过数组的扩容机制来支持动态调整大小，并且提供了快速的随机访问能力。
4.2 ArrayList初始化
| 方法 | 说明 |
| ArrayList ( ) | 无参构造器 |
| ArrayList (Collection<? extends E> c ) | 利用Collection构建ArrayList |
| ArrayList (int initialCapacity ) |
指定初始化容量 |
（1）使用无参构造器创建
ArrayList<Integer> arrayList = new ArrayList<>();注意：
1. 最好使用泛型规定数据类型 ，否则任何数据类型都可以进行操作，容易混乱
2. 当调用不带参数的构造的方法，不会分配空间，在第一次使用add方法的时候才会分配大小为10的空间
3. 当进行扩容时候每次扩容只扩容1.5倍
（2）使用有参数构造器
ArrayList<Integer> list2 = new ArrayList<>(5);（3）使用ArrayList (Collection<? extends E> c ) 构造器
ArrayList<Integer> arrayList = new ArrayList<>();
ArrayList<Integer> arrayList1 = new ArrayList<>(arrayList);
//arrList必须是Interger的子类或者本身注意：
ArrayList<String> arrayList2 = new ArrayList<>();
// ArrayList<Integer> arrayList3 = new ArrayList<>(arrayList2);//报错
//String类型不是Interager类型的子类或者本身1. ? extends E 是 Java 泛型中的通配符，表示这个构造器可以接受任何类型 E 或者 E 的子类型的集合
2. 会继承传入实例对象的所有元素，并且元素的顺序也会保持一致
4.3 ArrayLIst的常用API
|
boolean add (E e)
|
尾插 |
|
void add (int index, E element)
|
在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)
|
截取顺序表的一部分 |
（1）增加
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Text_3 {
public static void main(String[] args) {
ArrayList<Integer> arrayList1 = new ArrayList<>();
arrayList1.add(5);//尾插
arrayList1.add(0,4);//指定位置插入
//插入所有元素
Integer[] array = {1 ,5 ,6};
List<Integer> array1 = Arrays.asList(array);
arrayList1.addAll(array1);
System.out.println(arrayList1);
//另一种写法
ArrayList<Integer> arrayList3 = new ArrayList<>(Arrays.asList(array));
arrayList1.addAll(arrayList3);
}
}
注意：Arrays.asList()返回的是List类型，而不是ArrayList类型。
（2）删除
import java.util.ArrayList;
public class Remove {
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
arrayList.add(4);
//删除元素
arrayList.remove(new Integer(2));
// 实际上是在创建一个新的 Integer 对象。这意味着 remove 方法将尝试查找列表中与这个新创建的 Integer 对象引用相同的元素 ， 找到则删除
//删除位置
arrayList.remove(0);
System.out.println(arrayList);
}
}
注意： 对整数进行操作时：在使用remove()方法时，避免boolean remove(Object o）和E remove(int index)的混淆
（3）修改
import java.util.ArrayList;
public class Set {
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
arrayList.add(4);
arrayList.set(1,999);
System.out.println(arrayList);
}
}
输入对应下标和新的元素值，即可成功调用set（）方法，完成修改
（4）获取
import java.util.ArrayList;
public class Get {
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
arrayList.add(4);
int x = arrayList.get(2);
System.out.println(x);
}
}
注意：下标从0开始
（5）清空
import java.util.ArrayList;
public class Clear {
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
arrayList.add(4);
System.out.println(arrayList);
arrayList.clear();
System.out.println(arrayList);
}
}（6）查找
import java.util.ArrayList;
public class Contains {
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
arrayList.add(4);
//1,返回第一个出现元素的下标
int x = arrayList.indexOf(3);
System.out.println(x);
//2.返回最后一个出现元素的坐标
int x1 = arrayList.lastIndexOf(3);
System.out.println(x1);
//3.查看元素是否存在
Boolean x2 = arrayList.contains(5);
System.out.println(x2);
}
}
注意：indexOf从前往后找，lastIndexOf从后往前找，contains返回的是布尔值
（7）截取
import java.util.ArrayList;
import java.util.List;
public class SubList {
public static void main(String[] args) {
List<Integer> integers = new ArrayList<>();
integers.add(1);
integers.add(6);
integers.add(9);
integers.add(15);
// List<Integer> integers1 = integers.subList(1,3);
ArrayList<Integer> integers1 = new ArrayList<>(integers.subList(1,3));
System.out.println(integers1);//[6, 9]
integers1.set(0,999);
System.out.println(integers1);//[999, 9]
System.out.println(integers);//[1, 999, 9, 15],没有取出来，只是在原来的位置操作
//能够直接通过输出引用类型的内容，表示一定重写了toString方法
}
}
注意：
1. subList方法是左闭右开区 【 [ ， ）】
2. subList方法只是截取了一部分进行操作，本质上还是在原来的顺序表内
4.4 ArrayLIst的遍历
（1）使用for循环遍历
//遍历1
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i)+" ");
}
System.out.println();（2）使用for-each循环
//遍历2
for (Integer x:list) {
System.out.println(x);
}
System.out.println();（3）使用迭代器
从前往后遍历
//遍历3
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){//是否存在下一个
System.out.println(iterator.next()+" ");
}
System.out.println();
// 另一种方式
ListIterator listIterator = list.listIterator();//迭代器
while(listIterator.hasNext()){
System.out.println(listIterator.next()+" ");
}
System.out.println();
注意：
1. ListIterator继承Iterator
2. ListIterator和Iterator 是一个可以双向遍历列表的迭代器，它还允许在迭代期间修改列表。
从后往前遍历
//从后往前
ListIterator listIterator1 =list.listIterator(list.size());
while(listIterator1.hasPrevious()){
System.out.println(listIterator1.previous()+" ");
}注意：
（从前往后）while循环中的判断条件表示：是否存在下一个元素，如果存在，则获取迭代器的下一个元素并输出，因为 next 方法，所以在每次调用后进行移动1位