Java_简单模拟实现ArrayList_学习ArrayList

文章目录 一、 了解线性表和顺序表区别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位置元素设为value public void set (int pos,int value); //删除第一次出现的关键字key public void remove(int toRemove); //获取顺序表的长豆 public int size(); //清空顺序表 public void clear(); //打印顺序表，注意：该方法不是顺序表的方法，为了方便测试结果给出的 public void display(); } 2.定义MyArrayList

MyArrayList要继承上面的接口并实现，现在是框架。

package mylist; public class MyArrayList implements IList{ @Override public void add(int data) { } @Override public void add(int pos, int data) { } @Override public boolean contains(int toFind) { return false; } @Override public int indexOf(int toFind) { return 0; } @Override public int get(int pos) { return 0; } @Override public void set(int pos, int value) { } @Override public void remove(int toRemove) { } @Override public int size() { return 0; } @Override public void clear() { } @Override public 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;i<usedSize;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(usedSize>=elem.length){ return true; } return false; } private void checkCapacity() { if(isFull()) { //扩容 elem = Arrays.copyOf(elem,elem.length*2); } } @Override public void add(int data) { checkCapacity(); elem[usedSize++] = data; } private void checkPosOnAdd(int pos) { if(pos>usedSize||pos<0) { System.out.println("不合法！"); throw new PosIllegality("插入元素下标异常"+pos); } } @Override public void add(int pos, int data) { try{ checkPosOnAdd(pos); }catch (PosIllegality e) { e.printStackTrace(); return ; } checkCapacity(); for(int i = usedSize++;i>pos;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(usedSize==0) { return true; } return false; } @Override public boolean contains(int toFind) { if(isEmpty()) { return false; } for(int i = 0;i<usedSize;i++) { if(elem[i]==toFind) { return true; } } return true; } @Override public int indexOf(int toFind) { if(isEmpty()) { return -1; } for(int i = 0;i<usedSize;i++) { if(elem[i]==toFind) { return i; } } return -1; } 7.获取或更改pos位置的值 get和set

首先检查pos的合法性（单独写个检查pos的方法，如果不合法抛出异常），返回或修改pos位置的值。

private void checkPosOnGet(int pos) { if(pos<0||pos>=usedSize) { System.out.println("不合法！"); throw new PosIllegality("获取元素下标异常"+pos); } } @Override public int get(int pos) { try { checkPosOnGet(pos); }catch (PosIllegality e) { e.printStackTrace(); return -1; } return elem[pos]; } private void checkPosOnSet(int pos) { if(pos<0||pos>=usedSize) { throw new PosIllegality("获取元素下标异常"+pos); } } @Override public void set(int pos, int value) { // try { // checkPosOnSet(pos); // }catch (PosIllegality e) // { // e.printStackTrace(); // return ; // } checkPosOnSet(pos); elem[pos] = value; } 8.获取数组大小 size @Override public int size() { return usedSize; } 9.删除某个值 remove @Override public void remove(int toRemove) { int index = indexOf(toRemove); if(index==-1) { System.out.println("没有这数字"); return; } for(int i = index;i<usedSize-1;i++) { elem[i] = elem[i+1]; } usedSize--; } 10.清空 clear @Override public void clear() { usedSize = 0; }

思考如果存的是引用数据能不能直接将usedSize=0? 不能如果，数组里面装的是引用数据类型，就会造成内存泄漏。 JVM当中回收算法有很多 当前对象没有人引用的时候（1.elem=null 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就是扩容代码，oldCapacity>>1就是除2,ArraryList是1.5倍扩容。 总结： 1、 如果没有分配内存，第一次add会分配大小为10的内存 2、 ArrayList是1 .5倍扩容

5.addAll

public static void main(String[] args) { ArrayList<Integer> arrayList1 =new ArrayList<>(); arrayList1.add(1); arrayList1.add(2); arrayList1.add(3); ArrayList<Integer> 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) { ArrayList<Integer> 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) { ArrayList<Integer> list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); System.out.println(list); List<Integer> list1 = list.subList(1,3); System.out.println(list1); }

注意： 1.为左闭右开 2.返回的位List类型 3.截取不会产生新的对象（对返回的修改，被截取的也会修改）

8.迭代器 iterator public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); Iterator<Integer> it = list.iterator(); while(it.hasNext()) { System.out.print(it.next()+" "); } }