数据结构*集合框架顺序表-ArrayList

集合框架

常见的集合框架

什么是顺序表

顺序表是一种线性表数据结构，它借助一组连续的存储单元来依次存储线性表中的数据元素。一般情况下采用数组存储。 在数组上完成数据的增删查改。

自定义简易版的顺序表

代码展示：

public interface IArrayList {//新增元素,默认在数组最后新增void add(int data);//在 pos 位置新增元素void add(int pos, int data);//判定是否包含某个元素boolean contains(int toFind);//查找某个元素对应的位置int indexOf(int toFind);//获取 pos 位置的元素int get(int pos);//给 pos 位置的元素设为 valuevoid set(int pos, int value);//删除第⼀次出现的关键字keyvoid remove(int toRemove);//获取顺序表⻓度int size();//清空顺序表void clear();
}

import java.util.Arrays;public class MyArrayList implements IArrayList {private int useSize;private int[] elem;public MyArrayList() {this.elem = new int[Constant.DEFAULT_CAPACITY];}@Override//新增元素,默认在数组最后新增public void add(int data) {//1、是否能继续存放数据，不能就进行扩容if(isFill()) {grow();}//2、在数组末尾添加数据this.elem[useSize] = data;this.useSize++;}@Override//在 pos 位置新增元素public void add(int pos, int data) {//1、是不是满的if(isFill()) {grow();}//2、检查pos位置的合法性checkPosAdd(pos);//3、移动数据for (int i = useSize - 1; i >= pos ; i--) {elem[i+1] = elem[i];}/*if (useSize - pos >= 0) {System.arraycopy(elem, pos, elem, pos + 1, useSize - pos);}*/elem[pos] = data;useSize++;}private void checkPosAdd(int pos) {if(pos < 0 || pos > this.useSize) {throw new PosException(Constant.ADD_CHECK_MASSAGE);}}@Override//判定是否包含某个元素public boolean contains(int toFind) {for (int i = 0; i < this.useSize; i++) {if(elem[i] == toFind) {return true;}}return false;}@Override//查找某个元素对应的位置public int indexOf(int toFind) {for (int i = 0; i < this.useSize; i++) {if(elem[i] == toFind) {return i;}}return 0;}@Override//获取 pos 位置的元素public int get(int pos) {//1、判断顺序表是否为空if(isEmpty()) {throw new isEmptyException(Constant.EMPTY_MASSAGE);}//2、判断pos位置是否合法checkPos(pos);return elem[pos];}private void checkPos(int pos) {if(pos < 0 || pos >= this.useSize) {throw new PosException(Constant.GET_CHECK_MASSAGE);}}@Override//给 pos 位置的元素设为 valuepublic void set(int pos, int value) {if(isEmpty()) {throw new isEmptyException(Constant.EMPTY_MASSAGE);}checkPos(pos);elem[pos] = value;}@Override//删除第⼀次出现的关键字keypublic void remove(int toRemove) {if(isEmpty()) {throw new isEmptyException(Constant.EMPTY_MASSAGE);}int index = indexOf(toRemove);if(index == -1) {System.out.println("没有你要删除的数据");return;}for (int i = index; i < this.useSize - 1; i++) {elem[i] = elem[i+1];}elem[useSize - 1] = 0;useSize--;}@Override//获取顺序表⻓度public int size() {return this.useSize;}@Override//清空顺序表public void clear() {for (int i = 0; i < this.useSize; i++) {this.elem[i] = 0;}this.useSize = 0;}//是否为空private boolean isEmpty() {return useSize == 0;}//是否存满private boolean isFill() {return this.useSize == this.elem.length;//判断有效数据是否等于总数组长度}//数据扩容private void grow() {this.elem = Arrays.copyOf(this.elem,elem.length*2);}@Overridepublic String toString() {return Arrays.toString(elem);}
}

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

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

public class Constant {public static final int DEFAULT_CAPACITY = 5;public static final String EMPTY_MASSAGE = "顺序表为空";public static final String GET_CHECK_MASSAGE = "get方法的pos位置不合法";public static String ADD_CHECK_MASSAGE = "add方法的pos位置不合法";
}

public class Test {public static void main(String[] args) {MyArrayList myArrayList = new MyArrayList();myArrayList.add(1);myArrayList.add(2);myArrayList.add(3);myArrayList.add(4);myArrayList.add(2,10);myArrayList.add(2,10);System.out.println(myArrayList.contains(9));System.out.println(myArrayList.get(0));myArrayList.set(1,20);myArrayList.remove(10);System.out.println(myArrayList.size());System.out.println(myArrayList);myArrayList.clear();System.out.println(myArrayList);}
}

代码解释：

1、定义了一个IArrayList接口，里面有需要实现的方法。
2、Constant类用来存放一些常量。
3、自定义了一个MyArrayList顺序表。useSize表示数据中的有效长度，elem[]表示存储数据的数组。在构造方法中初始化了数组的默认大小。实现了如下方法：

方法	功能
void add(int data)	新增元素，默认在数组最后面新增
void add(int pos,int data)	在pos位置新增元素
boolean contains(int toFind)	判断是否包含某个元素
int indexOf(int toFind)	查找某个元素对应的位置
int get(int pos)	获得pos位置的元素
void set(int pos,int value)	给pos位置的元素设为value
void remove(int toRemove)	删除第一次出现的关键字toRemove
int size()	获得顺序表长度
void clear()	清空顺序表
4、两个自定义异常，分别表示数组中没有元素、pos位置不合法。
5、对于数据结构来说是很严谨的，需要考虑各种情况。将可能发生的情况进行书写。

官方定义的顺序表-ArrayList

类的属性

构造方法

有三种构造方法

无参构造方法

public static void test1() {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add("Hello");//报错System.out.println(arrayList);List<String> list = new ArrayList<>();//向上转型list.add("Hello");list.add("World");System.out.println(list);
}

此时new的是一个空的列表。arrayList已经限定为Integer类型，不能接收String类型。
对于add方法，查看源码：



grow方法就是扩容操作，完成的是1.5倍扩容。

指定顺序表初始容量

public static void test2() {ArrayList<Integer> arrayList = new ArrayList<>(20);arrayList.add(10);arrayList.add(20);arrayList.add(30);System.out.println(arrayList);
}

利用其他Collection构建ArrayList

public static void test3() {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);System.out.println(arrayList);ArrayList<Integer> arrayList1 = new ArrayList<>(arrayList);arrayList1.add(10);System.out.println(arrayList1);ArrayList<Number> arrayList2 = new ArrayList<>(arrayList);arrayList2.add(100);System.out.println(arrayList2);System.out.println(arrayList1);ArrayList<String> stringArrayList = new ArrayList<>(arrayList);//报错
}

输出：
[1]
[1, 10]
[1, 100]
[1, 10]

说明这种构造方法是创建一个新（单独）的列表，并继承传入的列表已有的值。

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

代码案例：

import java.util.ArrayList;
import java.util.List;public class Test {public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);arrayList.add(4);arrayList.add(4,10);System.out.println(arrayList);//arrayList.add(6,10);//报错，IndexOutOfBoundsExceptionArrayList<Integer> arrayList1 = new ArrayList<>();arrayList1.addAll(arrayList);System.out.println(arrayList1);arrayList1.add(5);System.out.println(arrayList);System.out.println("===========");arrayList.remove(4);System.out.println(arrayList);System.out.println("===========");Integer i = 4;arrayList.remove(i);System.out.println(arrayList);System.out.println("===========");System.out.println(arrayList.get(2));System.out.println("===========");arrayList.set(1,100);System.out.println(arrayList);System.out.println("===========");System.out.println(arrayList.contains(10));System.out.println("===========");ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);list.add(8);list.add(9);list.add(10);System.out.println(list);//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]List<Integer> sublist = list.subList(2, 7);System.out.println(sublist);//[3, 4, 5, 6, 7]sublist.set(0,100);System.out.println(sublist);//[100, 4, 5, 6, 7]System.out.println(list);//[1, 2, 100, 4, 5, 6, 7, 8, 9, 10]}
}

代码解释：

需要注意的是：
1、subList()方法截取的范围是 [ fromeIndex,toIndex )
2、这里的截取并不是创建一个新的顺序表，而是获取原表上fromeIndex的地址。所以修改的是原表上的值。

ArrayList的遍历

代码案例：

public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println("--------for循环遍历--------");for(int i = 0; i < list.size();i++) {System.out.print(list.get(i)+" ");}System.out.println();System.out.println("--------foreach循环遍历--------");for (Integer integer : list) {System.out.print(integer + " ");}System.out.println();System.out.println("--------迭代器正序输出1--------");Iterator<Integer> it = list.listIterator();while (it.hasNext()) {System.out.print(it.next()+" ");}System.out.println();System.out.println("--------迭代器正序输出2--------");ListIterator<Integer> its = list.listIterator();while (its.hasNext()) {System.out.print(its.next()+" ");}System.out.println();System.out.println("--------迭代器正序输出3（从指定下标位置输出）--------");ListIterator<Integer> itss = list.listIterator(2);while (itss.hasNext()) {System.out.print(itss.next()+" ");}System.out.println();System.out.println("--------迭代器逆序输出--------");ListIterator<Integer> reits = list.listIterator(list.size());while (reits.hasPrevious()) {System.out.print(reits.previous()+" ");}
}

输出：
--------for循环遍历--------
1 2 3 4 5 6 7
--------foreach循环遍历--------
1 2 3 4 5 6 7
--------迭代器正序输出1--------
1 2 3 4 5 6 7
--------迭代器正序输出2--------
1 2 3 4 5 6 7
--------迭代器正序输出3从指定下标位置输出--------
3 4 5 6 7
--------迭代器逆序输出--------
7 6 5 4 3 2 1

代码解释：

1、list.listIterator() 是调用 list 对象的方法来获取一个列表迭代器。it.hasNext() 是判断迭代器 it 是否还有下一个元素。it.next() 方法会返回迭代器指向的下一个元素（即列表中的下一个 Integer 元素）。
2、实现了Iterator接口就能使用迭代器进行打印。
3、ListIterator接口继承了Iterator接口，也就是说有更多的方法。

嵌套列表

代码案例

1、

public static void test() {List<List<Integer>> list = new ArrayList<>();List<Integer> list0 = new ArrayList<>();list0.add(10);list0.add(100);list0.add(1000);List<Integer> list1 = new ArrayList<>();list1.add(20);list1.add(200);List<Integer> list2 = new ArrayList<>();list2.add(30);list2.add(300);List<Integer> list3 = new ArrayList<>();list3.add(40);list3.add(400);list3.add(4000);List<Integer> list4 = new ArrayList<>();list4.add(50);list4.add(500);list.add(list0);list.add(list1);list.add(list2);list.add(list3);list.add(list4);for(int i = 0; i < list.size();i++) {for (int j = 0; j < list.get(i).size(); j++) {System.out.print(list.get(i).get(j)+" ");}System.out.println();}System.out.println();
}

输出：
10 100 1000
20 200
30 300
40 400 4000
50 500

关系大致如图所示：

2、

public static List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();//定义起始行List<Integer> list0 = new ArrayList<>();list0.add(1);ret.add(list0);//定义后面的行for (int i = 1; i < numRows; i++) {//定义每行列表List<Integer> currentRow = new ArrayList<>();//第一个元素都是1currentRow.add(1);//中间操作List<Integer> preRow = ret.get(i - 1);for (int j = 1; j < i; j++) {//按照规律添加元素currentRow.add(preRow.get(j) + preRow.get(j-1));}//每行最后一个元素都是1currentRow.add(1);//currentRow行存储到ret中ret.add(currentRow);}return ret;
}public static void main(String[] args) {List<List<Integer>> list = generate(5);for (List<Integer> integers : list) {for (Integer integer : integers) {System.out.print(integer + " ");}System.out.println();}System.out.println();
}

关系大致如图所示：

代码解释：

1、本质上是一个二维列表，可用于存储和操作二维数据结构。
2、代码二，实现的是杨辉三角的输出。

ArrayList顺序表的优缺点

优点

随机访问效率高，借助索引可以直接访问ArrayList里的任意元素，时间复杂度为O(1)。

缺点

1、扩容的时候可能会造成过多的内存消耗
2、插入和删除效率低，需要对元素进行插入与删除时，要移动后续的元素，时间复杂度为O(n)。