Java集合（二）List、ArrayList、LinkedList_java list arraylist linkedlist

  本系列文章：
    Java集合（一）集合框架概述
    Java集合（二）List、ArrayList、LinkedList
    Java集合（三）CopyOnWriteArrayList、Vector、Stack
    Java集合（四）Map、HashMap
    Java集合（五）LinkedHashMap、TreeMap
    Java集合（六）Hashtable、ConcurrentHashMap
    Java集合（七）Set、HashSet、LinkedHashSet、TreeSet
    Java集合（八）BlockingQueue、ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue、DelayQueue

【List】

一、List简介*

  List是有序集合，使用List可以控制列表中每个元素的插入位置，可以通过整数索引（列表中的位置）访问元素，并搜索列表中的元素。
  List通常允许重复的元素。
  使用List存储的特点：元素有序、可重复。
  List最常见的实现方式是ArrayList和LinkedList。以下是List接口常见实现类的对比：

  ArrayList是一个动态数组，随着容器中的元素不断增加，容器的大小也会随着增加。同时由于ArrayList底层是数组实现，所以可以随机访问元素。
  Vector与ArrayList类似，不过是同步的，因此Vector是线程安全的动态数组。
  Stack继承自Vector，实现一个后进先出的堆栈。
  LinkedList是一个双向链表，LinkedList不能随机访问，增删元素比较方便。
  CopyOnWriteArrayList是一个线程安全、并且在读操作时无锁的 ArrayList。当需要修改容器中的元素时，会首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。

  数据元素在内存中，主要有2种存储方式：顺序存储和链式存储。

• 1、顺序存储
    这种方式，相邻的数据元素存放于相邻的内存地址中，整块内存地址是连续的。可以根据元素的位置直接计算出内存地址，直接进行读取。读取一个特定位置元素的平均时间复杂度为O(1)。正常来说，只有基于数组实现的集合，才有这种特性。
    在List的实现类中，顺序存储以ArrayList为代表。
• 2、链式存储
    这种方式，每一个数据元素，在内存中都不要求处于相邻的位置，每个数据元素包含它下一个元素的内存地址。不可以根据元素的位置直接计算出内存地址，只能按顺序读取元素。读取一个特定位置元素的平均时间复杂度为O(n)。主要以链表为代表。
    在List的实现类中，链式存储以LinkedList为代表。

二、遍历List

  对于List集合的实现类，常见的遍历方式是：for循环、for each遍历和迭代器遍历。

2.1 不同遍历方式的使用

• 1、for循环遍历
    基于计数器。在集合外部维护一个计数器，然后依次读取每一个位置的元素，当读取到最后一个元素后停止。这种遍历方式主要就是需要按元素的位置来读取元素。示例：

	for (int i = 0; i < list.size(); i++) {
	    list.get(i);
	}
1
2
3

• 2、迭代器遍历
    示例：

	Iterator iterator = list.iterator();
	while (iterator.hasNext()) {
	    iterator.next();
	}
1
2
3
4

• 3、foreach 循环遍历
    foreach内部也是采用了Iterator的方式实现，使用时不需要显式声明Iterator或计数器。优点是代码简洁，不易出错；缺点是只能做简单的遍历，不能在遍历过程中操作数据集合，例如删除、替换。示例：

	for (String str : list) {
	}
1
2

2.2 不同遍历方式的适用场合

• 1、for循环遍历
    for循环遍历，适用于遍历顺序存储集合，因为读取性能比较高。扩展了说，for循环遍历适合实现了RandomAccess接口的集合。如果一个数据集合实现了该接口，就意味着它支持顺序访问，按位置读取元素的平均时间复杂度为 O(1)，如ArrayList。如果没有实现该接口，表示不支持顺序访问，如LinkedList。
• 2、迭代器遍历
    顺序存储：如果不是太在意时间，推荐选择此方式，毕竟代码更加简洁。
    链式存储：平均时间复杂度降为O(n)，所以推荐此种遍历方式。
    使用迭代器更加线程安全，因为它可以确保，在当前遍历的集合元素被更改的时候，它会抛出ConcurrentModificationException。

  综合而言，推荐的做法就是，支持顺序访问的List可用for循环遍历，否则建议用Iterator或foreach遍历。此外，如果需要在遍历时修改元素，则需要使用迭代器的遍历方式，否则会出现ConcurrentModificationException。

三、常见List实现类比较*

3.1 ArrayList和LinkedList

  LinkedList是一个双链表，在添加和删除元素时具有比ArrayList更好的性能，但在get与set方面弱于ArrayList。当然，这些对比都是指数据量很大或者操作很频繁。
  综合来说，在需要频繁读取集合中的元素时，更推荐使用ArrayList，而在插入和删除操作较多时，更推荐使用LinkedList。

• 快速随机访问
    快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index)方法)，对应到Java代码中，就是一个接口：

public interface RandomAccess {
}
1
2

  RandomAccess接口用来标识其实现类具有快速随机访问的特点。

• 两者效率对比
    当从头部依次添加元素时，链表和数组的性能差不不多。但当数据初始化完成之后，我们再进行插入操作时，尤其是从头部插入时，因为数组要移动之后的所有元素，因此性能要比链表低很多；但在查询时性能刚好相反，因为链表要遍历查询，并且LinkedList 是双向链表，所以在中间查询时性能要比数组查询慢了上万倍（查询 100 个元素），而两头查询（头部和尾部）时，链表也⽐数组慢了将近 1000 多倍（查询 100 个元素），因此在查询较多的场景中，我们要尽量使用数组，在添加和删除操作较多时，应该使用链表结构。
    数组和链表的操作时间复杂度对比：

3.2 ArrayList和Vector*

  这两个类都实现了List接口，他们都是有序集合。相同点：

1. ArrayList和Vector都是继承了相同的父类和实现了相同的接口。
2. 底层都是数组实现的。
3. 初始默认长度都为10。
4. 迭代器的实现都是fail-fast的。

  ArrayList和Vector的不同点：

  ArrayList与Vector都可以设置初始的空间大小， Vector还可以设置增长的空间大小，而ArrayList 没有提供设置增长空间的方法。
  ArrayList更加通用，因为我们可以使用Collections工具类轻易地获取同步列表和只读列表。

【ArrayList】

一、ArrayList介绍

  简单来说，ArrayList是动态数组（数组的容量会随着元素数量的增加而增加，即动态变化）。
  ArrayList的继承关系：

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

  在ArrayList中，并没有规定特殊的元素操作规则（比如只能在数组两端进行增删等），所以ArrayList是操作非常自由的动态数组：

1. 可以在数组头部 / 尾部 / 中间等任意位置插入、删除元素。
2. 添加单个或集合中的元素时，未指明添加位置时，都是添加在尾部。
3. 不会像队列那样在增加、取出元素时可能会产生阻塞现象。

1.1 ArrayList的特点*

• 1、自动扩容
    ArrayList是动态数组，这里的“动态”说的就是可以自动扩容。ArrayList默认初始容量为10，当容量不足时可以自动扩容（1.5倍扩容，即：原来大小+原来大小*0.5）。
    ArrayList的初始容量可以指定，扩容倍数(1.5)不能制定。
• 2、线程不安全
    ArrayList是线程不安全的，也实现了fail-fast机制。
• 3、访问元素效率高，增删元素效率低
    ArrayList实现了RandomAccess接口，支持随机访问。get、set、isEmpty等方法的时间复杂度都是O(1)，即遍历和随机访问元素效率比较高；add的时间复杂度是O(n)，添加和删除元素效率比较低。
• 4、可添加null,有序可重复
    ArrayList在添加元素时，并不需要进行非空判定，所以可以是null。ArrayList内的元素是有序的，所以也可重复。
• 5、元素下标是从0开始
    因为ArrayList底层实现是数组，所以下标是从0开始。
• 6、大量使用System.arraycopy()
    ArrayList是动态数组，所以肯定会有元素拷贝动作，ArrayList的实现中大量地调用了Arrays.copyof()和 System.arraycopy()方法，其实Arrays.copyof()内部也是调用 System.arraycopy()。System.arraycopy()为Native方法。
• 7、支持克隆和序列化
    ArrayList实现了Cloneable接口，支持克隆。
    ArrayList实现了Serializable接口，支持序列化，能通过序列化去传输。

1.2 ArrayList的使用

• 1、构造方法
    可以指定初始容量，也可以不指定。

	//构造一个初始容量为10的空ArrayList
	//（其实是构造了一个容量为空的ArrayList，第一次添加元素时，扩容为10）
	public ArrayList()
	//构造具有指定初始容量的空ArrayList  
	public ArrayList(int initialCapacity)
1
2
3
4
5

• 2、添加元素
    可以直接添加到尾部，也可以添加到指定位置。

	//将元素追加到此ArrayList的尾部
	public boolean add(E e)
	//在指定位置插入元素
	public void add(int index, E element)
1
2
3
4

• 3、删除元素
    可以删除某个元素，也可以清空ArrayList。

	//删除指定位置的元素
	public E remove(int index)
	//从ArrayList中删除第一个出现指定元素的（如果存在）
	public boolean remove(Object o)
	//清空ArrayList
	public void clear()
1
2
3
4
5
6

• 4、获取元素
    根据下标获取对应位置的元素，和数组类似。

	public E get(int index)
1

• 5、获取指定元素的下标
    可以从前向后，也可以从后向前，查找某个元素在ArrayList中的下标。

	//返回指定元素的第一次出现的索引，如果此ArrayList不包含元素，则返回-1
	public int indexOf(Object o)
	//返回指定元素的最后一次出现的索引，如果此ArrayList不包含元素，则返回-1
	public int lastIndexOf(Object o)
1
2
3
4

• 6、替换元素
    和数组类似，替换指定下标的元素，并且将原下标对应的元素返回。

	//替换元素，返回原有元素
	public E set(int index, E element)
1
2

• 7、截取ArrayList
    截取ArrayList的子串。

	//返回此ArrayList中指定的 fromIndex （包括）和 toIndex（不包括）之间的子ArrayList
	public List< E > subList(int fromIndex, int toIndex)
1
2

• 8、通用性方法
    判断ArrayList是否为空、获取总的元素数等。

	//判断ArrayList是否为空
	public boolean isEmpty()
	//返回ArrayList中的元素数
	public int size()
	//判断是否包含某个元素
	public boolean contains(Object o)
1
2
3
4
5
6

二、从源码理解ArrayList

  ArrayList里的变量：

    //版本号，用于序列化
	private static final long serialVersionUID = 8683452581122892189L;
    //默认的初始容量
	private static final int DEFAULT_CAPACITY = 10;
    //初始容量为0时，elementData指向该数组
	private static final Object[] EMPTY_ELEMENTDATA = {};
    //也是个空数组。简单来说，和EMPTY_ELEMENTDATA差异的地方在于：没有指定初始容量时，
    //elementData指向该数组。
	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    //元素数组
	transient Object[] elementData;
    //元素个数
	private int size;
1
2
3
4
5
6
7
8
9
10
11
12
13

• elementData
    elementData是存储数据的数组，元素类型为Object类型，即可以存放所有类型数据（至于ArrayList中具体存储什么类型的元素，一般通过泛型去规范），对ArrayList中所存储数据的所有操作都是基于该数组的。
    elementData通常会预留一些容量，等容量不足时再扩充容量。elementData用transient修饰 ，就可以保证只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间。

2.1 创建ArrayList对象

  常用的构造方法不指定初始容量的方式，默认容量为10。

    public ArrayList() {
    	//DEFAULTCAPACITY_EMPTY_ELEMENTDATA是个空数组.但在添加元素时，第一次对数组
    	//进行扩容时，会将数组容量扩展为10，所以我们此时可以把ArrayList的容量看作10
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
1
2
3
4
5

  此时可以假设ArrayList的容量为10（因为首次扩容时容量为10），数组中元素的数量size为0：

  ArrayList还支持指定初始容量、利用集合来创建的2种方式。

	//构造具有指定初始容量的空列表
    public ArrayList(int initialCapacity
  	//构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序
  	public ArrayList(Collection<? extends E> c)
1
2
3
4

2.2 往ArrayList中添加元素

• 1、添加元素到数组尾部
    先判断是否需要扩容，需要的话就扩容，再添加元素到数组已有元素末尾。

    public boolean add(E e) {
    	//判断是否需要扩容，确保处理后的容器能存下size + 1个元素
        ensureCapacityInternal(size + 1);
        //将元素追加到数组尾部
        elementData[size++] = e;
        return true;
    }
1
2
3
4
5
6
7

  以之前创建的10个容量的空ArrayList为例，添加一个元素后的ArrayList：

  如果此时再调用add方法先后添加2、3两个元素后，ArrayList会变成：

• 2、添加元素到数组的指定位置
    除了可以将元素增加到现有元素尾部，还可以添加在指定位置。相比于直接添加在尾部，多了一步从指定位置处元素向后移动一位的操作。

	//在指定位置添加元素
    public void add(int index, E element) {
    	//先判断index位置是否合法
        rangeCheckForAdd(index);
		//判断是否需要扩容
        ensureCapacityInternal(size + 1); 
        //将index到尾部的元素向后移动一位
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //将元素放置在index位置上
        elementData[index] = element;
        size++;
    }
    
	//index参数不合法，就抛IndexOutOfBoundsException
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

  之前的"1"、“2”、"3"都是直接追加到ArrayList现有元素的后面的，ArrayList当然还支持在指定位置添加元素，假设调用add(1,4)方法，就会在下标索引为1的位置添加元素4。这个过程分为以下几步：

2.3 从ArrayList中删除元素

• 1、删除数组指定位置的元素
    该方法的思路较简单：删除对应位置的元素，其后位置的元素前移。

    public E remove(int index) {
    	//校验index是否合法
        rangeCheck(index);

        modCount++;
        //取出index位置元素（为了返回该元素）
        E oldValue = elementData(index);
        //删除元素后，要移动的元素数
        int numMoved = size - index - 1;
        //如果删除的元素不是最后一个元素，就要将被删除元素后面的元素向前移动
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //将数组元素的最后一个位置置为null，为了GC
        elementData[--size] = null; 

        return oldValue;
    }
	//index参数超过数组元元素数的最大位置，抛IndexOutOfBoundsException
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

  在删除元素后，需要将对应的一个位置或多个位置设置为Null，是为了GC。

• 2、删除数组中第一个出现的某个元素，数组中不存在则不删除
    这种删除元素的方式主要分为两步：

1. 找出元素所在位置；
2. 删除对应位置的元素，其后位置的元素前移。

	//删除在数组第一次出现的指定元素
    public boolean remove(Object o) {
    	//判断要删除的元素是否为null
        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; 
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

  以上的两个删除元素的方法，其实大致思路相似：先找到index，再删除对应位置上的元素，被删除元素位置后面的元素往前移动一位，删除数组尾部元素。图示：

• 3、清空数组
    每个位置都置为null。

    public void clear() {
        modCount++;
        //清空数组元素，置为null，为了GC
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }
1
2
3
4
5
6
7
8

2.4 获取指定位置的元素

  和从数组中获取元素类似，根据数组下标获取元素。

    public E get(int index) {
    	//检验位置参数是否合法
        rangeCheck(index);
		//将该位置元素返回
        return elementData(index);
    }
1
2
3
4
5
6

2.5 替换指定位置的元素

  根据数组下标替换元素。

• set(int index, E element)

    public E set(int index, E element) {
    	//先校验位置元素是否合法
        rangeCheck(index);
		//取出该位置旧元素，放置新元素，再将旧元素返回
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
1
2
3
4
5
6
7
8

2.6 查找指定元素所在位置

  检索元素的方法有两个：检索元素第一次出现的位置和检索元素最后一次出现的位置。

• 1、检索元素第一次出现的位置
    从前往后遍历数组。

	//从前向后遍历，返回指定元素（或null）第一次出现的位置
    public int indexOf(Object o) {
    	//判断要检索的元素是否为null
        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
2
3
4
5
6
7
8
9
10
11
12
13
14

• 2、检索元素最后一次出现的位置
    从后往前遍历数组。

	//从后向前遍历，返回指定元素（或null）最后一次出现的位置
    public int lastIndexOf(Object o) {
    	//判断要检索的元素是否为null
        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
2
3
4
5
6
7
8
9
10
11
12
13
14

2.7 自动扩容机制*

  ArrayList自动扩容的本质就是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去。
  自动扩容时的方法调用：add --> ensureCapacityInternal --> calculateCapacity --> grow --> hugeCapacity。

  自动扩容机制是每次向数组中添加元素前，必须要做的判断操作，因此自动扩容的入口在add方法：

    public boolean add(E e) {
    	//判断是否可以容纳e，若能，则直接添加在末尾；
    	//若不能，则进行扩容，然后再把e添加在末尾
        ensureCapacityInternal(size + 1); 
        //将e添加到数组末尾
        elementData[size++] = e;
        return true;
    }

	//每次在add()一个元素时，arraylist都需要对这个list的容量进行一个判断。
	//通过ensureCapacityInternal()方法确保当前ArrayList维护的数组具有存储
	//新元素的能力，经过处理之后将元素存储在数组elementData的尾部
    private void ensureCapacityInternal(int minCapacity) {
    	//先判断一下是否是使用无参构造方法创建的ArrayList对象，
    	//如果是的话，就设置默认数组大小为DEFAULT_CAPACITY（10）
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        //如果修改后的(最小)数组容量minCapacity大于当前的数组长度elementData.length，
        //那么就需要调用grow方法进行扩容，反之则不需要
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        //目前数组长度
        int oldCapacity = elementData.length;
        //先将当前数组容量扩充至1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //newCapacity：扩容1.5倍后的新数组容量
        //minCapacity：数组存储元素所需要的最小容量
        //检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么
        //就把最小需要容量当作数组的新容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果新容量大于MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8),
        //调用hugeCapacity方法来获取扩容后数组的合适大小
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //将源数组复制到newCapcity大小的新数组上
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //对minCapacity和MAX_ARRAY_SIZE进行比较
        //若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
        //若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

  综上所述，ArrayList自动扩容流程：

• 1、是否用无参构造方法创建的ArrayList对象。如果是，则ArrayList新容量为10。
• 2、经过第一步后，判断新容量是否够用，不够用就进入扩容流程核心方法grow。
• 3、在grow扩容时，涉及到两个变量：
    newCapacity：扩容1.5倍后的新数组容量；
    minCapacity：数组存储元素所需要的最小容量，由现有数组元素数量size+1得来。
    取两者较大者作为newCapacity。

1. 此处为什么要用【初始容量 * 1.5】和【初始容量+1】相比。因为假如初始容量较小(比如0、1、2、3、4)，那么【初始容量 * 1.5】未必大于【初始容量+1】。
2. MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8。

• 4、newCapacity与MAX_ARRAY_SIZE比较。
    如果newCapacity< MAX_ARRAY_SIZE，则newCapcity不变。
    如果newCapacity>MAX_ARRAY_SIZE，再比较minCapacity和MAX_ARRAY_SIZE的大小。如果大于，就令newCapacity = Integer.MAX_VALUE；否则newCapacity = MAX_ARRAY_SIZE。
• 5、将源数组复制到newCapcity大小的新数组上。

  这里面有个ArrayList最大容量的问题，常规情况下ArrayList的最大容量为Integer.MAX_VALUE - 8，看源码：

    /**
     * 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
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
1
2
3
4
5
6
7

  ArrayList的存储空间，除了要存元素，还要存储对象头信息，所以-8，避免发生OOM。当然，从代码看，如果Integer.MAX_VALUE - 8的空间不够用的话，还是会将数组空间设置为Integer.MAX_VALUE。

三、ArrayList相关问题

3.1 Array和ArrayList的区别

3.2 多线程场景下如何使用ArrayList

  常见的方法有以下几种：

• 1、通过Collections的synchronizedList方法将其转换成线程安全的容器后再使用：

	List<String> synchronizedList = Collections.synchronizedList(list);
1

• 2、加锁：

	synchronized(list.get()) {
		list.get().add(model);
	}
1
2
3

• 3、直接使用线程安全的集合，如CopyOnWriteArrayList，替换线程不安全的ArrayList：

	List<Object> list1 = new CopyOnWriteArrayList<Object>();
1

3.3 System.arraycopy和Arrays.copyOf

  其实Arrays.copyof()也是调用System.arraycopy()来实现的。

• 1、System.arraycopy
    在ArrayList的源码中，增删元素时，要移动元素，而移动数组内的元素都是通过System.arraycopy方法来实现的。

	//Object src : 原数组
	//int srcPos : 从元数据的起始位置开始
	//Object dest : 目标数组
	//int destPos : 目标数组的开始起始位置
	//int length  : 要copy的数组的长度
	public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
1
2
3
4
5
6

  看个例子：

		int[] arrs = {1,2,3,4,5,6,7,8,9,10};
		for(int i=0;i<arrs.length;i++)
			System.out.print(arrs[i]+" "); //1 2 3 4 5 6 7 8 9 10
			
		System.out.println();
		//将arrs数组从下标为5的位置开始复制，总共复制5个元素，
		//将上面的元素复制到arrs数组，起始位置的下标为0
        System.arraycopy(arrs, 5,arrs, 0,5);
        
		for(int i=0;i<arrs.length;i++)
			System.out.print(arrs[i]+" "); //6 7 8 9 10 6 7 8 9 10
1
2
3
4
5
6
7
8
9
10
11

• 2、Arrays.copyOf
    在数组进行扩容时，原有数组中元素的迁移是通过Arrays.copyOf方法来实现的：

	//original：要复制的原数组
	//newLength：指定要建立的新数组长度，如果新数组的长度超过原数组的长度，则保留数组默认值
	//返回值：新的数组对象，改变传回数组中的元素值，不会影响原来的数组
	public static < T > T[ ] copyOf(T[ ] original, int newLength) 
1
2
3
4

  看个例子：

		 	int[] arr1 = {1, 2, 3, 4, 5}; 
		    int[] arr2 = Arrays.copyOf(arr1, 5);
		    int[] arr3 = Arrays.copyOf(arr1, 10);
		    for(int i = 0; i < arr2.length; i++) 
		        System.out.print(arr2[i] + " "); 
		    		System.out.println();  //1 2 3 4 5 
		    for(int i = 0; i < arr3.length; i++) 
		        System.out.print(arr3[i] + " ");  //1 2 3 4 5 0 0 0 0 0
			}
1
2
3
4
5
6
7
8
9

3.4 ArrayList的扩容因子为什么是1.5*

  关于扩容因子，有一个很通俗的解释，扩容因子最适合范围为(1, 2)。
  为什么不取扩容固定容量呢？扩容的目的需要综合考虑这两种情况：

1、扩容容量不能太小，防止频繁扩容，频繁申请内存空间和数组频繁复制。
2、扩容容量不能太大，需要充分利用空间，避免浪费过多空间。

  为什么是1.5，而不是1.2、1.25、1.8或者1.75？因为1.5可以充分利用移位操作，减少浮点数或者运算时间和运算次数。

	// 新容量计算
	int newCapacity = oldCapacity + (oldCapacity >> 1);
1
2

【LinkedList】

一、LinkedList介绍

  简单来说，LinkedList是一个双向链表：

  LinkedList中存放的不是普通的某个中类型的元素，而是节点（Node）。
  LinkedList通过prev、next将不连续的内存块串联起来使用。LinkedList是双向链表，除头节点的每一个元素都有prev（前驱指针）同时再指向它的上一个元素，除尾节点的每一个元素都有next（后继指针）同时再指向它的下一个元素。

  LinkedList的继承关系：

	public class LinkedList<E> extends AbstractSequentialList<E>
    	implements List<E>, Deque<E>, Cloneable, java.io.Serializable
1
2

1.1 LinkedList特点*

• 1、底层实现是双向链表
    LinkedList内部是一个双向链表（可以双向遍历）的实现，一个节点除了存储自身的数据外，还持有前、后两个节点的引用。
• 2、增删快、查询慢
    LinkedList具有对前后元素的引用，删除、插入节点很快，因为不需要移动其他元素，只需要改变部分节点的引用即可。
    LinkedList元素存储地址不连续，不支持随机访问，所以查询速度相比于ArrayList，是比较慢的。
• 3、线程不安全
    LinkedList是线程不安全的，也实现了fail-fast机制。
• 4、元素有序可重复
    LinkedList中的前后指针可以保证元素的顺序，因此可以重复。
• 5、删除、添加操作时间复杂度为O(1)，查找时间复杂度为O(n)
    查找函数有一定优化，容器会先判断查找的元素是离头部较近，还是尾部较近，来决定从头部开始遍历还是尾部开始遍历，因此推荐使用迭代器进行遍历。
• 6、实现了Deque接口，因此也可以作为栈、队列和双端队列来使用
    LinkedList在首尾两端都可以操作，因此可以充当栈、队列和双端队列的实现工具。
• 7、可以存储Null值
    Node中的item可以为null。

1.2 LinkedList的使用

• 1、 构造方法
    一般构造空链表。

	//构造一个空链表
	public LinkedList()
	//用已有的集合创建链表的构造方法
	public LinkedList(Collection<? extends E> c) 
1
2
3
4

• 2、添加元素
    因为LinkedList是双向链表，在首尾都可以操作，所以从首部和尾部添加元素均可。添加元素的方法分为3类：addXxxx、offerXxx、push。
    addXxxx：可在首部尾部添加，无返回值。
    offerXxx：可在首部尾部添加，有返回值。
    push：在首部添加，无返回值。

	//将元素追加到此链表末尾
	public boolean add(E e)
	//在链表的指定位置插入元素
	public void add(int index, E element) 
	//在链表的首部插入元素
	public void addFirst(E e)
	//将元素追加到链表末尾
	public void addLast(E e)
	//将元素添加到链表的尾部
	public boolean offer(E e)
	//在链表的首部插入元素
	public boolean offerFirst(E e)
	//在链表的末尾插入元素
	public boolean offerLast(E e)
	//在链表的头部添加元素
	public void push(E e)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 3、删除元素
    因为LinkedList是双向链表，在首尾都可以操作，所以从首部和尾部删除元素均可。添加元素的方法分为3类：removeXxx、clear。
    removeXxx：删除后可以返回被删除的元素，也可以返回表示删除结果的boolean值。
    clear：删除所有元素，即清空链表。

	//删除链表中指定位置的元素
	public E remove(int index)
	//从链表中删除指定元素的第一个出现（如果存在）
	public boolean remove(Object o)
	//从链表中删除并返回第一个元素
	public E removeFirst()
	//删除链表中指定元素的第一个出现（从头到尾遍历列表时）
	public boolean removeFirstOccurrence(Object o)
	//从链表中删除并返回最后一个元素
	public E removeLast()
	//删除链表中指定元素的最后一次出现（从头到尾遍历列表时）
	public boolean removeLastOccurrence(Object o)
	//清空链表
	public void clear()
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 4、检索并删除元素
    删除首部/尾部的元素，并把该元素返回。分为pop、remove、pullXxx3类。
    pop/remove：删除并返回链表首部的元素。
    pullXxx：可以删除并返回首部/尾部的元素。

	//检索并删除链表的首部元素
	public E poll()
	//检索并删除链表的第一个元素，如果此LinkedList为空，则返回 null 
	public E pollFirst()
	//检索并删除链表的最后一个元素，如果链表为空，则返回 null 
	public E pollLast()
	//删除并返回链表的第一个元素
	public E pop()
	//检索并删除链表的首部元素
	public E remove()
1
2
3
4
5
6
7
8
9
10

• 5、查找元素
    仅查找、不删除元素，有element、getXxx、peekXxx3类。

	//检索但不删除链表首部元素
	public E element()
	//返回链表指定位置的元素
	public E get(int index)
	//返回链表中的第一个元素
	public E getFirst()
	//返回链表中的最后一个元素
	public E getLast()
	//获取且不删除链表首部节点中的元素
	public E peek()	
	//检索但不删除链表的第一个元素，如果链表为空，则返回 null 
	public E peekFirst()
	//检索但不删除链表的最后一个元素，如果链表为空，则返回 null 
	public E peekLast()
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 6、检索元素位置
    从前向后、从后向前，

	//返回链表中指定元素的第一次出现的索引，如果此列表不包含元素，则返回-1
	public int indexOf(Object o)
	//返回链表中指定元素的最后一次出现的索引，如果此列表不包含元素，则返回-1
	public int lastIndexOf(Object o)
1
2
3
4

• 7、替换元素
    用指定的元素替换链表中指定位置的元素，并返回被替换的元素。

	public E set(int index, E element)
1

• 8、通用性方法
    获取链表元素的个数等。

	//返回链表中的元素数
	public int size()
	//判断链表中是否包含某个元素
	public boolean contains(Object o)
1
2
3
4

二、从源码理解LinkedList

  LinkedList里的变量：

    //元素个数
    transient int size = 0;
    //链表的头结点
	transient Node<E> first;
    //链表的尾结点
	transient Node<E> last;
1
2
3
4
5
6

  可以看出：头结点和尾节点的节点类型，都是静态内部类Node。一个Node中包含前驱指针、节点值和后继指针三个部分：

    private static class Node<E> {
    	//节点的值
        E item;
        //当前节点的后一个节点的引用
        Node<E> next;
        //当前节点的前一个节点的引用
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.1创建LinkedList对象

  因为LinkedList是基于链表的，所以不需要指定初始容量。常用的是无参构造方法。

    public LinkedList() {
    }
1
2

  LinkedList还支持通过其他集合来创建对象。

    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
1
2
3
4

  addAll方法的实现为：依次取出集合中的元素，追加到链表的尾部，其实就是在first节点后面一直添加元素。

2.2 往链表里添加节点

  LinkedList的存储单元为一个名为Node的内部类，包含pre指针，next指针，和item元素。所以向List中添加元素时，会先将要添加的元素封装成Node，再添加到List中。

• 1、将元素添加到链表尾部

	//add(E e)和addLast(E e)都是将元素添加到链表尾部，
	//区别就是一个有boolean返回值，一个没有
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    public void addLast(E e) {
        linkLast(e);
    }

    void linkLast(E e) {
    	//用临时变量l存储尾节点
        final Node<E> l = last;
        //构造了一个新节点newNode，该节点的前一个节点为l，节点值为e，后一个节点为null
        final Node<E> newNode = new Node<>(l, e, null);
        //将新创建的newNode作为尾节点
        last = newNode;
        //如果添加newNode前，之前的尾节点为null，代表链表为bull，因此newNode同时也就成了首节点
        if (l == null)
            first = newNode;
        //否则将newNode追加到原来的尾节点之后
        else
            l.next = newNode;
        //链表容量+1
        size++;
        //链表操作数+1
        modCount++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

  add(E e) / addLast(E e)方法的作用都是将元素追加到链表尾部，图示：

• 2、将元素添加到链表首部

	//在链表的头部添加元素
    public void push(E e) {
        addFirst(e);
    }

    public void addFirst(E e) {
        linkFirst(e);
    }

    private void linkFirst(E e) {
    	//创建临时变量f存储链表原来的首节点
        final Node<E> f = first;
        //构造一个新节点newNode，前一个节点为null，该节点值为e，后一个节点为f
        final Node<E> newNode = new Node<>(null, e, f);
        //将新节点newNode作为first节点
        first = newNode;
        //如果原有first节点为null，则代表原来链表为null，因此新创建的节点newNode同时为头节点和尾节点
        if (f == null)
            last = newNode;
        //否则新节点newNode作为原来头结点的前一个节点
        else
            f.prev = newNode;
        //链表元素数+1
        size++;
        modCount++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

  图示：

• 3、将元素添加到链表的指定位置

    public void add(int index, E element) {
    	//校验index参数
        checkPositionIndex(index);
		//判断位置参数是否与链表长度一致，如果一致的话，直接将元素追加到链表末尾
        if (index == size)
            linkLast(element);
        //否则就添加到index位置，原来的index位置的元素成为新插入元素的后继元素
        else
            linkBefore(element, node(index));
    }
	//在指定节点succ之前插入指定元素e。指定节点succ不能为null
    void linkBefore(E e, Node<E> succ) {
        //获得指定节点的前驱节点
        final Node<E> pred = succ.prev;
        //创建新节点newNode，其前驱节点为pred，节点值为e，后继节点为succ
        final Node<E> newNode = new Node<>(pred, e, succ);
        //succ的前驱节点为新节点newNode
        succ.prev = newNode;
        
        //判断原来该位置节点的前驱节点是否为null，如果为null，代表原来该位置的节点succ为首节点
        //因此，新创建的节点newNode就成为头节点
        if (pred == null)
            first = newNode;
        //否则为原来该位置节点的前驱节点的后继节点
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

  图示：

• 4、将另一个集合的元素添加到链表中
    上面的方法都是添加单个元素，这两个方法是添加集合中的多个元素，因此主要的差异就是：将添加单个元素的操作循环进行了多次。

	//在链表的末尾添加集合的全部元素
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
	//在链表的任意位置插入集合的全部元素
    public boolean addAll(int index, Collection<? extends E> c) {
    	//检验index参数合法性
        checkPositionIndex(index);
		//将集合转化成了数组
        Object[] a = c.toArray();
        //获取要插入集合的元素个数numNew 
        int numNew = a.length;
        if (numNew == 0)
            return false;
		//pred代表要插入位置的前驱节点，succ代表要插入位置的节点
        Node<E> pred, succ;
        //如果index和链表的长度相等，那么此时的pred就是原有的last节点，succ为null
        //因为链表在get(index)元素时，下标也是从0开始的
        if (index == size) {
            succ = null;
            pred = last;
        //否则succ就是原来index位置上的节点，pred就是succ的前驱节点
        } else {
            succ = node(index);
            pred = succ.prev;
        }
		//迭代的插入元素过程
        for (Object o : a) {
            @SuppressWarnings("unchecked") 
            E e = (E) o;
            //将集合中的元素取出来，作为新创建的节点的节点值，pred代表要插入位置的前驱节点，后继节点为null
            Node<E> newNode = new Node<>(pred, e, null);
            //如果pred为null，代表要插入的位置前面没有节点了，所以该节点就要成为头结点
            if (pred == null)
                first = newNode;
            //否则前一个节点的后继节点是新节点
            else
                pred.next = newNode;
            //至关重要的一步，将新插入的节点作为pred节点，以便继续向后增加节点
            pred = newNode;
        }
		//当succ==null,也就是新添加的节点位于LinkedList集合的最后一个元素的后面，
		//那么在之前添加的最后一个元素pred就成为了尾节点
        if (succ == null) {
            last = pred;
        //否则succ是pred的后继节点，pred是succ的前驱节点
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

• 5、在首部/尾部添加单个元素，并返回元素添加的结果
    添加单个元素，相比上面的添加单个元素的方法，多了boolean型的返回值。

	//在链表尾部添加元素
    public boolean offer(E e) {
        return add(e);
    }
	//在链表首部添加元素
    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }
	//在链表尾部添加元素
    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.3 从链表中删除节点

• 1、删除指定位置的节点

	//按索引删除指定元素
    public E remove(int index) {
    	//检验index参数是否合法，不合法就抛出IndexOutOfBoundsException
        checkElementIndex(index);
        return unlink(node(index));
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    //删除节点
    E unlink(Node<E> x) {
        // assert x != null;
        //取出该节点的数据（用于方法最后作为返回值）
        final E element = x.item;
        //取出该节点的前后节点：prev、next 
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
		//判断该节点的前驱节点是否存在，不存在的话，该节点的后继节点就是first节点
        if (prev == null) {
            first = next;
        //否则就将next节点（要删除的节点的后继节点）赋于原有的前驱节点的后继节点，
        //index位置的前驱节点置空
        } else {
            prev.next = next;
            x.prev = null;
        }
		//判断该节点的后继节点是否存在,如果为空，要删除的节点的前驱节点就变成last节点
        if (next == null) {
            last = prev;
        //否则后继节点的前驱节点直接prev，index位置的后继节点置空
        } else {
            next.prev = prev;
            x.next = null;
        }
		//将index位置节点的数据置空。这样原有index位置节点的前驱、后继指针及数据
		//全都为空，便于GC回收，最后size--，返回原有位置的数据
        x.item = null;
        size--;
        modCount++;
        return element;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

• 2、删除第一次出现的指定节点

	//删掉第一个出现指定数据的节点
    public boolean removeFirstOccurrence(Object o) {
        return remove(o);
    }

    public boolean remove(Object o) {
    	//判断要删除的元素是否为null
    	//如果是null，删除null
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        //如果不是null，则删除对应的元素
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

  remove(int index)、removeFirstOccurrence(Object o) /、remove(Object o)，这些方法可以理解为删除链表中间某个节点，图示：

• 3、删除链表首部节点

	//删除链表首部元素
    public E pop() {
        return removeFirst();
    }
	//删除链表首部元素
    public E remove() {
        return removeFirst();
    }
	//删除链表首部元素
    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        //将原来first节点的数据域和next指针都置空
        f.item = null;
        f.next = null; 
        first = next;
        //判断原有first的next节点是否为空，如果为空，说明此时链表已空，last = null
        if (next == null)
            last = null;
        //否则不处理last节点，只需将原来的next节点的前驱指针置空即可（这样这个节点就变成了first节点）
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

  pop() / remove() / removeFirst()这些方法的作用是删除链表首部元素，图示：

• 4、删除链表尾部节点

	//删除最后一个节点
    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        //先保存一下last节点的前驱节点，然后将last节点的数据和前驱指针置空
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; 
        last = prev;
        //判断前驱节点是否为空，如果是的话，就将first节点也置空（此时为空链表）
        if (prev == null)
            first = null;
        //否则将原有前驱节点的后继指针置空
        else
            prev.next = null;
        //size减1
        size--;
        modCount++;
        //返回原有last节点值
        return element;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

  removeLast()方法的作用是删除链表尾部元素，与上面的过程相似，不过操作的位置是链表的尾部，图示：

• 5、删除最后一次出现的指定节点

	//删除最后一个出现的指定数据
    public boolean removeLastOccurrence(Object o) {
    	//如果指定元素为null，就从后向前删除null
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        //如果指定元素不为null，就从后向前删除对应的元素
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 6、清空链表

    public void clear() {
    	//每个节点的前驱、后继指针和数据域全部清空，置为null
        for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        first = last = null;
        //size置为0
        size = 0;
        modCount++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

  clear()方法的作用是清空链表，图示：

2.4 获取链表中的节点

• 1、获取链表指定位置节点中的元素

    public E get(int index) {
    	//检验index参数合法
        checkElementIndex(index);
        //按索引获取对应元素
        return node(index).item;
    }
1
2
3
4
5
6

• 2、获取链表首部/尾部节点中的元素

	//获取首节点中的元素
    public E element() {
        return getFirst();
    }
	//获取首节点中的元素
    public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }
	//获取尾节点中的元素
    public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

  可以看出：在链表为空时，获取元素会抛出NoSuchElementException。

• 3、获取且不删除链表指定位置节点中的元素

	//获取且不删除链表首部节点中的元素
    public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }
	//获取且不删除链表首部节点中的元素
    public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }
	//获取且不删除链表尾部节点中的元素
    public E peekLast() {
        final Node<E> l = last;
        return (l == null) ? null : l.item;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 4、获取且删除链表指定位置节点中的元素

	//获取且删除链表首部节点中的元素
    public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
	//获取且删除链表首部节点中的元素
    public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
	//获取且删除链表尾部节点中的元素
    public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.5 更新元素

    public E set(int index, E element) {
    	//检验index参数合法性
        checkElementIndex(index);
        //取出旧的节点值，替换为新的节点值
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        //将旧的节点值返回
        return oldVal;
    }
1
2
3
4
5
6
7
8
9
10

  此处有个node(index)方法，作用是根据索引查找链表中对应位置的节点：

    Node<E> node(int index) {
		//判断该索引在链表的前半部分还是在后半部分
		//如果在前半部分，从前向后检索
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        //如果在后半部分，从后向前检索
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

  node(index)方法是根据索引获取链表中元素的方法。由于LinkedList是双向链表，存在从前向后、从后向前两种遍历方式。所以在获取某个位置元素时，就可以根据这个元素的索引在前半部还是后半部来决定采用哪种方式获取元素，这也就是node方法的全部，图示：

2.6 查找某个元素在链表中的位置

• 1、从前向后检索某个元素的所在位置

	//从first节点开始，从前向后检索某个元素所在位置
    public int indexOf(Object o) {
        int index = 0;
        //判断要检索的元素是否为null，是的话检索null，否则检索元素
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 2、从后向前检索某个元素的所在位置

	//从last节点开始，从后向前检索某个元素所在位置
    public int lastIndexOf(Object o) {
        int index = size;
        //判断要检索的元素是否为null，是的话检索null，否则检索元素
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19