目录

一，线性表

二，顺序表

1.接口实现

三，ArrayList简介

四，ArrayList使用

1.ArrayList的构造

2.ArrayList常见操作

3.ArrayList的遍历

4.ArrayList的扩容机制

五，ArrayLisit的具体使用

杨辉三角

一，线性表

线性表 （ linear list ） 是 n 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...

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

二，顺序表

1.接口实现

接口部分：

public interface IList {// 新增元素,默认在数组最后新增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 位置的元素设为 valuepublic void set(int pos, int value);//删除第一次出现的关键字keypublic void remove(int toRemove);// 获取顺序表长度public int size();// 清空顺序表public void clear();// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的public void display();//判断顺序表是否已满public boolean isFull();//判断顺序表是否为空public boolean isEmpty();
}

接口实现：

import java.util.Arrays;public class MyArrayList implements IList{public int[] elem;public int usedSize;public static final int DEFINE_SIZE = 10;public MyArrayList() {this.elem = new int[DEFINE_SIZE];}public MyArrayList(int capacity) {this.usedSize = capacity;}@Override//新增元素,默认在数组最后新增//1.检查数组是否已满//2.满了扩容，未满新增//usedSize++public void add(int data) {if (isFull()) {elem = Arrays.copyOf(elem,2 * elem.length);}this.elem[this.usedSize] = data;this.usedSize++;}public boolean isFull() {return this.usedSize ==elem.length;}@Override//在 pos 位置新增元素//1.检查数组是否已满//2.满了扩容//3.未满：在指定位置新增，原位置有元素就向后挪//4.usedSize++public void add(int pos, int data) {if (isFull()) {elem = Arrays.copyOf(elem,2 * elem.length);}//新增int i = this.usedSize;while (i > pos) {elem[i] = elem[i-1];i--;}this.elem[pos] = data;usedSize++;}@Override// 判定是否包含某个元素//1.顺序表是否为空//2.查找元素public boolean contains(int toFind) {if (isEmpty()) {return false;}//查找元素if (findVal(toFind) != 0) {return true;}return false;}public int findVal(int val) {for (int i = 0; i < elem.length; i++) {if (elem[i] == val) {return i;}}return 0;}public boolean isEmpty() {return usedSize == 0;}@Override// 查找某个元素对应的位置// 1.判断是否为空// 2.为空抛空List异常// 3.查找元素// 4.获取下标public int indexOf(int toFind) throws EmptyListException{if (isEmpty()) {throw new EmptyListException("空List异常");}//查找if (findVal(toFind) == 0) {//查询不到异常throw new NotFindException("NotFindException");}return findVal(toFind);}@Override// 获取 pos 位置的元素// 1.判断是否为空// 2.判断pos位置是否合法// 3.获取public int get(int pos) {if (isEmpty()) {throw new EmptyListException("空List异常");}if (checkPos(pos)) {//pos位置不合法throw new PosException("pos位置不合法");}return this.elem[pos];}private boolean checkPos(int pos) {if (pos < 0 || pos >= this.usedSize) {return true;}return false;}@Override// 给 pos 位置的元素设为 value// 1.判断是否为空// 2.判断pos位置是否合法// 3.设置public void set(int pos, int value) {if (isEmpty()) {throw new EmptyListException("空List异常");}if (checkPos(pos)) {//pos位置不合法throw new PosException("pos位置不合法");}this.elem[pos] = value;}@Override// 删除第一次出现的关键字key// 是否为空？// 查找关键字public void remove(int toRemove) {if (isEmpty()) {throw new EmptyListException("空List异常");}for (int i = indexOf(toRemove);i < this.usedSize - 1;i++) {elem[i] = elem[i+1];}usedSize--;}@Override// 获取顺序表长度public int size() {return this.usedSize;}@Override// 清空顺序表public void clear() {this.usedSize = 0;}@Overridepublic void display() {System.out.print("[");if (this.usedSize == 0) {System.out.println("]");}for (int i = 0; i < this.usedSize; i++) {if (i == this.usedSize - 1) {System.out.println(this.elem[i] + "]");} else {System.out.print(this.elem[i] + ",");}}}
}

三，ArrayList简介

class Solution {//求杨辉三角方法public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();//二维数组List<Integer> list = new ArrayList<>();list.add(1);ret.add(list);for (int i = 1; i < numRows; i++) {List<Integer> curRow = new ArrayList<>();//当前行List<Integer> prevRow = ret.get(i-1);//上一行curRow.add(1);//当前行首个元素为1for (int j = 1; j < i; j++) {int val = prevRow.get(j-1) + prevRow.get(j);curRow.add(val);}curRow.add(1);//当前行最后一个元素为1ret.add(curRow);}return ret;}
}
public class Test {//方法使用public static void main(String[] args) {Solution solution = new Solution();List<List<Integer>> mylist = new ArrayList<>();mylist = solution.generate(3);for (int i = 0; i < 3; i++) {List<Integer> arr = mylist.get(i);System.out.println(arr);}}
}