`
greemranqq
  • 浏览: 975645 次
  • 性别: Icon_minigender_1
  • 来自: 重庆
社区版块
存档分类
最新评论

JAVA 深入集合-- ArrayList

阅读更多

一、介绍

   ArrayList 简单的说就是一个存放元素的集合,也是一个数组,只是提供了大量方便我们操作的方法, 比数组的优势就是不用我们手动维护了,相信大家用得比较多了,还是看代码吧!

 

二、源码介绍

    2.1 类:

  

  public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

 

 

    

    可以看出,继承了AbstractList<E> 实现了 List<E> 和 RandomAccess,这里List 只一个接口,定义了该集合的一些方法,

AbstractList 是实现了List 接口的抽象类,继承他 只是为了减少我们常用的一些操作,这里和hashMap 的设计一样,具体请看hashMap 的介绍。

    RandomAccess 这东西作为一个接口定义,允许一般的算法更改其行为,- -比较抽象,暂时不管,后期再谈!

 

 

  2.2 构造
    private transient Object[] elementData;

    public ArrayList(int initialCapacity) {
	super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
	this.elementData = new Object[initialCapacity];
    }

    public ArrayList() {
	this(10);
    }
    
     // 从上面看出,当我们new一个 ArrayList 的时候,实际是创建了一个elementData 的数组,当     // 然默认长度为10,很简单对吧!
    // 这里集合扩展,就是数组复制,也没啥奇特的
    public ArrayList(Collection<? extends E> c) {
	elementData = c.toArray();
	size = elementData.length;
	if (elementData.getClass() != Object[].class)
	    elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

 

 

 

 2.3 我们切入点从常用的 add set 方法开始看:
       add:这里进行的重写

       // 属性获得获得元素的个数      
       private int size;
       public boolean add(E e) {
        // size 默认是0,其实这里仅仅是进行一个是否扩容的判断
	ensureCapacity(size + 1);  // Increments modCount!!
        // 可以看出 这就仅仅是给数组放值
	elementData[size++] = e;
	return true;
      }

	public void ensureCapacity(int minCapacity) {
        // 依然是控制集合修改次数,用于迭代的时候控制异常
	modCount++;
	// 数组长度
	int oldCapacity = elementData.length;
        // 如果当前容量大于的数组长度
	if (minCapacity > oldCapacity) {
	    Object oldData[] = elementData;
            // 进行扩容后的长度,这里有点意思,要扩容成奇数,不知道为啥
	    int newCapacity = (oldCapacity * 3)/2 + 1;
            // 这里为了addAll的时候,可能一次性添加多了
    	    if (newCapacity < minCapacity)
		newCapacity = minCapacity;
            // 这里就是扩容啦,也看看源码吧,虽然在工具类Arrays里面的
            elementData = Arrays.copyOf(elementData, newCapacity);
	}
    }
           
    // 扩容源码
       
	public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }   
	// 这里用于返回U类型的T 数组
	public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
	// 这里进行了地址判断,判断参数是否是Object类型,否则就从新 new 一个newType 类型的数        // 组
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
	// 这是JAVA数组扩容最快的方法了,参数解释 看看API 就行了
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }  
    

 

2.3.2 继续看方法:add(index, element)
        // 这里我们知道是方法是将元素element 加入到集合的指定位置index
 
	public void add(int index, E element) {
        // 先进行判断,位置是否超出了界限,当然这里判断只是判断size,而非数组界限
	if (index > size || index < 0)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);
	// 这里就是刚才的了
	ensureCapacity(size+1);  // Increments modCount!!
	// 这里看出还是数组的复制,只是将当前数组elementData 的index + 1位置 向后移动了一位,就完成了插入
	System.arraycopy(elementData, index, elementData, index + 1,
			 size - index);
	elementData[index] = element;
	size++;
    }

 

 2.3.3 方法addAll(Collection<? extends E> c)
	
	public boolean addAll(Collection<? extends E> c) {
	Object[] a = c.toArray();
        int numNew = a.length;
	// 数组扩容
	ensureCapacity(size + numNew);  // Increments modCount
	// 数组复制
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
	return numNew != 0;
    }

 

 2.4 get方法
	public E get(int index) {
	// 仅仅判断数组是否越界,抛出自己定义的错误信息
	RangeCheck(index);
	// 直接访问的数组下标,因此访问元素很快
	return (E) elementData[index];
    }
	private void RangeCheck(int index) {
	if (index >= size)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);
    }
   

  

 2.5  方法:remove(int index) 

	public E remove(int index) {
	// 同上
	RangeCheck(index);
	// 看来在迭代的时候不允许删除的
	modCount++;
	E oldValue = (E) elementData[index];
	// 获取删除的位置
	int numMoved = size - index - 1;
	if (numMoved > 0)
	    // 当前数组在numMoved 位置,向左复制,
	    System.arraycopy(elementData, index+1, elementData, index,
			     numMoved);
	// 将数组最后一个元素设为null,我们发现虽然元素删除了,但是数组的长度并没减少,还占         // 空间
	elementData[--size] = null; // Let gc do its work

	return oldValue;
    }
	// 这里要提到另一个方法,在remove(Object o)中使用了,其实内容和上面一样,只是JDK 人        // 员忘记掉了
	// 看到这些我总会相信,大神也会失误的,也是不完美的~。~
 	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; // Let gc do its work
    }

 

 

 

    2.6	方法:indexOf(Object o) 
	 public int indexOf(Object o) {
	if (o == null) {
	    // 这里小技巧发现,对null 的判断总是要特殊一些
	    for (int i = 0; i < size; i++)
		if (elementData[i]==null)
		    return i;
	} else {
	    // 总的来说就是便利数组啦,有就返回,没有返回-1
	    for (int i = 0; i < size; i++)
		if (o.equals(elementData[i]))
		    return i;
	}
	// 同时contains方法额也是调用的这个
	return -1;
    }

 

2.7 方法:toArray,带参数和不带参数差不多
	public <T> T[] toArray(T[] a) {
	// 带参数情况就是,如果a 数组length 比较大,那么剩余的都是null,而不带参数 仅仅是将
        // list元素放进数组返回
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
	
	System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

 

    2.8 方法:removeRange 
	 // 这个方法可以一次移除 指定两个位置的所有元素,但是不知道为什么是protected ,调用         // 不了
	 // 当然实现这个功能 我们可以用 list.sublist(int b,int e).clear() 完成此功能
	 protected void removeRange(int fromIndex, int toIndex) {
	// 内容和remove 比较类似
	modCount++;
	int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

	// Let gc do its work
	int newSize = size - (toIndex-fromIndex);
	while (size != newSize)
	    elementData[--size] = null;
    }

 

   
    2.9 方法:trimToSize 
	// 上面讲到我们删除元素的时候,数组还是占着位置,这个方法就是将那些没有元素的位置删        //  除掉
	public void trimToSize() {
	modCount++;
	int oldCapacity = elementData.length;
	if (size < oldCapacity) {
            elementData = Arrays.copyOf(elementData, size);
	}
    }

 

 

 2.9.1 方法:subList(fromIndex, toIndex)
	// 这里实际上是在AbstractList 里面了,arrayList 没进行重写
	public List<E> subList(int fromIndex, int toIndex) {
	// 这两个内部类...其实对象都访问到SubList 里面去了
        return (this instanceof RandomAccess ?
                new RandomAccessSubList<E>(this, fromIndex, toIndex) :
                new SubList<E>(this, fromIndex, toIndex));
    }  
    // 先来看看 内部类吧
         
	class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
	// 从构造看出,其实操作了 SubList<E> 的构造,super() 继续往下看
    	RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
       	 super(list, fromIndex, toIndex);
    	}

    	public List<E> subList(int fromIndex, int toIndex) {
        return new RandomAccessSubList<E>(this, fromIndex, toIndex);
    	}
   	 }
	// 这个内部类 就是我们需要返回RandomAccessSubList<E>  的父类,看看做了什么操作
	class SubList<E> extends AbstractList<E> {
   	 private AbstractList<E> l;
   	 private int offset;
    	 private int size;
    	 private int expectedModCount;
	// 构造线对位置进行了判断
    	SubList(AbstractList<E> 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;
        expectedModCount = l.modCount;
    }
   	// ...
    }
    // 这里可以看出其实我们调用subList 方法的同时,返回的其实是一个RandomAccessSubList 对象,

 

   // 但是该对象继承了SubList<E> ,而SubList<E>  内容是原来list 的的一个引用。

   // 既然是引用,那么为什么还要单独设计一个类呢,为什么不直接引用,操作数组呢?

  

// 这个是SubList<E> 内部的方法,看看区别
   public E set(int index, E element) {
	// 检查参数大小
        rangeCheck(index);
        checkForComodification();
        return l.set(index+offset, element);
    }

   public E get(int index) {
      	rangeCheck(index);
       	checkForComodification();
	// 这里看到 我们获得元素的位置 已经发生了变化
        return l.get(index+offset);
    }

   public int size() {
        checkForComodification();
        return size;
    }
    // 大家都调用了这个方法,也就是说当我们操作这个sublist 返回的类的时候
    // 都是不允许影响集合的操作
    // 包括原list 也不允许删除 等操作
    private void checkForComodification() {
        if (l.modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }

    // 下面继续看内部类的通用方法:
    // 下面所有的方法我们都可以看出一点
    // 所有元素的位置 都跟index 和 offset 相关,也就是和我们定义的位置有关,实质内容没变
    public void add(int index, E element) {
        if (index<0 || index>size)
            throw new IndexOutOfBoundsException();
        checkForComodification();
        l.add(index+offset, element);
        expectedModCount = l.modCount;
        size++;
        modCount++;
    }

    public E remove(int index) {
        rangeCheck(index);
        checkForComodification();
        E result = l.remove(index+offset);
        expectedModCount = l.modCount;
        size--;
        modCount++;
        return result;
    }

    protected void removeRange(int fromIndex, int toIndex) {
        checkForComodification();
        l.removeRange(fromIndex+offset, toIndex+offset);
        expectedModCount = l.modCount;
        size -= (toIndex-fromIndex);
        modCount++;
    }
     // 上面的元素操作,参考前面的介绍,我们来模拟一下这个内部类干了什么。

 

    // 1.假设我们有个ArrayList m,存放了元素  1,2,3,4,5,6,7,8,9

    // 2.假设我们要得到1,2,3 的元素,从而调用sublist(0,3) 方法。

    // 3.这个时候内部类给我们定义变量 private AbstractList<E> l ,size 等属性

    // 4.为属性赋值l = list; offset = fromIndex = 0; size = toIndex - fromIndex = 3;

    // 5.我们可以看出,现在 我们操作的实际是m的引用l,但是操作的范围只能是 0,3 这个区间。

    // 6.也就是说,大家共用一块区域,但是sublist 的结果,只能从大的区域m,划分出一片小的区域

    // 7.但是如果操作任何一个变量,都会引起大家的变化,我们做个尝试

   

public static void main(String[] args) {
		ArrayList<Object> m = new ArrayList<Object>();
		System.out.println(new Test() instanceof RandomAccess);
		for(int i =1;i<10;i++){
			// 放9个元素
			m.add(i);
		}
		// 取3个元素1,2,3
		List<Object> l = m.subList(0, 3);
		// 这里已经拿到 1,2,3 了
		System.out.println(l);
		// 这里是没变化的
		System.out.println(m); 
		// 如果l 添加一个值,我们发现m 的数据已经变了,多了一个元素10
	        l.add(10);
		System.out.println(m); 
		System.out.println(l); 
		// 如果操作m,那么打印l,就会抛ConcurrentModificationException
		m.add(11);
		System.out.println(m); 
		// 因为l添加时,先检查 checkForComodification() 变量再自增,
		// 而m 元素增加了 ,modCount 数量也加1,打印不报错
		// 而m添加元素了,modCount 增加,而l 元素没有增加,期望的expectedModCount                   // 没变
		// 价差不通过 就报错了
		System.out.println(l); 
		// 所以使用的时候要小心啦,当然你可以这样 new ArrayList(l) 创建新的
		System.exit(0);
	}  
 

 

关于AbstractList 里面提供的源码,后面再介绍吧,大概的都差不多,只是iterator 迭代 那里不同

关于私有方法writeObject 和 readObject 这是为io 准备的,传输的时候会通过反射查找调用,这里暂时不讲

 

 

三、小结:

    1.ArrayList 是一个动态数组,动态通过数组的底层复制进行,和Vector差不多,它不是线程安全的

    2.为了减小计算,可以手动指定空间或者扩容ensureCapacity ,同时也可以trimToSize 去掉不必要的空间

    3.存放元素和获取元素 都是通过数组依次存放,通过下标存放,因此是很快的

 

分享到:
评论

相关推荐

    java基础 集合-21-对象的一对多与多对多

    在本课程"java基础 集合-21-对象的一对多与多对多"中,我们将深入探讨如何在Java中实现对象之间的关系,特别是一对一、一对多和多对多的关系。 1. **对象的一对一关系**: 在一对一关系中,一个类的对象只对应另一...

    面试真题包含spring-java-集合-框架-并发-spring-运维-数据库等多领域45卷合集.rar

    集合框架的"集合框架.pdf"将涵盖ArrayList、LinkedList、HashMap、HashSet、TreeMap等基础数据结构,以及泛型、迭代器、比较器等概念。求职者应能熟练运用这些集合,并了解其性能特点。 对于服务器端技术,"Tomcat...

    java基础 集合-22-迭代器设计模式

    本文将深入探讨Java中的迭代器模式及其在集合框架中的应用。 迭代器模式是一种行为设计模式,它提供了一种方法来顺序访问聚合对象的元素,而不暴露其底层表示。在Java中,迭代器模式广泛用于遍历集合类,如...

    关于java基础集合-定义及练习资料

    本资料主要关注Java集合的基础定义以及相关的练习,帮助开发者深入理解和掌握这些概念。 首先,我们来详细讲解Java集合的定义。在Java中,集合是一种容器,可以用来存储一组对象。集合框架包括了接口(如List、Set...

    Java-Interview-超全集合github上评分最高的jiva面试题

    "Java-Interview-超全集合github上评分最高的jiva面试题"就是一个这样的宝藏,它涵盖了Java编程语言、Git版本控制工具以及面试策略等多个方面的知识点。以下是这些内容的详细解析: 1. **Java基础** - **数据类型...

    【IT十八掌徐培成】Java基础第10天-03.List-集合框架-ArrayList.zip

    本课程“【IT十八掌徐培成】Java基础第10天-03.List-集合框架-ArrayList”深入讲解了Java中的ArrayList类,这是集合框架中的一个重要组成部分,特别适用于对元素有序且可变大小的需求。 ArrayList是Java.util包下的...

    Java-Java集合体系-List-Set

    Java集合体系是Java编程中非常核心的部分,涵盖了用于存储和操作数据的各种数据结构。在Java中,集合主要分为三大接口:List、...在面试中,深入理解集合的底层原理和操作性能,能展现出扎实的Java基础和问题解决能力。

    Java基础----集合类汇总

    本文将深入探讨Java集合类的汇总,包括List、Set和Map这三大核心接口及其实现类。 首先,让我们从List接口开始。List是一种有序的集合,允许有重复元素,并且支持通过索引来访问元素。ArrayList和LinkedList是List...

    【死磕Java集合】-集合源码分析.pdf

    在Java集合框架中,LinkedList、ArrayList、HashMap、TreeMap等都是非常常用的数据结构。本文将对Java集合框架的源码进行分析,深入探讨其实现原理和机制。 一、LinkedList源码分析 LinkedList是一种以双向链表...

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

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

    java基础教程----精华版

    - `java.util`包中的ArrayList, LinkedList, HashMap等是常用的集合类,提供了存储和操作对象的方法。 - 集合框架包括List, Set, Queue, Map等接口,以及它们的实现类。 7. **多线程**: - Java内置对多线程的...

    Java基础-ArrayList方法全解(上).pdf

    ArrayList是Java集合框架中常用的动态数组,它允许我们在运行时添加、删除和访问元素。在Java中,ArrayList实现了List接口,因此它支持有序的元素序列,并且允许有重复元素。本文将深入解析ArrayList的主要方法,...

    精通java集合框架--List,Set..

    本文将深入探讨Java集合框架的核心概念,包括`List`、`Set`、`Map`以及它们之间的区别和联系。 #### Java集合框架简介 Java集合框架是Java平台的一部分,它由一系列接口组成,这些接口描述了不同类型的容器,比如...

    中信java培训资料------第一部分

    文本文件【7月3日.txt】至【7月25日.txt】可能是每日学习要点或作业的记录,随着时间推移,内容可能涉及更多高级主题,如集合框架(ArrayList、LinkedList、HashMap等)、IO流、线程并发、网络编程、数据库连接以及...

    java提高篇(二一)-----ArrayList.pdf

    《Java提高篇(二一)-----ArrayList.pdf》这篇文章主要深入讲解了Java编程语言中的ArrayList类的内部工作机制以及如何高效地使用这个重要的数据结构。ArrayList是基于数组实现的动态数组,用于存储顺序的集合,并且...

    arrayliSt---listDemo

    这个"arrayliSt---listDemo"示例可能包含了以上提到的一些或所有操作,通过运行和分析代码,可以更深入地理解和掌握ArrayList的用法。在实际开发中,熟练运用ArrayList可以极大地提高代码的效率和可读性。

    java-util-iterator.pdf java-util-iterator.pdf

    根据提供的文件信息,本文将深入探讨Java中的`java.util.Iterator`接口及其在集合类中的应用。我们将从以下几个方面进行详细解析: ### 一、集合类的根接口:Collection `Collection`接口是Java集合框架的基础,它...

    CoreJava串讲---超好!

    6. **集合框架**:Java集合框架包括List、Set、Queue和Map四大接口,以及ArrayList、LinkedList、HashSet、HashMap等实现类。熟练运用集合框架可以有效地组织和操作数据。 7. **IO流**:Java的IO流提供了读写文件、...

Global site tag (gtag.js) - Google Analytics