Java数据结构 & ArrayList顺序表
我们平时很喜欢使用的数组，就是顺序表！
下面我们将以 “模拟ArrayList” 的视角来盘一盘顺序表吧！
1. ArrayList的模拟
首先，这个类的功能如下：
能够完成增删改查基础操作
能够自动扩容（隐性，让这个顺序表能够存储足够多的数据）
在一个类中放数据，这样可以给类加上一些方法，那么这个类的功能就更加丰富且有针对性，就像包装起来的一组东西（包括数组整体）
在后面的链表集合类LinkedList中，虽然链表可用链表头结点表示（代表），但是这个类就是节点类吗，节点只是存储的方式，而集合类是包装起来的一组东西，即对象，通过这个对象，使用丰富的属性（包括这个链表整体）和方法
1.1 ArrayList的基础模板
总的模板如下（具体个别方法在后面）
public class MyArrayList { public int[] elem; public int usedSize;//0 //默认容量 private static final int DEFAULT_SIZE = 10; public MyArrayList() { this.elem = new int[DEFAULT_SIZE]; } public MyArrayList(int size) { if (size <= 0) { throw new IndexException("MyArraylist"); } this.elem = new int[size]; } /** * 打印顺序表: * 根据usedSize判断即可 */ public void display() { } // 新增元素,默认在数组最后新增 public void add(int data) { } public boolean isFull() { } /** * 判断当前的顺序表是不是满的！ * * @return true:满 false代表空 */ private boolean checkPosInAdd(int pos) { } // 在 pos 位置新增元素 public void add(int pos, int data) { } // 判定是否包含某个元素 public boolean contains(int toFind) { } // 查找某个元素对应的位置 public int indexOf(int toFind) { } // 获取 pos 位置的元素 public int get(int pos) { } private boolean isEmpty() { } // 给 pos 位置的元素设为【更新为】 value public void set(int pos, int value) { } /** * 删除第一次出现的关键字key * * @param key */ public void remove(int key) { } // 获取顺序表长度 public int size() { } // 清空顺序表 public void clear() { } }
1.1 属性
public int[] elem;
public int usedSize;//0
//默认容量
private static final int DEFAULT_SIZE = 10;
elem 顺序表“本体”
usedSize 顺序表已添加的有效数据
DEFAULT_SIZE（不带参数的构造方法，在构造数组时的默认容量）
1.2 方法
1.2.1 构造方法
非正常操作的异常
public class IndexException extends RuntimeException{ public IndexException() { } public IndexException(String message) { super(message); } }
public MyArrayList() { this.elem = new int[DEFAULT_SIZE]; } public MyArrayList(int size) { if (size <= 0) { throw new IndexException("MyArraylist"); } this.elem = new int[size]; }
不带参数的构造方法
以默认值构造数组
带参数的构造方法
以传入的值作为起始容量
1.2.2 遍历方法
这个没啥好说的 /** * 打印顺序表: * 根据usedSize判断即可 */ public void display() { if(isEmpty()) { System.out.println("[]"); } else{ System.out.print("[ "); for (int i = 0; i < this.usedSize; i++) { if(i == usedSize - 1) { System.out.print(this.elem[i] + " ]"); }else { System.out.print(this.elem[i] + ", "); } } System.out.println(); } }
1.2.3 增加元素方法以及判断是否满方法
我们只需要在elem[usedSize] = data即可
然后usedSize++，这样就刚好添加到数组的末尾
但是，如果数组满了的话怎么办？
那就要扩容一下了
copyOf()这个方法可以动态调整数组的大小，对比于C语言，这个方法更加全能
elem 2 * usedSize 被拷贝的数组 新数组的大小（我这里扩大两倍） // 新增元素,默认在数组最后新增 public void add(int data) { if (isFull()) { //满了即扩容 elem = Arrays.copyOf(elem, 2 * usedSize); } elem[usedSize] = data; usedSize++; } //is...() 这种命名一般返回boolean类型，起判断作用 public boolean isFull() { if (usedSize == elem.length) { return true; } else { return false; } }
我们还可以在指定位置进行插入（需要检验下标是否合理）
我们需要将对应位置以及后面的元素都向后挪动，腾出一个位置给待插入的元素（检验是否需要扩容）
从尾挪动
//检验下标是否合理的方法 private boolean checkPosInAdd(int pos) { if (pos < 0 || pos > this.usedSize) { return false; } return true;//合法 } // 在 pos 位置新增元素，构成重载 //pos刚好在末尾，是允许的 public void add(int pos, int data) { if (this.isFull()) { elem = Arrays.copyOf(elem, 2 * usedSize); } if (checkPosInAdd(pos)) { usedSize++; for (int i = usedSize; i > pos; i--) { elem[i] = elem[i - 1]; } elem[pos] = data; }else { throw new IndexException("add"); } }
1.2.4 查找方法
第一个查找-> 找得到返回true 否则false
第二个查找-> 找得到返回对象下标，找不到返回-1（-1下标在java中完全用不了）
C语言中，访问下标arr[-1] = (arr - 1);
// 判定是否包含某个元素 public boolean contains(int toFind) { for (int i = 0; i < this.usedSize; i++) { if (elem[i] == toFind) { return true; } } return false; } // 查找某个元素对应的位置 public int indexOf(int toFind) { for (int i = 0; i < this.usedSize; i++) { if (elem[i] == toFind) { return i; } } return -1; }
1.2.5 获取下标元素方法
// 获取 pos 位置的元素 public int get(int pos) { if (checkPosInAdd(pos)) { if (pos == usedSize) { //下标不合理就会抛异常 throw new IndexException("get"); } else { //返回对应元素的值 return elem[pos]; } } else { //下标不合理就会抛异常 throw new IndexException("get"); } }
1.2.6 更新下标对应元素方法
// 给 pos 位置的元素设为【更新为】 value // 即使pos刚好对应末尾，只要是“空的”就不能够设置 public void set(int pos, int value) { if (checkPosInAdd(pos)) { if (pos == usedSize) { throw new IndexException("set"); } else { this.elem[pos] = value; } } else { throw new IndexException("set"); } }
1.2.7 是否空以及获取顺序表元素个数方法
private boolean isEmpty() { return usedSize == 0; // 获取顺序表长度 public int size() { return usedSize; }
1.2.8 删除元素方法
对于第一次出现的key值，进行删除
后面的所有元素要把这个空位补上去（也就是一个个挪动过去）
从头挪动
/** * 删除第一次出现的关键字key * * @param key */ public void remove(int key) { int index = indexOf(key); if (index == -1) { System.out.println("Can‘t find"); } else { for (int i = index; i < usedSize - 1; i++) { this.elem[i] = this.elem[i + 1]; } usedSize--; } }
清空顺序表的方法：
// 清空顺序表 public void clear() { this.elem = new int[DEFAULT_SIZE]; this.usedSize = 0; }
1.3 测试
public class Test { public static void main(String[] args) { MyArrayList myArrayList = new MyArrayList(5); myArrayList.display(); myArrayList.add(1); myArrayList.add(2); myArrayList.add(3); myArrayList.display(); System.out.println(myArrayList.indexOf(3)); System.out.println(myArrayList.contains(3)); System.out.println(myArrayList.indexOf(4)); System.out.println(myArrayList.contains(4)); myArrayList.add(4); myArrayList.add(5); myArrayList.add(6); myArrayList.display(); myArrayList.add(2, 99); System.out.println(myArrayList.get(2)); myArrayList.display(); myArrayList.set(3, 99); myArrayList.display(); myArrayList.remove(4); myArrayList.display(); System.out.println(myArrayList.size()); myArrayList.clear(); myArrayList.display(); } }
测试结果正常！
2. ArrayList的使用以及系统源码的一些细节
E 是一个泛型类（不能用基本数据类型）
List<Integer> list = new ArrayList<>();
这个是最常用的使用方式， 一般实例化List接口，这样功能更加具体
如果是自定义类的话，一定要重写equals()方法，因为在查找的时候，判断是否相同尤为重要
重写compareTo()方法更好，在用工具类Collections去排序的时候要用到
2.1 属性
重点：
默认数组大小，DEFAULT_CAPACITY
本体数组，elementData[]
有效元素个数，size
2.2.1 构造方法
带参数int的构造方法
提供自定义数组大小，非法下标则抛异常
等于0的情况，则给一个空数组
不带参数的构造方法
以默认的数组大小构造数组
提供一整个集合类对象作为参数的构造方法
即直接将这个集合类对象的所有元素，拷贝一份下来整合成顺序表返回
但是这个集合类对象的泛型类型必须是E的子类或者E本身
2.2.2 常用方法
高亮即重点
方法 解释
boolean add(E e) 尾插e,（返回true）
void add(int index, E element) 指定位置插入元素
boolean addAll(Collection c) 尾插一集合的所有元素
E remove(int index) 删除指定下标的元素
boolean remove(Object o) 删除第一个指定元素（不存在返回false）
E get(int index) 获取下标对应元素
E set(int index, E element) 设置下标对应元素（必须存在）
void clear() 清空顺序表
boolean contains(Object o) 判断此元素是否存在于顺序表
int indexOf(Object o) 返回第一个对应元素下标
int lastIndexOf(Object o) 从后往前找第一个对应元素的下标
List subList(int fromIndex, int toIndex) 截取对应顺序表（sub形式的方法一般返回的对象与原对象是共用的）
使用这些方法的方式更上一部分相似
2.3 顺序表的遍历
2.3.1 for-each循环(不是foreach方法)
for(Integer i : list) { System.out.print(i + " "); }
2.3.2 for循环
for(int i = 0; i < list.size(); i++) { System.out.print(list.get(i) + " "); }
2.3.3 listIterator() =》Iterator 迭代器实现
了解即可
Iterator<Integer> iterator = list.listIterator(); while(iterator.hasNext()) { System.out.print(iterator.next() + " "); }
2.3.4 直接sout（快捷）打印
前提是知道泛型类型的打印方法！！！
所以我们的自定义类型就必须重写toString() 方法
System.out.print(list);
不难发现，List，ArrayList两个类都没有重写toString方法
那么这个类的对象是怎么打印的那？
其实可以在这之前已经重写好了
2.4 toArray() 方法
不带参数的构造方法，直接返回对应的数组，数据类型为Object[] 需要强制类型转化为对应的类型，（由于此时的Object是对应的类型实例化的，所以不会有问题）
System.out.println(list.toArray()[0] instanceof Integer);
带参数，即直接对提供的数组进行修改，返回值跟上面一样
注意：不能用基本数据类型的数组，且基本数据类型数组与对象数组之间不能进行拆箱装箱
2.5 ArrayList扩容机制
简单的来说就是
满了扩容
用copyOf()1.5倍扩容(位操作符速度快)
超过最大容量报错
3. 实例
到这里，ArrayList的基本使用与原理知识已经讲解完了，
下面是一个小项目，可以去提高自己对顺序表的理解
大家可以通过我写的博客去理解和完成
3.1 扑克牌系统-斗牛
(21条消息) JavaProject & 洗牌斗牛系统_Carefree_State的博客-CSDN博客
3.2 拓展：八皇后问题（非必要方法，只是结合ArrayList去解决罢了）
(21条消息) 《八皇后问题》& Java数据结构 & JavaProject & JavaOJ题集_Carefree_State的博客-CSDN博客
3.3 杨辉三角
二维顺序表的表示（解题类似二维数组）
class Solution { public static List<List<Integer>> generate(int numRows) { List<List<Integer>> list = new ArrayList(); for(int i = 0; i < numRows; i++) { list.add((List<Integer>)new ArrayList()); for(int j = 0; j < i + 1; j++) { if(j == 0 || i == j) { list.get(i).add(1); }else if(i > 1 && j > 0 && j < i) { list.get(i).add(list.get(i - 1).get(j - 1) + list.get(i - 1).get(j)); } } } return list; } } public class Test { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int scan = scanner.nextInt(); List list = Solution.generate(scan); System.out.println(list); } }
