从零手写顺序表到深入理解ArrayList：Java数据结构核心实践指南

顺序表理解顺序表在物理内存结构是连续的 通常用数组 完成增删查改 我们需要删除和修改的时候 必须要遍历整个数组 效率不高 于是引出来链表顺序表的模拟package Book3;import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class nn{private int[] array;//数组private int size;//数组个数private int a10;// 默认构造方法nn(){// 将顺序表的底层容量设置为initcapacity//数组初始化this.size0;this.arraynew int[a];}//扩容数组private void k(){array Arrays.copyOf(this.array,2*this.array.length);}//判断是否满// 新增元素,默认在数组最后新增public void add(int data) {//先判断是否满 如果没有满则直接写入if(this.size1array.length){k();}array[this.size]data;this.size;}private void zuobiao(int pos) throws zuobiao{if(pos0||possize){System.out.println(坐标插入不合法,请输入0到size的数);throw new zuobiao(坐标位置不合法);}}//在 pos 位置新增元素public void add(int pos, int data) {//先检查拆入的坐标合法性zuobiao(pos);this.array[pos]data;this.size;}// 判定是否包含某个元素public boolean contains(int toFind) {for (int i 0; i this.size; i) {if (array[i]toFind){System.out.println(找到了);return true;}}return false;}// 查找某个元素对应的位置public int indexOf(int toFind) {for (int i 0; i this.size; i) {if (array[i]toFind){System.out.println(对应的坐标 i);return i;}}return -1; }// 获取 pos 位置的元素public int get(int pos) {//先判断输入的坐标的合法性zuobiao(pos);return array[pos];}// 给 pos 位置的元素设为 valuepublic void set(int pos, int value) {zuobiao(pos);this.array[pos]value;}//删除第一次出现的关键字keypublic void remove(int toRemove) {int b0;for (int i 0; i this.size; i) {if(array[i]toRemove){bi;break;}}for (int i b; i size-1; i) {array[i]array[i1];}this.size--;}//获取顺序表长度public int size() { return array.length; }// 清空顺序表public void clear() {this.size0;}// 打印顺序表注意该方法并不是顺序表中的方法为了方便看测试结果给出的public void display() {//判断数组是否为空if(this.size0){System.out.println(数组为空);return;}for (int i0;ithis.size;i){System.out.println(this.array[i]);}}//int indexOf(Object o) 返回第一个 o 所在下标public int frinstindexof1(int o){for (int i 0; i this.size; i) {if(array[i]o){System.out.println(找到了o下标为i);return i;}}return 0;}//int lastIndexOf(Object o) 返回最后一个 o 所在下标public int lastIndexof(int a){for (int isize; i 0 ; i--) {if (aarray[i]){System.out.println(找到了下标为i);return i;}}return 0;}// ListE subList(int fromIndex, int toIndex) 截取部分 list//左闭右开public List subList(int qishi,int jieshu){zuobiao(qishi);zuobiao(jieshu);List anew ArrayList();for (int i qishi; i jieshu-qishi ; i) {a.add(array[i]);}return a;}}class mm{public static void main(String[] args) {nn nnew nn();n.add(1);n.add(1);n.add(2);n.add(2);n.add(3);n.lastIndexof(2);System.out.println(n.subList(1, 3));}}ArraryListArrayListInteger anew ArrayList(); //无参构造 a.add(1); a.add(2); a.add(3); a.add(4); //有参构造 ArrayListInteger bnew ArrayList(a); System.out.println(b); //初始化数组容量 ArrayListInteger cnew ArrayList(20); System.out.println(c);1. ArrayList是以泛型方式实现的使用时必须要先实例化2. ArrayList实现了RandomAccess接口表明ArrayList支持随机访问3. ArrayList实现了Cloneable接口表明ArrayList是可以clone的4. ArrayList实现了Serializable接口表明ArrayList是支持序列化的5.和Vector不同ArrayList不是线程安全的在单线程下可以使用在多线程中可以选择Vector或者CopyOnWriteArrayList6. ArrayList底层是一段连续的空间并且可以动态扩容是一个动态类型的顺序表ArryaryList使用ArrayList cnew ArrayListInteger(); c.add(1); System.out.println(c);顺序表add运行底层 扩容机制顺序表中的数组是怎么给定容量 在什么时候给定容量的第一次进行分配空间是10如果数组存满的话则返回的个数1 11数组容量变为10如果不够以1.5倍扩容如果在不够 以用户实际为标准扩容//三种遍历顺序表的方式//for循环for (int i 0; i c.size(); i) {System.out.println(c.get(i));}//earhfor (Integer integer:c){System.out.println(integer);}//迭代器IteratorInteger f c.listIterator();//向前向后遍历的迭代器 接收while (f.hasNext()){//hasnext判断后面是否有元素System.out.println(f.next());//next指向下一个元素顺序表的优缺点分析优点支持快速随机访问、无需额外存储指针、缓存命中率高。缺点插入删除效率低、扩容成本高、需预分配空间可能导致浪费。