【数据结构与算法】ArrayList 与顺序表的实现

目录

一、List 接口

1.1 List 接口的简单介绍

1.1 常用方法

二、顺序表

2.1 线性表的介绍

2.2 顺序表的介绍

2.3 顺序表的实现

2.3.1 前置条件：自定义异常

2.3.2 顺序表的初始化

2.3.2 顺序表的实现

三、ArrayList 实现类

3.1 ArrayList 的两种使用方式

3.2 ArrayList的构造方法

3.3 常用方法及 API

3.3.1 remove 方法

3.3.2 subList 方法

3.3 ArrayList 的三种遍历方式

3.3.1 for 循环遍历

3.3.2 for-each 遍历

3.3.3 迭代器遍历

3.4 ArrayList 的扩容机制

3.4.1 无参构造源码分析

3.4.2 带参构造源码分析

3.4.3 借助容器构造源码分析

四、链接算法

4.1 笔试真题

4.1.1 CVTE 删除字符串

4.1.2 杨辉三角

---

一、List 接口

1.1 List 接口的简单介绍

在集合框架中，List是一个接口，继承自Collection。

Collection也是一个接口，该接口中规范了后序容器中常用的一些方法，具体如下所示：

Iterable也是一个接口，表示实现该接口的类是可以逐个元素进行遍历的，具体如下：

站在数据结构的角度来看，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。

1.1 常用方法

常用方法如下：

List是个接口，并不能直接用来实例化。如果要使用，必须去实例化List的实现类。在集合框架中，ArrayList和LinkedList都实现了List接口。

二、顺序表

2.1 线性表的介绍

线性表（linear list）：是 n 个具有相同特性的数据元素的有限序列（序列就是指元素之间是有顺序的）。若存在多个元素，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。

线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列。

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.2 顺序表的介绍

顺序表：是用一段物理地址连续的存储单元依次存储数据元素的线性结构。底层结构是通过数组存储（因为数组是按顺序进行存储的），在数组上完成数据的增删查改。

2.3 顺序表的实现

2.3.1 前置条件：自定义异常

public class PosOutOfException extends RuntimeException{public PosOutOfException(){super();}public PosOutOfException(String message){super(message);}
}

2.3.2 顺序表的初始化

public class MyArrayList {/*** 用于存储数据元素*/private int[] elem;/*** 代表当前顺序表的有效元素的个数：默认值为 0*/private int usedSize;private static final int DEFAULT_SIZE = 10;public MyArrayList() {this.elem = new int[DEFAULT_SIZE];this.usedSize = 0;}/*** 指定容量* @param initCapacity*/public MyArrayList(int initCapacity) {this.elem = new int[initCapacity];this.usedSize = 0;}
}

2.3.2 顺序表的实现

/*** 遍历数组：建议使用的时候加上 this*/
public void display(){for(int i=0;i<this.usedSize;i++){System.out.print(this.elem[i]+" ");}System.out.println();
}
/*** 新增元素：默认放置到数组末尾*/
public void add(int data){if(isFull()){// 扩容this.elem = Arrays.copyOf(this.elem,this.elem.length*2);}this.elem[this.usedSize] = data;this.usedSize++;
}/*** 指定位置新增元素* @param pos* @param data*/
public void add(int pos,int data){// 前置：判断 pos 位置是否合法if(pos<0 || pos>this.usedSize){throw new PosOutOfException(pos+"位置不合法!");}//1.如果容量满，需要进行扩容；否则导致移动元素发生数组越界访问if(isFull()){