`

java ArrayList源码 下

阅读更多

版本 jdk-7u71-windows-x64

 

JavaSE7 ArrayList源码上:http://flyouwith.iteye.com/blog/2166890  

 

	/**
	 * 从这个列表中移除所有c中包含元素
	 */
	public boolean removeAll(Collection<?> c) {
		return batchRemove(c, false);
	}

	/**
	 * 只保留包含在这个列表中的元素
	 */
	public boolean retainAll(Collection<?> c) {
		return batchRemove(c, true);
	}

	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++)
				//*****注意这种在集合中删除n多元素的逻辑*****
				if (c.contains(elementData[r]) == complement)
					elementData[w++] = elementData[r];
		} finally {
			if (r != size) {
				System.arraycopy(elementData, r, elementData, w, size - r);
				w += size - r;
			}
			if (w != size) {
				// 明确让GC做它的工作
				for (int i = w; i < size; i++)
					elementData[i] = null;
				modCount += size - w;
				size = w;
				modified = true;
			}
		}
		return modified;
	}

    /**
     * 私有,不知道留着干嘛用的
     * 序列化ArrayList的实例
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        int expectedModCount = modCount;
        s.defaultWriteObject();
        s.writeInt(size);

        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

    /**
     * 重建实例
     * 反序列化ArrayList的实例
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;
        s.defaultReadObject();
        s.readInt(); 
        if (size > 0) {
            ensureCapacityInternal(size);
            Object[] a = elementData;
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

    /**
     * 返回一个指向数组索引index处的ListIterator
     */
    public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        
        return new ListItr(index);
    }

    /**
     * 返回一个指向数组起始处的ListIterator
     */
    public ListIterator<E> listIterator() {
        return new ListItr(0);
    }

    /**
     * 返回一个指向数组起始处的iterator
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

    /**
     * 此为内部类,是ArrayList,iterator的具体实现
     */
    private class Itr implements Iterator<E> {
        int cursor;       // 下一个元素的索引,初始0
        int lastRet = -1; // 当前返回元素的索引,初始-1,没有可返回的元素
        //这个元素的作用出来了,在进行迭代的时候
        //如果有改变modCount值的方法执行,那么就会抛出异常
        //看这个内部类的最后一个方法
        int expectedModCount = modCount; 

        //判断下一个元素是否存在,返回false循环退出
        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; //在next()取值时 ,计算下一个索引
            return (E) elementData[lastRet = i];
        }

        //删除lastRet索引处元素
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
            	//上面介绍过的方法
                ArrayList.this.remove(lastRet);
                //上面方法执行后,cursor下一个索引位置前移
                cursor = lastRet;
                //一次next()只允许删除一次元素
                lastRet = -1;
                //因为执行删除modCount值改变。重新赋值
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
        //检核
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

    /**
     * 内部类,是ArrayList,ListIterator的具体实现
     * 注意这里继承了上面的向后迭代器
     * 所以这个迭代器可以向前和向后迭代
     */
    private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            //构造方法,初始化索引位置
            cursor = index;
        }
        // 判断上一个元素是否存在,只要不等于零就一定存在前一个元素
        public boolean hasPrevious() {
            return cursor != 0;
        }
        // 下一个元素索引
        public int nextIndex() {
            return cursor;
        }
        // 上一个元素索引
        public int previousIndex() {
            return cursor - 1;
        }
        //返回上一个元素
        @SuppressWarnings("unchecked")
        public E previous() {
            checkForComodification();//检核
            int i = cursor - 1; //上一个元素索引
            if (i < 0)//检核
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)//检核
                throw new ConcurrentModificationException();
            cursor = i;//这里就有意思了
            return (E) elementData[lastRet = i];
        }
        //替换当前索引处的元素
        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
        //在当前索引处添加元素
        public void add(E e) {
            checkForComodification();

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

 

 

就上面的listIterator写个小程序看看

	public static void main(String[] args) throws IOException{
		//初始化
		ArrayList<String> list = new ArrayList<String>(Arrays.asList("a","b","d","e"));
		//从2位置("d")开始迭代
		ListIterator<String> iter = list.listIterator(2);
		//cursor=2
		iter.add("c");//在d位置插入c,d、e后移一位
		//cursor=3
		if(iter.hasPrevious()){  //向前迭代 
			//cursor=3
			System.err.println(iter.previous());//elementData[2]
			//cursor=2
		}
		if(iter.hasNext()){      //向后迭代 
			//cursor=2
			System.err.println(iter.next());   //elementData[2]
			//cursor=3
		}
		if(iter.hasPrevious()){  //向前迭代
			//cursor=3
			System.err.println(iter.previous());//elementData[2]
			//cursor=2
		}
		if(iter.hasNext()){      //向后迭代 
			//cursor=2
			System.err.println(iter.next());   //elementData[2]
			//cursor=3
		}
		while(iter.hasNext()){
			System.out.println(iter.next());
		}
	}

      输出:

             c
             c     
             c
             c
             d
             e

继续源码

   /**
     * 截取一段数据,生成一个新的List。
     * 如果原数组(列表)太大,可以截取出一段来进行操作。
     * 其实就是对原数组(列表)的某一段的操作,改变哪一个另一个都会改变
     */
    public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, 0, fromIndex, toIndex);
    }

    static void subListRangeCheck(int fromIndex, int toIndex, int size) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        if (toIndex > size)
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                               ") > toIndex(" + toIndex + ")");
    }

    /**
     * 继承了AbstractList 所以具有所有List的功能
     * 但是操作的依然是源数据
     * 下面方法基本都是通过操作索引大小来调用外部类的方法操作源数组
     * 没什么意思。。不介绍了
     */
    private class SubList extends AbstractList<E> implements RandomAccess {
        private final AbstractList<E> parent;
        private final int parentOffset;
        private final int offset;
        int size;

        SubList(AbstractList<E> parent,
                int offset, int fromIndex, int toIndex) {
            this.parent = parent;
            this.parentOffset = fromIndex;
            this.offset = offset + fromIndex;
            this.size = toIndex - fromIndex;
            this.modCount = ArrayList.this.modCount;
        }

        public E set(int index, E e) {
            rangeCheck(index);
            checkForComodification();
            E oldValue = ArrayList.this.elementData(offset + index);
            ArrayList.this.elementData[offset + index] = e;
            return oldValue;
        }

        public E get(int index) {
            rangeCheck(index);
            checkForComodification();
            return ArrayList.this.elementData(offset + index);
        }

        public int size() {
            checkForComodification();
            return this.size;
        }

        public void add(int index, E e) {
            rangeCheckForAdd(index);
            checkForComodification();
            parent.add(parentOffset + index, e);
            this.modCount = parent.modCount;
            this.size++;
        }

        public E remove(int index) {
            rangeCheck(index);
            checkForComodification();
            E result = parent.remove(parentOffset + index);
            this.modCount = parent.modCount;
            this.size--;
            return result;
        }

        protected void removeRange(int fromIndex, int toIndex) {
            checkForComodification();
            parent.removeRange(parentOffset + fromIndex,
                               parentOffset + toIndex);
            this.modCount = parent.modCount;
            this.size -= toIndex - fromIndex;
        }

        public boolean addAll(Collection<? extends E> c) {
            return addAll(this.size, c);
        }

        public boolean addAll(int index, Collection<? extends E> c) {
            rangeCheckForAdd(index);
            int cSize = c.size();
            if (cSize==0)
                return false;

            checkForComodification();
            parent.addAll(parentOffset + index, c);
            this.modCount = parent.modCount;
            this.size += cSize;
            return true;
        }

        public Iterator<E> iterator() {
            return listIterator();
        }

        public ListIterator<E> listIterator(final int index) {
            checkForComodification();
            rangeCheckForAdd(index);
            final int offset = this.offset;

            return new ListIterator<E>() {
                int cursor = index;
                int lastRet = -1;
                int expectedModCount = ArrayList.this.modCount;

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

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

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

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

                public int nextIndex() {
                    return cursor;
                }

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

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

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

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

                    try {
                        ArrayList.this.set(offset + lastRet, e);
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

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

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

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

        public List<E> subList(int fromIndex, int toIndex) {
            subListRangeCheck(fromIndex, toIndex, size);
            return new SubList(this, offset, fromIndex, toIndex);
        }

        private void rangeCheck(int index) {
            if (index < 0 || index >= this.size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

        private void rangeCheckForAdd(int index) {
            if (index < 0 || index > this.size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

        private String outOfBoundsMsg(int index) {
            return "Index: "+index+", Size: "+this.size;
        }

        private void checkForComodification() {
            if (ArrayList.this.modCount != this.modCount)
                throw new ConcurrentModificationException();
        }
    }

 

 

补充一下 ArrayList 实现了一个RandomAccess标记接口

        如果集合类是RandomAccess的实现,则尽量用for(int i = 0; i < size; i++) 来遍历而不要用Iterator迭代器来遍历,在效率上要差一些。反过来,如果ListSequence List,则最好用迭代器来进行迭代。

        在对List特别是Huge size的List的遍历算法中,要尽量来判断是属于RandomAccess还是Sequence List,因为适合RandomAccess List的遍历算法,用在Sequence List上就差别很大。

 

 

 

1
2
分享到:
评论
2 楼 shuizhaosi888 2014-12-30  
string2020 写道
RandomAccess 是干啥的

你可以参考一下http://jianchen.iteye.com/blog/291047
谈一下我自己的看法:
因为ArrayList底层实现就是一个数组,如果用Iterator进行迭代的话,我们根据源码也能看到,它附加了很多操作(比如各种数组越界的检核)然后才通过数组下标返回数据,如果用for循环就直接返回下标数据了,这样的话我就对该容器添加一个标记RandomAccess来告诉使用人员,这个容器适合用for循环进行读取数据。
而LinkedList的数据结构是双向链表,跟ArrayList完全不是一回事。他每一个元素并没有记录下标,而是记录上一个和下一个元素,所以用Iterator会比较快。
1 楼 string2020 2014-12-29  
RandomAccess 是干啥的

相关推荐

    ArrayList源码分析

    ArrayList不是线程安全的,这意味着在多线程环境下,对ArrayList的操作可能导致数据不一致。如果需要线程安全的列表,应使用`CopyOnWriteArrayList`。 7. **ArrayList与LinkedList的比较** - ArrayList更适合于...

    ArrayList源码分析(含jdk1.8).pdf

    通过以上对ArrayList源码的分析,可以总结出如下关键知识点: 1. ArrayList的实现基于动态数组,可以动态地进行容量的调整; 2. ArrayList具有默认初始化容量10,以及无参构造时延迟初始化的特性; 3. ArrayList...

    ArrayList源码.zip

    ArrayList是Java编程语言中最常用的集合...总之,这个“ArrayList源码.zip”文件是Java程序员学习和优化代码的宝贵资源,它揭示了ArrayList内部的工作机制,帮助我们提升编程技巧,更好地理解和利用这个强大的集合类。

    Java中ArrayList类的源码解析

    Java中ArrayList类的源码解析 ArrayList是Java中最常用的集合类之一,它实现了List接口,继承自AbstractList抽象类。在ArrayList中,我们可以看到它的源码实现了Iterable接口、List接口和Collection接口。下面我们...

    JDK8的ArrayList源码文件

    JDK8的ArrayList源码文件

    ArrayList源码Jdk1.8

    ### ArrayList源码解析(JDK 1.8) #### 概述 `ArrayList`是Java集合框架中的一个核心组件,它提供了动态数组的功能。与固定大小的数组不同,`ArrayList`可以随着元素的增加而自动扩展其容量。在JDK 1.8中,`...

    查看Java类库源码

    2. **验证源码可见性**:返回IDE的项目视图,尝试打开某个Java类,如`String`或`ArrayList`。如果一切设置正确,IDE应能成功加载并显示对应类的源代码。 #### 扩展知识点 - **JRE与JDK的区别**:JRE(Java Runtime...

    Java源码大全

    Java源码大全是一个集合了各种Java编程基础知识和经典算法的资源包,对于Java初学者以及有一定经验的开发者来说,都是一个宝贵的参考资料。这个压缩包涵盖了Java语言的不同方面,旨在帮助学习者深入理解Java编程的...

    java源码文档src

    `java.util`包下的`List`、`Set`、`Map`等接口以及它们的实现类,如`ArrayList`、`HashMap`等,构成了Java集合框架。源码解析可以帮助我们理解这些数据结构的内部实现,优化数据存储和操作。 8. **网络编程** `...

    ArrayList扩容机制源码解析.md

    本资源根据个人学习和总结,主要介绍Java中ArrayList扩容机制源码的解析,主要包含文字和代码等内容,以源码的形式进行分析,详细介绍了ArrayList扩容机制的整个流程,特此将该资源分享

    Java SE 源码 Java SE 源码

    7. **集合框架**:Java集合框架包括数组、列表、队列、映射等数据结构,如`ArrayList`、`HashMap`等。源码揭示了这些数据结构的实现细节,对于优化和定制自己的数据结构非常有用。 8. **IO/NIO**:`java.io`和`java...

    Thinking in Java 4 源码 导入IDEA可直接运行

    其次,集合框架部分的源码将展示ArrayList、LinkedList、HashSet、HashMap等各种容器的使用方法,以及泛型、迭代器和比较器的概念。这部分代码可以帮助你理解Java集合的强大功能和灵活性。 再者,多线程编程的源码...

    Java 编程 源码 处理

    4. **集合框架**:Java集合框架包括List、Set、Map等接口及其实现类,如ArrayList、HashSet、HashMap等。源码分析能帮助理解它们的工作机制和性能特点,选择合适的数据结构存储和操作数据。 5. **多线程编程**:...

    Java集合框架ArrayList源码分析(一)

    《深入剖析Java集合框架ArrayList源码》 Java集合框架中的ArrayList是开发者常用的数据结构,它是一种基于动态数组实现的列表。ArrayList的特点在于它的内部结构、性能优化以及在并发环境下的处理方式。本文将深入...

    Java编程中ArrayList源码分析

    Java编程中ArrayList源码分析 Java编程中ArrayList源码分析是Java编程中一个重要的知识点,对于Java开发者来说,了解ArrayList的源码可以帮助他们更好地理解Java集合框架的实现机制,从而提高自己的编程水平。 ...

    Java 集合框架(2-9)-Collection - ArrayList 源码解析.pdf

    《Java集合框架(2-9)-Collection - ArrayList 源码解析》 ArrayList是Java集合框架中的一个重要组件,它属于List接口的实现类,提供了一种动态数组的逻辑视图。ArrayList以高效、灵活的方式存储和操作对象序列,是...

    Java大全源码包

    4. **集合框架**:Java集合框架是用于存储和操作对象的工具,包括List(如ArrayList、LinkedList)、Set(如HashSet、TreeSet)和Map(如HashMap、TreeMap)。源码可能包含各种数据结构的实现和操作,比如查找、排序...

    第二章 ArrayList源码解析1

    第二章 ArrayList源码解析 ArrayList是Java集合框架中的一种动态数组,它继承自AbstractList,并实现了List接口。ArrayList主要用于存储可变大小的对象列表,它的核心是通过一个Object类型的数组elementData来实现...

    java贪吃蛇源码

    此外,还会使用到Java集合框架中的数组和ArrayList来存储游戏元素。 2. **图形用户界面(GUI)**:游戏的界面通常是使用Java的Swing或JavaFX库来创建的。Swing提供了诸如JFrame、JPanel、JButton等组件,用于构建...

Global site tag (gtag.js) - Google Analytics