摘要:类属性是基于数组实现的,其属性有其中常量表示数组的基础容量。表示数组表当前长度数组元素个数,作索引时,表示数组的最后一个元素,而表示新添加的项可以被放置的位置。
PS:如果觉得文章有什么地方写错了,哪里写得不好,或者有什么建议,欢迎指点。
ArrayList 类提供了 List ADT 的可增长数组的实现。
一、自定义实现的 ArrayList 类 MyArrayList源码链接:戳此进GitHub查看
MyArrayList 泛型类实现了 Iterable 接口从而可以拥有增强 for 循环(for each 循环)。
public class MyArrayList1. 类属性implements Iterable { @Override public Iterator iterator() { return new ArrayListIterator(); } }
MyArrayList 是基于数组实现的,其属性有:
private static final int DEFAULT_CAPACITY = 10; private int theSize; private AnyType[] theArrays;
其中常量 DEFAULT_CAPACITY 表示数组的基础容量。theSize 表示数组表当前长度(数组元素个数),作索引时,A[theSize - 1] 表示数组的最后一个元素,而 A[theSize] 表示新添加的项可以被放置的位置。泛型数组 theArrays 为 MyArrayList 类的数组实现,即对 MyArrayList 对象的操作实际为对数组 theArrays 的操作。
2. 构造方法当实例化 MyArrayList 对象时,调用构造方法:
public MyArrayList(){ theArrays = (AnyType[])new Object[DEFAULT_CAPACITY]; doClear(); }
在构造方法中先实例化泛型数组 theArrays。由于泛型数组的创建是非法的,所以我们需要创建一个泛型类型限界的数组;即创建一个 Object[] 类型的数组,然后向泛型类型数组 AnyType[] 强制转型。
然后调用 doClear() 方法对数组表进行清空、初始化的操作,此方法仅类内部可调用:
private void doClear(){ theSize = 0; expandCapacity(DEFAULT_CAPACITY); }
此处先设置 theSize = 0,然后调用 expandCapacity() 方法改变数组容量为基础容量。(在 expandCapacity() 方法的实现中,若扩充的容量(参数)小于 theSize 时表示非法的操作。)
3. 成员方法数组扩容方法 expandCapacity() :
public void expandCapacity(int newCapacity){ if (newCapacity < theSize){ return; } // 数组容量的扩充: AnyType[] newArrays = (AnyType[])new Object[newCapacity]; // 利用 System.arraycopy() 方法拷贝数组 System.arraycopy(theArrays,0,newArrays,0,theSize); theArrays = newArrays; }
System.arraycopy() 方法:get 方法的实现
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
/** * 根据下标得到数组元素的值 */ public AnyType get(int idx){ if (idx <0 || idx >= theSize){ throw new ArrayIndexOutOfBoundsException(); } return theArrays[idx]; }set 方法的实现
/** * 根据下标设置数组元素的值 * 返回该下标元素的原值 */ public AnyType set(int idx,AnyType newVal){ if (idx <0 || idx >= theSize){ throw new ArrayIndexOutOfBoundsException(); } AnyType oldVal = theArrays[idx]; theArrays[idx] = newVal; return oldVal; }add 方法的实现
/** * 根据下标向数组插入新元素 */ public boolean add(int idx,AnyType newVal){ // 当 idx=theSize 时,在 A[theSize] 位置处插入元素 if (idx < 0 || idx > theSize){ throw new ArrayIndexOutOfBoundsException(); } // 数组满时扩充容量 if (theArrays.length == theSize){ expandCapacity(theSize*2 + 1); } // 数组元素后移 for (int i=theSize;i>idx;i--){ theArrays[i] = theArrays[i-1]; } theArrays[idx] = newVal; theSize++; return true; } /** * 在数组末尾插入新元素 */ public boolean add(AnyType newVal){ add(theSize,newVal); return true; }remove 方法的实现
/** * 根据下标删除元素 * 返回被删除的元素 */ public AnyType remove(int idx){ if (idx < 0 || idx >= theSize){ throw new ArrayIndexOutOfBoundsException(); } // 数组元素前移 AnyType removedElem = theArrays[idx]; for (int i = idx; i < theSize-1; i++) { theArrays[i] = theArrays[i+1]; } theSize--; return removedElem; }4. Iterator 迭代器 关于 Iterator 接口
实现 Iterable 接口的集合必须提供 iterator 方法,该方法返回一个 Iterator (java.util.Iterator)类型的对象:
public interface Iterator{ boolean hasNext(); AnyType next(); void remove(); }
即每个集合均可通过 iterator 方法创建并返回给客户一个实现 Iterator 接口的对象,并把 当前位置 的概念在对象内部存储下来。根据当前位置项每次调用 hasNext() 来判断是否存在下一项,调用 next() 来给出下一项,而 remove() 方法则删除由 next() 方法最新返回的项(即当调用一次 remove() 后,直到对 next() 再调用一次后才能调用 remove() 方法)。例:
public staticvoid print(Collection coll){ Iterator itr = coll.iterator(); while(itr.hasNext()){ AnyType item = itr.next(); System.out.println(item); // itr.remove(); } }
Java 中的增强 for 循环(for each)底层即是通过这种迭代器模式来实现的,当使用增强 for 循环时也就是间接的使用 Iterator。
MyArrayList 中 Iterator 的实现import java.util.Iterator; import java.util.NoSuchElementException; public class MyArrayListimplements Iterable { ...... @Override public Iterator iterator() { return new ArrayListIterator(); } private class ArrayListIterator implements Iterator { // 初始时当前位置为 0 private int current = 0; @Override public boolean hasNext() { return current < theSize; } @Override public AnyType next() { if (!hasNext()){ throw new NoSuchElementException(); } return theArrays[current++]; } @Override public void remove() { /* 因为 remove() 方法有相同的,MyArrayList.this 表示外部类当前对象的一个引用 */ MyArrayList.this.remove(--current); } } }
iterator() 方法直接返回 ArrayListIterator 类的一个实例,该类是一个实现 Iterator 接口的类。ArrayListIterator 存储当前位置的概念,并提供 hasNext()、next()、remove() 的实现。当前位置 表示要被查看的下一元素(的数组下标),因此初始化当前位置为 0。
其中,泛型类 ArrayListIterator 是一个 内部类,使用内部类的目的及优点:
next() 方法中使用当前位置作为下标访问数组元素然后将当前位置向后推进,而迭代器中是没有数组的,使用内部类可以访问外部类的域 theArrays;
theArrays 是 MyArrayList 的私有域,使用内部类访问可以很好的满足面向对象编程的基本原则,即让数据尽可能地隐藏;
满足迭代器 Iterator 的特性,即当集合(外部类)不存在的时候,迭代器(内部类)也是不存在的。
二、MyArrayList 类各方法的算法分析因为 ArrayList 是基于数组实现的,所以和数组相似:ArrayList 的 get() 和 set() 方法花费常数时间 O(1);而使用 add() 和 remove() 方法时为了保持内存数据的连续性,需要做大量的数据搬移工作,其花费的时间代价为 O(n)。
欢迎您的点赞、收藏和评论!
(完)
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/74022.html
摘要:自定义类的概述自定义类的概述代码映射成现实事物的过程就是定义类的过程。自定义类的格式自定义类的格式使用类的形式对现实中的事物进行描述。 01引用数据类型_类 * A: 数据类型 * a: java中的数据类型分为:基本类型和引用类型 * B: 引用类型的分类 * a: Java为我们提供好的类,比如说:Scanner,Random等。 * b: 我们自己创建的类...
摘要:加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行操作即重建内部数据结构,从而哈希表将具有大约两倍的桶数。成员变量每个对由封装,存在了对象数组中。 虽是读书笔记,但是如转载请注明出处 http://segmentfault.com/blog/exploring/ .. 拒绝伸手复制党 LinkedLis...
摘要:在最近写程序题的时候,需要存储一个为为的后来需要根据的长度对从小到大进行排序。用代替,然后中的元素为配对类,变相实现了一个键对应一个值的集合,并且能够排序。 在最近写程序题的时候,需要存储一个key为char,value为string的map,后来需要根据string的长度对map从小到大进行排序。 showImg(https://segmentfault.com/img/bVbiZz...
摘要:阅读本文约分钟处理战舰游戏前言你听说过有些程序员上班总是迟到,而下班又很准时吗因为他们使用了。复现上一章我们的程序运行起来了,但是还存在一些低级或者严重的,即当用户击中一个坐标后可以重复击杀来快速接受游戏。 阅读本文约 6分钟 ArrayList处理战舰游戏BUG 前言 你听说过有些程序员上班总是迟到,而下班又很准时吗?因为他们使用了Java API。核心Java函数库是由一堆等着被...
摘要:集合代表一个元素有序可重复的集合,集合中每个元素都有其对应的顺序索引。集合默认按元素的添加顺序设置元素的索引。 List集合代表一个元素有序、可重复的集合,集合中每个元素都有其对应的顺序索引。List集合可以通过索引来访问指定位置的集合元素。List集合默认按元素的添加顺序设置元素的索引。 Java8改进的List接口和ListIterator接口 普通方法 List是有序集合,因此L...
阅读 1164·2021-11-22 15:24
阅读 4440·2021-09-23 11:51
阅读 2302·2021-09-08 09:36
阅读 3514·2019-08-30 15:43
阅读 1295·2019-08-30 13:01
阅读 1115·2019-08-30 12:48
阅读 530·2019-08-29 12:52
阅读 3366·2019-08-29 12:41