资讯专栏INFORMATION COLUMN

Java究极打基础之ArrayList篇

DevTalking / 2750人阅读

摘要:将之前第位置的元素置空,返回被删除的元素。平常常用的迭代器方法就是判断当前索引是否等于。最重要的是会更新,此时调用了父类的方法,会使,所以更新了,让后续的检查不会抛异常。

本篇主要介绍ArrayList的用法和源码分析,基于jdk1.8,先从List接口开始。

List

List接口定义了如下方法:

int size();
boolean isEmpty();
boolean contains(Object o);
Iterator iterator();
Object[] toArray();
 T[] toArray(T[] a);
boolean add(E e);
void add(int index, E element);
boolean addAll(Collection c);
boolean addAll(int index, Collection c);
boolean remove(Object o);
E remove(int index);
boolean removeAll(Collection c);
boolean retainAll(Collection c);
void clear();
E get(int index);
E set(int index, E element);
int indexOf(Object o);
int lastIndexOf(Object o);
List subList(int fromIndex, int toIndex);
ListIterator listIterator();
ListIterator listIterator(int index);

乍一看,这么多方法。其实很多方法是同样的功能,方法重载而已。
接下来逐个介绍下List定义的方法。

size 获得List元素的个数

isEmpty 判断List是否为空

contains/containsAll 判断List中是否有该元素,或者有该集合中的所有元素

iterator 获得迭代器对象用于迭代

toArray 将List转换成数组

add/addAll 添加元素至List中,默认直接添加到最后,也可以选择指定的位置,还可以添加整个集合

remove/removeAll 删除元素,可以根据元素删除,也可以根据索引删除,还可以根据集合删除

retainAll 取与目标集合的交集

clear 清空List的所有元素

get 根据索引获得元素

set 覆盖索引处的元素

indexOf 获得该元素的索引

lastIndexOf 获得该元素的索引(从后往前)

subList 获得子List根据start 和 end

listIterator 获得ListIterator对象

方法名言简意赅,基本上都可以从方法名知道方法的目的。
接下来分析List的常用实现类:
ArrayList
LinkedList
Vector

本篇介绍ArrayList

ArrayList类图

在我的理解中,ArrayList是一个封装的数组,提供了一些便利的方法供使用者使用,规避了使用原生数组的风险。

ArrayList的定义
public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable

继承了AbstractList即成为了List,就要实现定义的所有方法。
实现了RandomAccess接口 就是提供了随机访问能力,可以通过下标获得指定元素
实现了Cloneable接口 代表是可克隆的,需要实现clone方法
实现了Serializable接口 代表ArrayList是可序列化的

下面介绍下ArrayList的主要方法

添加元素

boolean add(E e)
先附上源码

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

此方法的执行逻辑:

判断数组长度是否够,不够则扩容。默认扩容1.5倍

elementData[size++] = e;将新元素添加进去。

    private void ensureCapacityInternal(int minCapacity) {
            //是否是空List,是则使用初始容量扩容
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
        }
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;    //增加修改次数
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//扩容1.5倍,采用位运算
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);//最大容量就是Integer的最大值
        // minCapacity is usually close to size, so this is a win:
        //采用Arrays的copyOf进行深拷贝,其中调用的本地方法System.arraycopy,此方法是在内存中操作因此速度会很快。
        elementData = Arrays.copyOf(elementData, newCapacity);
        //至此扩容结束
    }

void add(int index, E element)方法稍有不同

首先检查index是否合法

扩容

将新元素插入指定位置

    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //将index -> (size -1)的元素都往后移动一位 
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

boolean addAll(Collection c)
boolean addAll(int index, Collection c)
这两个方法和上面的add大同小异,第一步都是判断容量,并扩容。
容量大小从1变为c的length,elementData[index] = element;赋值也变为数组拷贝,
直接上代码,秒懂。

    public boolean addAll(Collection c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
    
    public boolean addAll(int index, Collection c) {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }
add总结

无论是哪种add,都需要先执行方法 ensureCapacityInternal(size + 1) 进行容量判断及扩容,确保之后的操作不会产生数组越界。

建议在我们日常工作时,如果大概知道元素的数量,可以在初始化的时候指定大小,这样可以减少扩容的次数,提升性能。

删除元素

E remove(int index)

检查是否索引不正确。

计算移动的元素的个数,数组往前移动。

将之前第size位置的元素置空,返回被删除的元素。

    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

boolean remove(Object o)

区分要删除的元素是null还是非null。

找到该元素的索引,执行上面方法逻辑的2、3步。

    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

这种方法依赖元素的equals方法,循环遍历数组,因为ArrayList是允许null元素的,所以无论是使用if (o.equals(elementData[index])) 还是 if (elementData[index].equals(o)) 均可能产生空指针,所以多带带对null进行处理,逻辑都是一样的。
奇怪的是这个fastRemove方法,原本以为会有些特殊处理,结果发现代码和上面remove(int index)中的一模一样,为什么上面的remove中不调用这个fastRemove呢?难道写两个remove方法的不是同一人?逻辑不影响,只是代码冗余了一点。

boolean removeAll(Collection c)

    public boolean removeAll(Collection c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }

删除存在于目标集合的方法,使用了batchRemove(Collection c, boolean complement)这个方法,这个方法作了封装,在retainAll(Collection c)取并集这个方法也有使用。
retainAll中是这样使用的:

return batchRemove(c, true);

和我们的removeAll只差第二个参数boolean complement,remove是false,retail是true,那到底是什么意思呢?complement的原意的补充,在这里我理解为保留,remove就不保留,retail就保留,接着我们分析batchRemove这个方法。

 
    private boolean batchRemove(Collection c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

定义了 r 和 w两个int,r用于遍历原来的数组,w的意思是新的数组的size。
假如定义2个数组用于举例,
数组1,五个元素 1,2,3,4,5
数组2,五个元素 3,4,6,7,8

数组1调用removeAll(数组2)
此时进入batchRemove,我们来一步一步走看r,w如何变化
此时complement是false,即数组2中没有数组1中第r个元素才满足if条件

r = 0, w = 0, elementData[r] = 1, c.contains(elementData[r]) = false.
执行elementData[w++] = elementData[r],
数组1:1,2,3,4,5

r = 1, w = 1, elementData[r] = 2, c.contains(elementData[r]) = false.
执行elementData[w++] = elementData[r],
数组1:1,2,3,4,5

r = 2, w = 2, elementData[r] = 3, c.contains(elementData[r]) = true.
此时if条件不满足了,w不自增了,代表elementData[r]要不存在与新数组中,要被删除,所以跳过了。

r = 3, w = 2, elementData[r] = 4, c.contains(elementData[r]) = true.
if条件依旧不满足,w不自增,此元素也是要删除。

r = 4, w = 2, elementData[r] = 5, c.contains(elementData[r]) = false.
执行elementData[w++] = elementData[r],
数组1:1,2,5,4,5
此时for循环结束,elementData数组目前是这样的,接着执行finally中的代码,

首先执行

            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }

我们的情况是 r=size,那什么时候r会不等于size呢,jdk中写了注释,就是在if判断时,调用数组2的contains方法,可能会抛空指针等异常。这时数组还没有遍历完,那r肯定是小于size的。
那没判断的那些数据还要不要处理?保守起见jdk还是会将他保存在数组中,因为最终w是作为新的size,所以w加上了没处理过的个数size - r。

接着执行下面一段

            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }

这段代码意图很清晰,w因为是新的size值,所以将w及其之后的都置位null,增加修改次数,
给size赋予新值之后就结束了。

remove总结

删除元素尽量使用指定下标的方法,性能好。

每次删除都会进行数组移动(除非删除最后一位),如果频繁删除元素,请使用LinkedList

boolean contains(Object o)
contains 底层调用的是indexOf方法

     public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

int indexOf(Object o)

    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

就是循环遍历,一个个比对,有则返回对应下标,无则返回-1
对应的lastIndexOf是从最后往前遍历。

    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

E get(int index)

        rangeCheck(index);

        return elementData(index);

先检查index,再返回数组对应元素。

E set(int index, E element)

    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

先检查index,在覆盖index的元素,返回旧元素。

void clear()

        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;

增加修改次数,将所有元素置空,size设置为0,需要注意的是,数组的大小是没有变化的。

int size()
size方法就是直接将size变量直接返回

    public int size() {
        return size;
    }

boolean isEmpty()
判断size是否等于0

    public boolean isEmpty() {
        return size == 0;
    }
迭代器

Iterator iterator()

    public Iterator iterator() {
        return new Itr();
    }

如代码所示,创建了一个Itr对象并返回,接下来看Itr类的定义

    private class Itr implements Iterator {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

首先介绍下三个成员变量

cursor,代表下一个访问元素的在elementData数组中的索引,初始值是0。

lastRet,代表上一个访问元素在elementData数组中的索引,初始值是-1。

expectedModCount,预期的modcount的值,在Itr对象创建的时候从父类ArrayList的modcount获得,用于判断在使用该对象迭代时,有么有对数组进行修改,有则会抛出ConcurrentModificationException。

平常常用的迭代器方法
hasNext()
就是判断当前索引是否等于size。

E next()
首先检查list是否被修改过,expectedModCount是在创建对象时就获得了,如果在之后对list进行了其他修改操作的话,modCount就会增加,就会抛出ConcurrentModificationException。
没有异常就按下表返回坐标,cursor自增,lastRet也自增。

void remove()

首先判断是否能删除,若能则调用父类的remove方法,删除元素,接着会更新cursor和lastRet。
最重要的是会更新expectedModCount,此时调用了父类的remove方法,会使modCount+1,所以更新了 expectedModCount,让后续的检查不会抛异常。

ListIterator listIterator

listIterator和iterator一样,只不过listIterator有更多的方法,相当于iterator的加强版。
定义如下

    private class ListItr extends Itr implements ListIterator {
        ListItr(int index) {
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public E previous() {
            checkForComodification();
            try {
                int i = cursor - 1;
                E previous = get(i);
                lastRet = cursor = i;
                return previous;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor-1;
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                AbstractList.this.set(lastRet, e);
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                AbstractList.this.add(i, e);
                lastRet = -1;
                cursor = i + 1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

没有什么需要注意的地方,基本的方法都从Iterator中继承过来并添加一些方法。

List subList(int fromIndex, int toIndex)

这又是一个内部类

class SubList extends AbstractList {
    private final AbstractList l;
    private final int offset;
    private int size;

    SubList(AbstractList list, int fromIndex, int toIndex) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        if (toIndex > list.size())
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                               ") > toIndex(" + toIndex + ")");
        l = list;
        offset = fromIndex;
        size = toIndex - fromIndex;
        this.modCount = l.modCount;
    }
    。
    。
    。
}

持有了父类的引用,内部的所有方法都是通过父类的这个引用去完成的,
所以需要注意的是,subList不是返回一个新的List,还是原来的引用,所以改变subList的数据,原有的数据也会更改。

终于把基本的方法都介绍完了,从源码的角度分析了所有的方法,感觉对ArrayList知根知底了,用它时肯定会更加得心应手了,看了源码才有原来实现都这么简单啊这样的感觉,不过从中也学习到了大牛规范的代码风格,良好的结构,可读性很高。下篇分析List的另一个实现类,LinkedList。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/67776.html

相关文章

  • 一份送给Java初学者的指南

    摘要:编程思想第版这本书要常读,初学者可以快速概览,中等程序员可以深入看看,老鸟还可以用之回顾的体系。以下视频整理自慕课网工程师路径相关免费课程。 我自己总结的Java学习的系统知识点以及面试问题,目前已经开源,会一直完善下去,欢迎建议和指导欢迎Star: https://github.com/Snailclimb/Java-Guide 笔者建议初学者学习Java的方式:看书+视频+实践(初...

    banana_pi 评论0 收藏0
  • Vim修炼秘籍语法

    摘要:建议先熟悉一遍修炼秘籍之命令篇,本秘籍食用更佳正文核心秘诀功法之究极总结操作次数操作行为操作范围下面,我会将此秘诀亲自传授于你。 前言 少年,我看你骨骼精奇,是万中无一的武学奇才,维护世界和平就靠你了,我这有本秘籍《Vim修炼秘籍》,见与你有缘,就十块卖给你了! 如果你是一名 Vimer,那么恭喜你,你的 Vim 技能马上要升级了 ?! 如果你之前不了解过 Vim ,那么也没关系,本文...

    hikui 评论0 收藏0
  • Android知识点 - 收藏集 - 掘金

    摘要:可以由其焦点事件分发与传递机制掘金如果您对事件分发机制不太了解的,可以参考我的这篇文章安卓事件分发机制。一基础知识分一种相似图片搜索算法的实现掘金本文介绍一种相似图片搜索算法感知哈希算法。 被人忽视的面向对象的六大原则 - 后端 - 掘金1.前言 作为文集的第一篇,我觉得有必要介绍一下大概的写作规划。整个文集将分为三个部分,分别是面向对象六大原则、23种设计模式,以及MVC、MVP、M...

    RobinQu 评论0 收藏0
  • Java爬虫下载全世界国家的国旗图片

    摘要:介绍本篇博客将继续上一篇博客爬虫之使用的模块爬取各国国旗的内容,将用来实现这个爬虫,下载全世界国家的国旗图片。 介绍   本篇博客将继续上一篇博客:Python爬虫之使用Fiddler+Postman+Python的requests模块爬取各国国旗 的内容,将用Java来实现这个爬虫,下载全世界国家的国旗图片。项目不再过多介绍,具体可以参考上一篇博客。  我们将全世界国家的名称放在一个...

    YancyYe 评论0 收藏0
  • 类的加载机制 - 收藏集 - 掘金

    摘要:是现在广泛流行的代从开始学习系列之向提交代码掘金读完本文大概需要分钟。为了进行高效的垃圾回收,虚拟机把堆内存划分成新生代老年代和永久代中无永久代,使用实现三块区域。 React Native 开源项目 - 仿美团客户端 (Android、iOS 双适配) - Android - 掘金推荐 React Native 学习好项目,仿照美团客户端... 极简 GitHub 上手教程 - 工具...

    Gilbertat 评论0 收藏0

发表评论

0条评论

DevTalking

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<