• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

List集合和ArrayList集合源码

互联网 diligentman 2小时前 1次浏览

文章目录

    • 1、List集合
      • 1.1、List简介
      • 1.2、其主要派生类
    • 2、ArrayList集合源码
      • 2.1、ArrayList的继承关系
      • 2.2、相关属性
      • 2.3、构造方法
      • 2.4、相关操作方法
        • 2.4.1、add()
        • 2.4.2、add(int index, E element)
        • 2.4.3、addAll(Collection c)
        • 2.4.4、get()
        • 2.4.5 set()
        • 2.4.6、remove(int index)
        • 2.4.7 remove(Object o)
        • 2.4.8、removeRange(int fromIndex, int toIndex)
        • 2.4.9、 indexOf()和lastIndexOf()方法
    • 3、Arraylist 和 Vector 的区别?
    • 4、Arraylist 与 LinkedList 区别?

1、List集合

1.1、List简介

List接口是一个有序的 Collection,使用此接口能够精确的控制每个元素插入的位置,能够通过索引(元素在List中位置,类似于数组的下标)来访问List中的元素,第一个元素的索引为 0,而且允许有相同的元素。List 接口存储一组可重复,有序(插入顺序)的对象。

1.2、其主要派生类

  • ArraylistObject[] 数组
  • Vector:Object[] 数组
  • LinkedList:双向链表

List集合和ArrayList集合源码

2、ArrayList集合源码

2.1、ArrayList的继承关系

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

List集合和ArrayList集合源码

继承关系说明

  1. extends AbstractList:说明了ArrayList具备AbstractList的一些属性和方法
  2. RandomAccess:实现了该接口,表明的ArrayList是支持快速随机访问的(我们可以通过元素序号进行对元素的访问)。
  3. Cloneable:实现了该接口,覆盖clone()函数,说明能被克隆
  4. java.io.Serializable:说明ArrayList支持序列化

2.2、相关属性

// 序列化id
private static final long serialVersionUID = 8683452581122892189L;

/**
* Default initial capacity. 默认的初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* Shared empty array instance used for empty instances.
* 指定该ArrayList容量为0时,返回该空数组。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
* 当调用无参构造方法,返回的是该数组。刚创建一个ArrayList 时,其内数据量为0。
* 它与EMPTY_ELEMENTDATA的区别就是:该数组是默认返回的,而EMPTY_ELEMENTDATA是在用户指定容量为0时返回。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
* 保存添加到ArrayList中的元素。 
* ArrayList的容量就是该数组的长度。 
* 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时,当第一次添加元素进入ArrayList中时,数组将扩容值DEFAULT_CAPACITY。 
* 被标记为transient,在对象被序列化的时候不会被序列化。
*/
transient Object[] elementData; // non-private to simplify nested class access

/**
* The size of the ArrayList (the number of elements it contains).
* ArrayList的实际大小(数组包含的元素个数/实际数据的数量)默认为0
* @serial
*/
private int size;
  
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
/**
* 分派给arrays的最大容量
* 为什么要减去8呢?
* 因为某些VM会在数组中保留一些头字,尝试分配这个最大存储容量,可能会导致array容量大于VM的limit,最终导致OutOfMemoryError。
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//备注:MAX.VALUE为0x7fffffff,转换成十进制就是2147483647,也就是数组的最大长度是2147483639;

属性说明

  1. serialVersionUID序列化id
  2. DEFAULT_CAPACITY:默认的初始容量为10
  3. EMPTY_ELEMENTDATA:指定该ArrayList容量为0时,返回该空数组
  4. DEFAULTCAPACITY_EMPTY_ELEMENTDATA当调用无参构造方法,返回的是该数组。 它与EMPTY_ELEMENTDATA的区别就是:该数组是默认返回的,而EMPTY_ELEMENTDATA是在用户指定容量为0时返回
  5. elementData保存添加到ArrayList中的元素。ArrayList的容量就是该数组的长度。被标记为transient,在对象被序列化的时候不会被序列化

2.3、构造方法

ArrayList()空参构造

 /**
  * Constructs an empty list with an initial capacity of ten.
  * 构造一个初始容量为10的空数组
  *
  * 不传初始容量,初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组,
  * 会在添加第一个元素的时候扩容为默认的大小,即10。
  */
 public ArrayList() {
     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }

如果是无参构造的话,就使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA进行初始化。

ArrayList(int initialCapacity)有参构造方法

/**
 * Constructs an empty list with the specified initial capacity.
 * 构造具有指定初始容量的空数组
 *
 * @param initialCapacity the initial capacity of the list 列表的初始容量
 * @throws IllegalArgumentException if the specified initial capacity is negative
 *
 * 传入初始容量,如果大于0就初始化elementData为对应大小,如果等于0就使用EMPTY_ELEMENTDATA空数组,
 * 如果小于0抛出异常。
 */
// ArrayList(int initialCapacity)构造方法
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("不合理的初识容量: " +
                initialCapacity);
    }
}

执行逻辑

  1. 判断所传入的参数是否大于0,大于0,就新创建一个长度特定的数组。
  2. 长度等于0,就使用EMPTY_ELEMENTDATA替代
  3. 长度小于0抛出异常。

ArrayList(Collection<? extends E> c)有参构造

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 * 把传入集合的元素初始化到ArrayList中
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
    // 将构造方法中的集合参数转换成数组
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 检查c.toArray()返回的是不是Object[]类型,如果不是,重新拷贝成Object[].class类型
        if (elementData.getClass() != Object[].class)
        	// 数组的创建与拷贝
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 如果c是空的集合,则初始化为空数组EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

执行逻辑

  1. 先将传入的集合转化为数组。
  2. 如果数组的长度不为0,就判断转换后的数组的Class是否为Object。如果不是还要将其转换为Object
  3. 如果数组长度为0,就使用EMPTY_ELEMENTDATA进行初始化。

2.4、相关操作方法

2.4.1、add()

在列表的末尾进行添加,时间复杂度为O(1)

    /**
     * Appends the specified element to the end of this list.
     * 将指定的元素追加到此列表的末尾
     * @param e element to be appended to this list 被添加到list的元素
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
		//确认list容量,如果不够,容量加1。注意:只加1,保证资源不被浪费
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //将元素e放在size的位置上,并且size++
        elementData[size++] = e;
        return true;
    }
	//数组容量检查,不够时则进行扩容,只供类内部使用 
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
		// 若elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA,则取minCapacity为DEFAULT_CAPACITY和参数minCapacity之间的最大值。DEFAULT_CAPACITY在此之前已经定义为默认的初始化容量是10。
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
	//数组容量检查,不够时则进行扩容,只供类内部使用 
	// minCapacity 想要的最小容量
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
		//最小容量>数组缓冲区当前长度
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);//扩容
    }

容量和大小说明

List集合和ArrayList集合源码

所以说在每一次进行添加元素的时候,我们都需要进行确认list容量,如果不够,进行扩容

1. elementData中的元素是空的情况

此时也就是 第一次添加元素 的时候。calculateCapacity返回的minCapacity = 10

2. elementData中的元素不是空的情况

此时也就不是 第一次添加元素 的时候。calculateCapacity返回的minCapacity = size + 1

3. 执行流程

  1. ensureCapacityInternal:数组容量检查
  2. calculateCapacityDEFAULT_CAPACITY和minCapacity之中最大的一个作为minCapacity
  3. ensureExplicitCapacity:判断是否需要进行扩容,如果需要扩容,就调用grow方法进行扩容;。如果minCapacity = 10(也就是elementData中的元素是空的情况下第一次进行添加元素),那么newCapacity = 10;否则就是新的容量=当前容量+当前容量/2

4.grow()方法的源码

    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *扩容,保证ArrayList至少能存储minCapacity个元素 
	 * 第一次扩容,逻辑为newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基础上增加一半。
	 第一次扩容后,如果容量还是小于minCapacity,就将容量扩充为minCapacity。
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
		// 获取当前数组的容量
        int oldCapacity = elementData.length;
		// 扩容。新的容量=当前容量+当前容量/2.即将当前容量增加一半(当前容量增加1.5倍)。
        int newCapacity = oldCapacity + (oldCapacity >> 1);
		//如果扩容后的容量还是小于想要的最小容量
        if (newCapacity - minCapacity < 0)
			//将扩容后的容量再次扩容为想要的最小容量
            newCapacity = minCapacity;
//elementData就空数组的时候,length=0,那么oldCapacity=0,newCapacity=0,在这里就是真正的初始化elementData的大小了,就是为10.
		//如果扩容后的容量大于临界值,则进行大容量分配
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //新的容量大小已经确定好了,就copy数组,改变容量大小。
        //copyof(原数组,新的数组长度)
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
	//进行大容量分配
    private static int hugeCapacity(int minCapacity) {
		//如果minCapacity<0,抛出异常
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
		//如果想要的容量大于MAX_ARRAY_SIZE,则分配Integer.MAX_VALUE,否则分配MAX_ARRAY_SIZE	
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

2.4.2、add(int index, E element)

在特定位置进行元素的添加,需要将相应位置的元素往后挪动一位,所以时间复杂度为O(n)

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 * 添加元素到指定位置,平均时间复杂度为O(n)。
 *  * @param index   指定元素要插入的索引
 * @param element 要插入的元素
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    // 检查是否越界
    rangeCheckForAdd(index);
    // 检查是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将inex及其之后的元素往后挪一位,则index位置处就空出来了
    // **进行了size-索引index次操作**
    System.arraycopy(elementData, index, elementData, index + 1,
            size - index);
    // 将元素插入到index的位置
    elementData[index] = element;
    // 元素数量增1
    size++;
}
/**
 * A version of rangeCheck used by add and addAll.
 * add和addAll方法使用的rangeCheck版本
 */
// 检查是否越界
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

执行流程

  1. 检查是否越界
  2. 检查是否进行扩容
  3. 将相应位置之后的元素相后挪动一位
  4. 将相应元素插入
  5. size ++

2.4.3、addAll(Collection c)

将集合c的元素追加到相应的集合中

/**
 * Appends all of the elements in the specified collection to the end of
 * this list, in the order that they are returned by the
 * specified collection's Iterator.  The behavior of this operation is
 * undefined if the specified collection is modified while the operation
 * is in progress.  (This implies that the behavior of this call is
 * undefined if the specified collection is this list, and this
 * list is nonempty.)
 * 将集合c中所有元素添加到当前ArrayList中
 *  * @param c collection containing elements to be added to this list
 * @return <tt>true</tt> if this list changed as a result of the call
 * @throws NullPointerException if the specified collection is null
 */
public boolean addAll(Collection<? extends E> c) {
    // 将集合c转为数组
    Object[] a = c.toArray();
    int numNew = a.length;
    // 检查是否需要扩容
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 将c中元素全部拷贝到数组的最后
    System.arraycopy(a, 0, elementData, size, numNew);
    // 集合中元素的大小增加c的大小
    size += numNew;
    // 如果c不为空就返回true,否则返回false
    return numNew != 0;
}

执行流程

  1. 将集合c转为数组
  2. 检查是否需要扩容
  3. 将c中元素全部拷贝到数组的最后
  4. 集合中元素的大小增加c的大小
  5. 如果c不为空就返回true,否则返回false

2.4.4、get()

由于ArrayList实现了RandomAccess接口,所以ArrayList支持快速随机访问所以该方法的时间复杂度为O(1)所以该方法的时间复杂度为O(1)

    /**
     * Returns the element at the specified position in this list.
     * 返回list中指定位置的元素
     * @param  index index of the element to return 要返回的元素的索引
     * @return the element at the specified position in this list
	 位于list中指定位置的元素
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        rangeCheck(index);//越界检查
        return elementData(index);//返回索引为index的元素
    }
    /**
     * Checks if the given index is in range.  If not, throws an appropriate
     * runtime exception.  This method does *not* check if the index is
     * negative: It is always used immediately prior to an array access,
     * which throws an ArrayIndexOutOfBoundsException if index is negative.
	 检查指定索引是否在范围内。如果不在,抛出一个运行时异常。
	 这个方法不检查索引是否为负数,它总是在数组访问之前立即优先使用,
	 如果给出的索引index>=size,抛出一个越界异常
     */
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

   /**
     * Constructs an IndexOutOfBoundsException detail message.
     * Of the many possible refactorings of the error handling code,
     * this "outlining" performs best with both server and client VMs.
     */
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    // Positional Access Operations 位置访问操作
	// 返回索引为index的元素
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

执行流程

  • 但是在每一次的获取元素时,我们都需要进行越界检查。如果越界就抛出相应的异常。
  • 返回相应索引位置的元素

2.4.5 set()

由于ArrayList支持快速随机访问,所以该方法时间复杂度为O(1)

    /**
     * Replaces the element at the specified position in this list with
     * the specified element.
     * 用指定的元素替换列表中指定位置的元素。
     * @param index index of the element to replace 要替换的元素的索引
     * @param element element to be stored at the specified position  要存储在指定位置的元素
     * @return the element previously at the specified position	 先前位于指定位置的元素(返回被替换的元素)
     * @throws IndexOutOfBoundsException {@inheritDoc} 如果参数指定索引index>=size,抛出一个越界异常
     */
    public E set(int index, E element) {
		//检查索引是否越界。如果参数指定索引index>=size,抛出一个越界异常
        rangeCheck(index);
		//记录被替换的元素(旧值)
        E oldValue = elementData(index);
		//替换元素(新值)
        elementData[index] = element;
		//返回被替换的元素
        return oldValue;
    }

执行流程

  1. 检查索引是否越界
  2. 记录要被替换的元素
  3. 使用新值替换旧值
  4. 返回被替换的元素

2.4.6、remove(int index)

根据索引值进行移除元素,时间复杂度为O(n)因为需要进行元素挪动

    /**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *删除list中位置为指定索引index的元素
	 * 索引之后的元素向左移一位
     * @param index the index of the element to be removed 被删除元素的索引
     * @return the element that was removed from the list 被删除的元素
     * @throws IndexOutOfBoundsException {@inheritDoc} 如果参数指定索引index>=size,抛出一个越界异常
     */
    public E remove(int index) {
		//检查索引是否越界。如果参数指定索引index>=size,抛出一个越界异常
        rangeCheck(index);
		//结构性修改次数+1
        modCount++;
		//记录索引处的元素
        E oldValue = elementData(index);
		// 删除指定元素后,需要左移的元素个数
        int numMoved = size - index - 1;
		//如果有需要左移的元素,就移动(移动后,该删除的元素就已经被覆盖了)
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
	 	// size减一,然后将索引为size-1处的元素置为null。为了让GC起作用,必须显式的为最后一个位置赋null值
	 	elementData[--size] = null; // clear to let GC do its work
		//返回被删除的元素
        return oldValue;
    }

执行流程

  1. 进行越界检查
  2. 记录修改次数(modCount 可以用来检测快速失败的一种标志。)
  3. 通过索引找到要删除的元素
  4. 计算要移动的位数
  5. 移动元素(其实是覆盖掉要删除的元素)
  6. 将–size上的位置赋值为null,让gc(垃圾回收机制)更快的回收它。
  7. 返回被删除的元素

2.4.7 remove(Object o)

根据对象进行移除。时间复杂度为O(n)。因为需要寻找相应的元素以及元素挪动

    /**
     * Removes the first occurrence of the specified element from this list,
     * if it is present.  If the list does not contain the element, it is
     * unchanged.  More formally, removes the element with the lowest index
     * <tt>i</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
     * (if such an element exists).  Returns <tt>true</tt> if this list
     * contained the specified element (or equivalently, if this list
     * changed as a result of the call).
     *从列表中删除指定元素的第一个出现项,
如果它存在的话。如果列表不包含该元素,它将保持不变。更正式地说,删除索引最低的元素...
     * @param o element to be removed from this list, if present
     * @return <tt>true</tt> if this list contained the specified element
     */
    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 remove method that skips bounds checking and does not
     * return the value removed.
	 私有的remove方法,该方法跳过边界检查,并且不返回已删除的值。
     */
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
	//arraycopy(原数组,源数组中的起始位置,目标数组,目标数据中的起始位置,要复制的数组元素的数量)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

执行流程

  1. 循环遍历寻找对应的元素。
  2. 找到后进行删除(包含了元素挪动)
  3. elementData[--size] = null让gc(垃圾回收机制)更快的回收它

2.4.8、removeRange(int fromIndex, int toIndex)

删除一个区间范围内的元素,时间复杂度为O(size - toIndex)

    /**
     * Removes from this list all of the elements whose index is between
     * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
     * Shifts any succeeding elements to the left (reduces their index).
     * This call shortens the list by {@code (toIndex - fromIndex)} elements.
     * (If {@code toIndex==fromIndex}, this operation has no effect.)
     * 从该列表中删除索引位于两者之间的所有元素,包含fromIndex,但是不包含toIndex,
	 * 将任何后续元素向左移动(减少它们的索引)
	 * 这个调用通过{@code (toIndex - fromIndex)}元素缩短列表。
	 *(如果{@code toIndex==fromIndex},此操作无效。)
     * @throws IndexOutOfBoundsException if {@code fromIndex} or
     *         {@code toIndex} is out of range
     *         ({@code fromIndex < 0 ||
     *          fromIndex >= size() ||
     *          toIndex > size() ||
     *          toIndex < fromIndex})
     */
    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;//被删除的索引后面的个数
        //arraycopy(原数组,源数组中的起始位置,目标数组,目标数据中的起始位置,要复制的数组元素的数量)
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);//新数组的长度
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

执行流程

  1. 此方法删除fromIndex到toIndex之间的全部元素,把toIndex以后的元素移动(size-toIndex)位
  2. 把左移后空的元素置为null好让垃圾回收机制回收内存
  3. 最后把新数组的大小赋值给size。

2.4.9、 indexOf()和lastIndexOf()方法

	 //返回此列表中指定元素的第一个出现项的索引,如果该列表不包含该元素,则返回-1。
    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。
    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;
    }

  1. indexOf()正向查找,返回第一个我们需要查找的元素下标,如果没有找到返回-1。
  2. lastIndexOf()反向查找,返回第一个我们需要查找的元素下标,如果没有找到返回-1。

3、Arraylist 和 Vector 的区别?

  1. ArrayList: 底层使用Object[ ]存储,适用于频繁的查找工作,线程不安全
  2. Vector : 底层使用Object[ ]存储,线程安全的

4、Arraylist 与 LinkedList 区别?

  1. 线程安全:Arraylist和LinkedList都是线程不安全的。
  2. 底层数据结构:Arraylist底层使用Object[ ]存储,LinkedList底层使用双向链表
  3. 插入删除元素Arraylist:底层采用的是数组进行存储,所以当添加元素的时候(add())是在列表的末尾进行添加,所以时间复杂度为O(1)。在特定i位置进行元素的添加(add(int index, E element))和删除时,需要将相应位置的元素进行挪动,所以时间复杂度为O(n - i)LinkedList :采用链表存储,当进行元素头部尾部的添加和删除时,时间复杂度为O(1)。而在特定位置进行添加删除时,时间复杂度为近似O(n)
  4. 是否支持快速随机访问Arraylist底层使用Object[ ]存储,所以我们可以通过元素索引进行快速随机访问LinkedList :采用链表存储,所以不支持高效的元素随机访问

程序员灯塔
转载请注明原文链接:List集合和ArrayList集合源码
喜欢 (0)