建网站公司汽车六万公里是否累变速箱油,制作wordpress文章模板,一个专门做ppt的网站,国内网站建设代理文章目录 一、 了解线性表和顺序表区别1.线性表2.顺序表 二、模拟实现1.定义接口2.定义MyArrayList3.成员变量以及构造方法4.实现打印数组5.实现add方法6.实现查找某个数是否存在contains或者某个数的下标indexOf7.获取或更改pos位置的值 get和set8.获取数组大小 size9.删除某个… 文章目录 一、 了解线性表和顺序表区别1.线性表2.顺序表 二、模拟实现1.定义接口2.定义MyArrayList3.成员变量以及构造方法4.实现打印数组5.实现add方法6.实现查找某个数是否存在contains或者某个数的下标indexOf7.获取或更改pos位置的值 get和set8.获取数组大小 size9.删除某个值 remove10.清空 clear 三、ArrayList源码如何做的1.成员变量2.构造方法1、有参数的构造2、无参数的构造3、数组构造 4.add5.addAll6.remove7.subList8.迭代器 iterator 一、 了解线性表和顺序表区别
1.线性表
线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列… 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。
2.顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。
二、模拟实现
1.定义接口
package mylist;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();}
2.定义MyArrayList
MyArrayList要继承上面的接口并实现现在是框架。
package mylist;public class MyArrayList implements IList{Overridepublic void add(int data) {}Overridepublic void add(int pos, int data) {}Overridepublic boolean contains(int toFind) {return false;}Overridepublic int indexOf(int toFind) {return 0;}Overridepublic int get(int pos) {return 0;}Overridepublic void set(int pos, int value) {}Overridepublic void remove(int toRemove) {}Overridepublic int size() {return 0;}Overridepublic void clear() {}Overridepublic void display() {}
}
3.成员变量以及构造方法 //储存元素的数组public int [] elem;//当前顺序表有多少个元素public int usedSize;//默认数组大小public static final int DEFAULT_SIZE 10;public MyArrayList() {this.elem new int [DEFAULT_SIZE];}public MyArrayList(int capacity ) {this.elem new int[capacity];}4.实现打印数组 public void display() {for(int i 0;iusedSize;i){System.out.print(this.elem[i] );}System.out.print(\n);}5.实现add方法
在添加之前需要判断是否满单独将判断是否满方法实现方法名为isFull如果满了对数组扩容所以我可以实现检查容量方法如果满了就扩容没满就什么都不做没满添加。 重复上面操作对于在pos位置添加要判断pos如果合法就把后面向后挪一位再对于pos位置添加数据。 不合法抛出异常。 public class PosIllegality extends RuntimeException{public PosIllegality(String msg){super(msg);}
}
---------------------------------------------------------------------------------------public boolean isFull(){if(usedSizeelem.length){return true;}return false;}private void checkCapacity(){if(isFull()) {//扩容elem Arrays.copyOf(elem,elem.length*2);}}Overridepublic void add(int data) {checkCapacity();elem[usedSize] data;}private void checkPosOnAdd(int pos){if(posusedSize||pos0){System.out.println(不合法);throw new PosIllegality(插入元素下标异常pos);}}Overridepublic void add(int pos, int data) {try{checkPosOnAdd(pos);}catch (PosIllegality e){e.printStackTrace();return ;}checkCapacity();for(int i usedSize;ipos;i--){elem[i] elem[i-1];}elem[pos] data;}
测试 public static void main(String[] args) {MyArrayList myArrayList new MyArrayList();myArrayList.add(1);myArrayList.add(2);myArrayList.add(3);myArrayList.add(4);myArrayList.add(5);myArrayList.add(6);myArrayList.add(7);myArrayList.add(8);myArrayList.add(9);myArrayList.add(10);myArrayList.add(11);myArrayList.add(0,0);myArrayList.add(1,-1);myArrayList.display();}6.实现查找某个数是否存在contains或者某个数的下标indexOf
首先得判断数组是否为空可以单独实现是否为空的方法isEmpty其次再寻找目标数。 注意如果是引用类型要重写这个方法比较不能直接比较要调用比较的方法 public boolean isEmpty(){if(usedSize0){return true;}return false;}Overridepublic boolean contains(int toFind) {if(isEmpty()){return false;}for(int i 0;iusedSize;i){if(elem[i]toFind){return true;}}return true;}Overridepublic int indexOf(int toFind) {if(isEmpty()){return -1;}for(int i 0;iusedSize;i){if(elem[i]toFind){return i;}}return -1;}7.获取或更改pos位置的值 get和set
首先检查pos的合法性单独写个检查pos的方法如果不合法抛出异常返回或修改pos位置的值。 private void checkPosOnGet(int pos){if(pos0||posusedSize){System.out.println(不合法);throw new PosIllegality(获取元素下标异常pos);}}Overridepublic int get(int pos) {try {checkPosOnGet(pos);}catch (PosIllegality e){e.printStackTrace();return -1;}return elem[pos];}
private void checkPosOnSet(int pos){if(pos0||posusedSize){throw new PosIllegality(获取元素下标异常pos);}}Overridepublic void set(int pos, int value) {
// try {
// checkPosOnSet(pos);
// }catch (PosIllegality e)
// {
// e.printStackTrace();
// return ;
// }checkPosOnSet(pos);elem[pos] value;}8.获取数组大小 size Overridepublic int size() {return usedSize;}9.删除某个值 remove Overridepublic void remove(int toRemove) {int index indexOf(toRemove);if(index-1){System.out.println(没有这数字);return;}for(int i index;iusedSize-1;i){elem[i] elem[i1];}usedSize--;}10.清空 clear Overridepublic void clear() {usedSize 0;}思考如果存的是引用数据能不能直接将usedSize0? 不能如果数组里面装的是引用数据类型就会造成内存泄漏。 JVM当中回收算法有很多 当前对象没有人引用的时候1.elemnull 2.将每一个下标的值 elem[i]null
三、ArrayList源码如何做的
1.成员变量 elementData为存储元素的数组是物理空间连续的内存地址。 size为数组存储元素的个数。
2.构造方法
1、有参数的构造 2、无参数的构造 发现无参数构造不给任何空间,那么add时数据放哪里
3、数组构造 Collection是什么 请看下图 ? extends E表示通配符的上级是E的子类或本身 举例 ArrayList list new ArrayList() ArrayListlist2 new ArrayList(list); ?就表示list的类型Interger,而E就是list2的类型是Number符合子类。
4.add 这里可以看见add调用了ensureCapacityInternal,size为当前存储的个数当前还是没有任何插入size为0 minCapacity为1 看上面无参数构造可以知道if成立此时返回了默认大小DEFAULT_CAPACITY也就是10,返回10。 看下面代码不难发现grow就是扩容代码oldCapacity1就是除2,ArraryList是1.5倍扩容。 总结 1、 如果没有分配内存第一次add会分配大小为10的内存 2、 ArrayList是1 .5倍扩容
5.addAll public static void main(String[] args) {ArrayListInteger arrayList1 new ArrayList();arrayList1.add(1);arrayList1.add(2);arrayList1.add(3);ArrayListInteger arrayList2 new ArrayList();arrayList2.add(4);arrayList2.add(5);arrayList2.add(6);arrayList1 .addAll(arrayList2);arrayList2.addAll(1,arrayList1);System.out.println(arrayList1);System.out.println(arrayList2);}6.remove 注意传数字只会删除对应下标的值而传对象才会删对应的对象。 public static void main(String[] args) {ArrayListInteger arrayList1 new ArrayList();arrayList1.add(1);arrayList1.add(2);arrayList1.add(3);arrayList1.remove(2);System.out.println(arrayList1);arrayList1.remove(new Integer(1));System.out.println(arrayList1);}7.subList public static void main(String[] args) {ArrayListInteger list new ArrayList();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);System.out.println(list);ListInteger list1 list.subList(1,3);System.out.println(list1);}注意 1.为左闭右开 2.返回的位List类型 3.截取不会产生新的对象对返回的修改被截取的也会修改
8.迭代器 iterator public static void main(String[] args) {ArrayListInteger list new ArrayList();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);IteratorInteger it list.iterator();while(it.hasNext()){System.out.print(it.next() );}}
