目录
一.定义
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
在集合框架中，ArrayList是一个普通的类，实现了List接口。
二.ArrayList的使用
1.ArrayList的构造方法
| 方法 | 解释 |
| ArrayList() | 无参构造 |
| ArrayList(Collection<? extends E> c) | 利用其他 Collection 构建 ArrayList |
| ArrayList(int initialCapacity) | 指定顺序表初始容量 |
2.常用方法
| 方法 | 解释 |
| boolean add(E e) | 尾插 （放在集合的最后）e（可以插入size下标的元素） |
| void add(int index, E element) | 将 e 插入到 index 位置 |
| boolean addAll(Collection<? extends E> c) | 尾插 c 中的元素 |
| E remove(int index) | 删除 index 位置元素（不可以删除size下标的元素） |
| 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（包含fromIndex，不包含toIndex） |
三.自定义实现List和ArrayList
自定义实现线性表（接口MyList）和顺序表（类MyArrayList）。
1.要求：
(1).熟悉ArrayList下的常见方法
- 各个方法的作用
- 各个方法的基本实现原理
- 各个方法时间复杂度
(2).注意
- 什么叫做正确的对象
- 容量和元素之间的关系，以及准确判断出什么位置是容量，什么是元素个数。
eg：get(int index)中要求index的范围是[0.size)，其中的size最主要的是元素个数。
- 在循环中的边界问题
2.实现
(1).MyList接口的实现
/*
1.元素类型 Long
2.线性表
3.无元素的位置 null
*/
public interface MyList {
/**
* 返回线性表中的元素个数
* @return
*/
int size();
/**
* 将 e 尾插到线性表中，一定返回 true
* @param e
* @return
*/
boolean add(Long e);
/**
* 将 e 插入到线性表的 index 位置，从 [index, size()) 向后移
* index 的合法下标 [0, size()]
* 如果下标不合法：抛出一个 ArrayIndexOutOfBoundsException
* @param index
* @param e
*/
void add(int index,Long e);
/**
* 删除 index 位置的元素
* index 的合法下标：[0, size())
* 如果下标不合法：抛出一个 ArrayIndexOutOfBoundsException
* @param index
* @return 从线性表中删除掉的元素
*/
Long remove(int index);
/**
* 从前到后，删除第一个遇到的 e（ equals() == true）
* @param e
* @return 删除成功：true，没有该元素：false
*/
boolean remove(Long e);
/**
* 直接返回 index 位置的元素
* index: [0, size())
* @param index
* @return
*/
Long get(int index);
/**
* 使用 e 替换 index 位置的元素
* @param index [0, size())
* @param e
* @return 原来 index 位置的元素
*/
Long set(int index,Long e);
/**
* 返回第一次遇到 e 的下标（equals() == true）
* @param e
* @return 如果没有找到，返回 -1
*/
int indexOf(Long e);
/**
* 从后往前，返回第一次遇到 e 的下标（equals() == true）
* @param e
* @return 如果没有找到，返回 -1
*/
int lastIndexOf(Long e);
/**
* 线性表中是否包含 e（equals）
* @param e
* @return
*/
boolean contains(Long e);
/**
* 清空数组
*/
void clear();
/**
* 判断数组是否为空
* @return
*/
boolean isEmpty();
}(2).MyArrayList的实现（包含扩容的实现）
/**
* 顺序表：物理上元素相连的线性表
* 约束：
* 0 <= size <= array.length
* array[0, size) != null
* array[size, array.length) == null
*/
public class MyArrayList implements MyList{
// 定义属性
private Long[] array; //array.length 容量
private int size; //保存元素个数
// 构造方法
public MyArrayList(){
// 容量没有规定，自行定义为 16 个
this.array=new Long[16];
//把数组中的每个位置都初始化为null，数组初始化后本身就是null
for (int i=0;i<array.length;i++){
array[i]=null;
}
// 元素个数 = 0
this.size=0;
}
public MyArrayList(int initialCapacity){
this.array=new Long[initialCapacity];
// 这一步不是必须的，把数组中的每个位置都初始化成 null
for (int i=0;i<array.length;i++){
array[i]=null;
}
// 元素个数 = 0
this.size=0;
}
@Override
public int size() {
return size;
}
//扩容的实现
private void ensureCapacity(){
if(this.size<this.array.length){
return; //此时不需要扩容
}
//需要扩容
//1.申请新数组，容量是原来的2倍
int newLength=this.array.length*2;
Long[] newArray=new Long[newLength];
//2.搬家
for (int i=0;i<this.size;i++){
newArray[i]=this.array[i];
}
//3.让顺序表的array引用指向新数组
this.array=newArray;
}
//时间复杂度：数据规模：size O(1)
//最坏情况，扩容 O(n)
//认为扩容是小概率事件，平均时间复杂度：O(1)
@Override
public boolean add(Long e) {
//TODO:容量问题
ensureCapacity();
// 为 size 赋予一个新的逻辑含义 —— 尾插时的元素的位置
array[size]=e;
// 让元素个数的记录 + 1
size=size+1;
// 返回 true 表示插入成功
return true;
}
//时间复杂度：O(n)
@Override
public void add(int index, Long e) {
//TODO:容量问题
ensureCapacity();
//下标不合法，合法范围：[0,size]
if(index<0||index>size){
throw new ArrayIndexOutOfBoundsException("下标不合法");
}
//下标合法
for (int i=size-1;i>=index;i--){
array[i+1]=array[i];
}
array[index]=e;
size++;
}
//时间复杂度：O(n)
@Override
public Long remove(int index) {
//下标不合法，合法范围：[0,size)
if(index<0||index>=size){
throw new ArrayIndexOutOfBoundsException("下标不合法");
}
//先把要删除的元素保存
Long e=array[index];
for (int i=index+1;i<size;i++){
array[i-1]=array[i];
}
//把不存在的元素置为null
array[size-1]=null;
size--;
return e;
}
//时间复杂度：O(n)
@Override
public boolean remove(Long e) {
// 按照从前到后的顺序，找到第一个遇到的 e
for (int i=0;i<size;i++){
// 比较 array 的值是否和 e 相等（equals）
if(array[i].equals(e)){
//删除i位置的元素
remove(i);
return true;
}
}
//没有找到e
return false;
}
//时间复杂度：O(1)
@Override
public Long get(int index) {
//下标不合法，合法范围：[0,size)
if(index<0||index>=size){
throw new ArrayIndexOutOfBoundsException("下标不合法");
}
return array[index];
}
//时间复杂度：O(1)
@Override
public Long set(int index, Long e) {
//下标不合法，合法范围：[0,size)
if(index<0||index>=size){
//下标不合法
throw new ArrayIndexOutOfBoundsException("下标不合法");
}
Long oldE=array[index];
array[index]=e;
return oldE;
}
//时间复杂度：O(n)
@Override
public int indexOf(Long e) {
for (int i=0;i<size;i++){
if(array[i].equals(e)){
return i;
}
}
return -1;
}
//时间复杂度：O(n)
@Override
public int lastIndexOf(Long e) {
for (int i=size-1;i>=0;i--){
if(array[i].equals(e)){
return i;
}
}
return -1;
}
//时间复杂度：O(n)
@Override
public boolean contains(Long e) {
return indexOf(e)!=-1;
}
@Override
public void clear() {
// array 中全部置为 null
for (int i = 0; i < size; i++) {
array[i] = null;
}
this.size = 0;
}
@Override
public boolean isEmpty() {
return size == 0;
}
}如有建议或想法，欢迎一起讨论学习~
本文含有隐藏内容，请 开通VIP 后查看