怎样建设智能网站,福建搜索引擎推广方法,搜索引擎seo是什么,微信网站搭建价格找往期文章包括但不限于本期文章中不懂的知识点#xff1a; 个人主页#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏#xff1a;数据结构#xff08;Java版#xff09; 顺序表的学习#xff0c;点我
上面这篇博文是关于顺序表的基础知识#xff0c;以及顺序表的实现。…找往期文章包括但不限于本期文章中不懂的知识点 个人主页我要学编程(ಥ_ಥ)-CSDN博客 所属专栏数据结构Java版 顺序表的学习点我
上面这篇博文是关于顺序表的基础知识以及顺序表的实现。
目录
手动实现顺序表的源码
分析Java 8 的 ArrayList 的源码
字段
构造方法
ArrayList本身的扩容机制和分配内存机制
ArrayList常见操作
ArrayList的遍历
普通for循环遍历
for-each遍历
toString方法遍历
迭代器遍历 手动实现顺序表的源码
下面是Java版的顺序表源码
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];}/*** 打印顺序表:* 根据usedSize判断即可*/public void display() {for (int i 0; i this.usedSize; i) {System.out.print(this.elem[i] );}System.out.println();}// 新增元素,默认在数组最后新增public void add(int data) {// 增加元素之前得先判断数组是否已满if (isFull()) {expansion();}// 尾插数据不需要判断 pos 位置是否合法elem[this.usedSize] data;}// 扩容private void expansion() {// 原来数组的2倍扩容this.elem Arrays.copyOf(this.elem, 2 * this.elem.length);}/*** 判断当前的顺序表是不是满的* return true:满 false代表空*/public boolean isFull() {// 判断这个数组的有效元素个数是否等于数组的长度return this.usedSize this.elem.length;}private boolean checkPosInAdd(int pos) {if (pos 0 || pos this.usedSize) {return false;}return true;//合法}// 在 pos 位置新增元素public void add(int pos, int data) throws PosofAddException{if (!checkPosInAdd(pos)) {throw new PosofAddException(add(int pos, int data) pos位置不合法);}// 判断是否为尾插if (pos this.usedSize) {add(data);}else {// 开始移除元素从后往前移除for (int i this.usedSize; i pos; i--) {this.elem[i] this.elem[i-1];}// 开始插入数据this.elem[pos] data;this.usedSize;}}// 判定是否包含某个元素public boolean contains(int toFind) {// 先判断这个数组是否有元素if (isEmpty()) {return false;}for (int i 0; i this.usedSize; i) {if (this.elem[i] toFind) {return true;}}return false;}// 查找某个元素对应的位置public int indexOf(int toFind) {for (int i 0; i this.usedSize; i) {if (this.elem[i] toFind) {return i;}}return -1;}// 获取 pos 位置的元素public int get(int pos) throws PosofGetException{if (pos 0 || pos this.usedSize) {throw new PosofGetException(get(int pos) pos位置不合法);}return this.elem[pos];}private boolean isEmpty() {// 有效数据个数为0就是为空return this.usedSize 0;}// 给 pos 位置的元素设为【更新为】 valuepublic void set(int pos, int value) throws PosofSetException{// 先得判断这个 pos 位置是否合法if (pos 0 || pos this.usedSize) {throw new PosofSetException(set(int pos, int value) 要修改的位置不合法);}this.elem[pos] value;}/*** 删除第一次出现的关键字key* param key*/public void remove(int key) throws PosofRemoveException{int pos indexOf(key); // 下标if (pos 0) {throw new PosofRemoveException(remove(int key) 没有您要删除的数据);}for (int i pos; i this.usedSize - 1; i) {// 后一个位置往前覆盖this.elem[i] this.elem[i1];}this.usedSize--;}// 获取顺序表长度public int size() {return this.usedSize;}// 清空顺序表public void clear() {// 由于存放的是基本数据类型直接清空即可this.usedSize 0;// 如果存放的是引用数据类型就得通过for循环遍历把数组的内容置为null// 注意如果直接把数组置为null的话就会存在安全问题而且源码也是遍历的方式}
}异常
PosofAddException
public class PosofAddException extends RuntimeException{public PosofAddException() {}public PosofAddException(String msg) {super(msg);}
}PosofGetException
public class PosofGetException extends RuntimeException{public PosofGetException() {}public PosofGetException(String msg) {super(msg);}
}
PosofSetException
public class PosofSetException extends RuntimeException{public PosofSetException() {}public PosofSetException(String msg) {super(msg);}
}PosofRemoveException
public class PosofRemoveException extends RuntimeException{public PosofRemoveException() {}public PosofRemoveException(String msg) {super(msg);}
}分析Java 8 的 ArrayList 的源码
实现了咱们自己写的顺序表了之后就该来看Java本身的源码是怎么写的以及与我们的有什么不同注意由于Java 17封装性太强不好观看源码因此下面的源码来自Java 8。
字段 elementData 就是我们自己实现的 elem 数组。
size 就是 usedSize 也就是这个数组的有效元素的个数。
构造方法
Java 8 实现的顺序表有三个构造方法。
带有一个 int 类型的参数的构造方法 不带参数的构造方法 带一个 Collection 类型的参数的构造方法
下面的是其源码 首先我们得知道Collection 到底是这个啥 根据上面这个图可以得知Collection 是一个接口。
上面的参数先不看泛型那就是Collection c 这个意味着只要实现了Collection 接口就可以被当成实参传过来。而从上图的关系可知ArrayList 继承了 AbstractLIst 这个抽象类 并且实现了LIst这个接口而 LIst 这个接口拓展了 Collection 这个接口的功能。也就意味着 ArrayList 这个类实现了 Collection 这个接口。那么 ArrayList 就可以被当成参数传过来。
接下来就是了解 ? extends E 就可以当成是被传过来的 ArrayList 中的泛型也就是说被传过来的 ArrayList 中的泛型要是 E 或者 E的子类。例如 了解了这些我们就来看源码吧。这个源码的大概意思是把传入的 ArrayList 中的元素给全部拷贝到原来的 ArrayList 的后面。
ArrayList本身的扩容机制和分配内存机制
既然我们在创建一个顺序表的时候原本是空那么当我们去增加元素的时候扩容的机制又是如何呢 上面是分析过程可忽略总之得出了下面这个结论
当顺序表为空时我们如果去增加元素就会初始化一个大小10的数组。并且数组在满了之后会按照1.5倍的扩容方式来扩容。如果用户所需大小超过预估1.5倍大小则按照用户所需大小扩容。
ArrayList常见操作
ArrayList常用方法 boolean add(E e)尾插evoid add(int index, E element)将 e 插入到 index 位置boolean addAll(Collection? extends E c)将c 中的元素进行尾插E remove(int index)删除 index 位置元素boolean remove(Object o)删除遇到的第一个oE get(int index)获取下标index位置元素E set(int index, E element)将下标 index 位置元素改为 elementvoid clear()清空boolean contains(Object o判断是否在顺序表中int indexOf(Object o)返回第一个o所在下标int lastlndexOf(Object o)返回最后一个o的下标ListE subList(int fromlndex, int tolndex)截取部分list
大部分方法我们都很熟悉。因此这里只展示 addAll()方法 和 subList 方法。 addAll () 方法可以实现 ArrayList 的带Collection 类型的参数的构造方法。
从上面打印的结果可以看出来ArrayList 是重写了toString 方法的。 从这里我们就可以看出来被分割的数组应该是下面这样 ArrayList的遍历
普通for循环遍历
public class Test {public static void main(String[] args) {ArrayListInteger arrayList new ArrayList();arrayList.add(1);arrayList.add(2);arrayList.add(3);for (int i 0; i arrayList.size(); i) {System.out.print(arrayList.get(i) );}}
}
for-each遍历
public class Test {public static void main(String[] args) {ArrayListInteger arrayList new ArrayList();arrayList.add(1);arrayList.add(2);arrayList.add(3);for (Integer x : arrayList) {System.out.print(x );}}
}
toString方法遍历
public class Test {public static void main(String[] args) {ArrayListInteger arrayList new ArrayList();arrayList.add(1);arrayList.add(2);arrayList.add(3);System.out.println(arrayList.toString());}
}
迭代器遍历
public class Test {public static void main(String[] args) {ArrayListInteger arrayList new ArrayList();arrayList.add(1);arrayList.add(2);arrayList.add(3);// 调用iterator方法生成一个迭代器用IteratorE来接收IteratorInteger integerIterator arrayList.iterator();// 如果下一个元素有值话就进入while循环并且打印下一个值最后自己往后走while (integerIterator.hasNext()) {System.out.print(integerIterator.next() );}}
}
只要是实现了 Iterator 接口就可以使用迭代器的方式来遍历。就是下面这张图 好啦本期 数据结构之ArrayList与顺序表上的学习就到此结束啦我们下一期再一起学习吧
