List总结

发表于 | 分类于

ArrayList

小结

  • ArrayList底层实现是数组，而且允许元素为null值
  • 增加和删除的操作效率低，因为有扩容和数组复制的开销存在（如果是根据下标去删除元素的会比较快）
  • 查询和修改的效率较高，可以直接通过下标去访问元素，时间复杂度为O(1)
  • ArrayList 插入元素需要复制的元素，所以 ArrayList 插入元素的位置越靠后效率越高
  • 多线程操作同一个ArrayList是不安全的

PS：如果事先知道要存储的元素个数，那么最好使用带int参数的构造函数，因为这样能够减少数组扩容的开销

大致结构

​ ArrayList是使用数组实现的列表，具有顺序性。ArrayList内部使用了transient Object[] elementData; 来存储列表中的元素（即数组的缓存区）；ArrayList的容量就是该缓存区的数组长度

  1. private static final int DEFAULT_CAPACITY = 10 默认容量，只有在add的时候判断elementData是空数组的时候，就会初始化这个默认容量的数组赋值给elementData

  2. modCount 这个属性是用来记录List列表的表结构发生变化的次数（要对list的结构发生变化的操作，都会使得modCount的值进行加一；结构性操作指对列表长度进行修改的，即add/remove操作）；这个属性比较重要

modCount其实是fail-fast 机制的实现，即当某一个线程A通过Iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件

构造方法

  1. 无参构造方法
1
2
3
4
5
6
7
//无参构造方法
//无参的构造函数得到的是一个空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
  1. 带int参数的构造方法
1
2
3
4
5
6
7
8
9
10
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
  • 参数大于0返回int大小的数组
  • 参数为0返回空的数组
  • 参数小于0则抛出异常IllegalArgumentException
  1. 构造一个包含指定元素的列表
1
2
3
4
5
6
7
8
9
10
11
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
		// c.toArray might (incorrectly) not return Object[]
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

​ 构造指定元素的列表，当指定的元素为空时返回的是一个空的数组；如果元素不为空，那么直接得到一个指定元素的数组

​ 这里有个官方的注释，这里的作用是：如果得到的element数组类型不是Obejct类型的数组，那么就要将其转换成Object类型的数组，至于这样做的原因是：

如果没有这个Object类型转换的情况会是怎么样的，我们模拟一下

1
2
3
> List<Object> list = new ArrayList<Object>(Arrays.asList("yes", "no"));
> list.set(0, new Object());
>
注意：此处模拟指没有类型转换的情况

执行上面的代码，会调用指定元素的构造方法（推荐debug看）

  1. 当执行elementData = c.toArray(); 之后，elementData会是 String[] 类型的数组，而不是 Object[] 类型的

  2. 那么执行完该构造方法之后，上面代码就会等价于

    1
    2
    3
    >    Object[] list = new String[]{"yes","no"};
    >    list[0]=new Object();
    >
  1. 然后当你再执行list.set(0, new Object()); 的时候，就会抛出ArrayStoreException 异常了

根本原因是toArray()方法中调用的是copyOf 方法，该方法实际使用的是泛型，虽然返回的是 Object[] 类型的数组，但是实际的类型已经声明成 String[] 了

增删改查方法

System.arraycopy、Arrays.copyOf

了解这两个方法对看下面几个方法很有帮助

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
/**
 * @param src      源数组
 * @param srcPos   源数组中的起始位置
 * @param dest     目标数组
 * @param destPos  指定目标数据中的起始位置
 * @param length   要复制的数组元素的数量.
 */
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

/**
 * @param original 	要复制的数组
 * @param newLength 要返回的副本的长度
 * @param newType 	要返回的副本的类型
 */
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

add

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
//执行顺序1.
//size默认值是0
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

//2.其实是执行3和4的方法
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//3.
/**
  * 这个方法是计算list的容量的:
  *    上面add方法调用的时候会传入(size+1)到这个计算的方法中
  *    如果当前的数组是空数组,那么就比较(size+1)与默认的容量(默认是10),取较大的值返回.
  *    如果不是空数组,那么直接返回(size+1)
  */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //默认容量DEFAULT_CAPACITY是10
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

//4.
/**
  * 因为是add操作,对列表结构有改动,需要modCount++
  * 如果传入的(size+1)值大于当前数组的长度的时候,才对此数组进行扩容的操作
  */
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

//5.如果是超过当前数组长度才需要进行数组扩容的操作
/**
 * 如果新数组大小还是小于传入的容量的话,那就直接取传入的容量作为新数组的长度
 * 如果新数组的长度要比最大定义的数组长的话
 *      (最大的数组长度是Integer.MAX_VALUE-8)
 *      那么就直接使用Integer.MAX_VALUE作为数组的长度.
 * 然后就将数组的元素拷贝到一个新的数组中
 */
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //右移1位，此处得到新容量是旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

​ addAll(Collection<? extends E> c) 方法和普通add方法类似，主要使用了System.arraycopy方法来拷贝指定元素

Set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//插入到index的下标的位置,然后返回旧的值
public E set(int index, E element) {
    //判断传入的下标是否越界
    rangeCheck(index);

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

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

Get

1
2
3
4
5
public E get(int index) {
    //判断传入的下标是否越界
    rangeCheck(index);
    return elementData(index);
}

Remove

  1. 根据传入下标来移除列表中的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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);
    //更新列表的元素个数,清除最后一个元素,让GC回收
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}
  1. 根据传入的对象来删除元素
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
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循环遍历列表,根据对象的equals方法来移除对应元素
        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
}
  1. 移除包含指定元素的列表
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
public boolean removeAll(Collection<?> c) {
    //如果参数为null,那么抛出异常
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        //注意此处的complement是false
        //所以就是将elementData中不存在c中的元素留下
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        //这里的判断的原因是因为 contains 方法可能会抛出异常
        //如果抛出异常的情况下,就需要对 elementData 进行处理
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        //这里很简单,清除元素,修改 modCount 的值,然后返回true
        if (w != size) {
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

ArrayList的迭代器

1
2
3
public Iterator<E> iterator() {
    return new Itr();
}

ArrayList使用的迭代器是其内部类Itr

其内部类还有ListItr也是迭代器，只是这个迭代器可以在任意方向遍历列表，即可以向前/向后遍历。可以通过public ListIterator<E> listIterator()方法得到该迭代器

此处专注于迭代器Itr，先来查看该类的属性

  • int cursor ：要返回的下一个元素的索引
  • int lastRet = -1：返回的最后一个元素的索引，如果没有返回-1
  • int expectedModCount = modCount：结构修改次数
  1. 遍历元素的方法

在遍历元素前列表都会比较结构修改次数，如果结构修改次数不对应，那么会抛出ConcurrentModificationException异常；所以在多线程对同个列表进行迭代和增删操作的时候，很大可能会抛出异常

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//是否还有下一个可遍历的元素
public boolean hasNext() {
    return cursor != size;
}

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();
    //游标+1
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}
//在获取元素之前，需要先判断列表结构是否被修改过
final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}
  1. 移除元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void remove() {
    //这个地方就是为什么需要先执行 next 方法后才能调用 remove 方法的原因
    if (lastRet < 0)
        throw new IllegalStateException();
    //在移除元素之前，需要先判断列表结构是否被修改过
    checkForComodification();

    try {
        //调用arrayList的remove方法
        ArrayList.this.remove(lastRet);
        //重置一下游标,因为 next 操作里面将游标+1了
        cursor = lastRet;
        lastRet = -1;
        //更新结构修改次数，上面调用remove方法导致modCount增加了
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

ArrayList的遍历方式及问题

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
/**
  * List的遍历方式
  */
public void cycleList() {
    Integer[] ints = {1,2,3,4,5,6,7,8,9};
    // Arrays.asList(ints) 将数组转成List
    List<Integer> lists = Arrays.asList(ints);
    /**
      * 1.for循环遍历
      *
      * foreach循环(增强for循环)
      */
    for (int i = 0;i < lists.size();i++) {
        System.out.println(lists.get(i));
    }
    for (Integer i : lists) {
        System.out.println(i);
    }


    /**
      * 2.迭代器遍历
      */
    Iterator<Integer> iterator = lists.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }

    /**
      * 3.JDK8的stream流方式
      */
    lists.stream().forEach(System.out::println);
}

注意：

for循环遍历元素的时候，如果需要在for循环中删除元素，此时需要注意：

  • 使用foreach（即增强for循环）的话会有下标越界问题
  • for循环如果长度length是每次判断都重新获取的话是没有问题的
  • for循环如果是事先定义好长度length的话会发生下标越界问题

ArrayList元素去重

遍历列表去重

实现思路：

  1. 定义（new）一个新的List集合
  2. 遍历原集合中的每一个元素，然后判断新集合中是否包含了该元素
    • 包含就不添加到新集合
    • 不包含则加到新集合中
  3. 然后返回新的集合得到去重后的List

自定义对象去重

实现思路：跟遍历去重方式思路基本上一致，只是对于对象的遍历判断，是需要重写equals和hasCode方法来比较对象是否重复

JDK8的流方式去重

1
list.stream().distinct().forEach(System.out::println);
注意： 如果列表中是对象的话，一定要重写对象的equals() 和hasCode() 方法来定义对象是否重复的规则



### SubList方法的坑

SubList方法能够返回指定下标区间的父List的视图、视图、视图

1
2
3
4
5
6
7
8
9
10
11
12
13
//不包含toIndex下标的元素，即左闭右开
public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}
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;
}


要注意的地方就是：调用这个方法并不是返回一个全新的列表，而是返回一个视图。所以在操作这个方法得到的视图会影响原列表的内容。简单来说就是subList后得到的列表跟原列表是同一个对象



## LinkedList

### 小结

- LinkedList底层的实现是链表（双向链表），可以允许元素为null值，LinkedList是有序集合
- 增加和删除的时候只需要修改节点上的指针即可，效率比较高
- 查找和修改的时候就只能从链表的头出发一直往下遍历找到该目标元素的节点才能进行操作，效率很低
- LinkedList内部查询的时候使用的size >> 1 的方式（即折半法查找）来查找index，从而提高查询的效率
- LinkedList 集合插入元素的位置影响 LinkedList 集合插入的效率，插入位置越靠前或者越靠后，效率越高；位置越中间效率低

大致结构

  1. transient Node<E> first 存放头结点
  2. transient Node<E> last 存放尾节点
  3. modCount：fail-fast机制
  4. Node节点；LinkedList内部使用了Node类的存放元素的，新增元素的时候，会将元素包装成Node节点来进行操作
1
2
3
4
5
6
7
8
9
10
11
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. 无参构造（真无参。。）
1
2
public LinkedList() {
}
  1. 指定元素列表的构造器
1
2
3
4
5
//调用addAll方法，这个下面详说
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

增删改查方法

add

LinkedList的增加方法的核心是linkBefore(E e, Node<E> succ)、linkFirst(E e)、linkLast(E e)和node(int index)

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
//添加元素到链表末尾
//将元素包装成Node节点,然后就是链表的操作了
//	如果尾节点是空的,那么将该节点作为头和尾节点
//	如果尾节点非空,那么将该节点作为尾节点,并且加入到链表中
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}
//添加元素到链表头
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
//链表操作,将 e 插入到 succ 前面
void linkBefore(E e, Node<E> succ) {
    // succ 不能为null
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        //即succ是头节点的情况
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}
/**
 * 采用折半法得到index所在的位置(左/右区间)
 * 然后采用for循环遍历的方式得到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. add(E e)
1
2
3
4
5
public boolean add(E e) {
    //插入链表的末尾
    linkLast(e);
    return true;
}
  1. add(int index, E element)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void add(int index, E element) {
    //检查下标是否越界
    checkPositionIndex(index);
	
    if (index == size)
        //添加到链表最后,即调用上面的add(E e)方法
        linkLast(element);
    else
        //插入node(index)节点之前
        linkBefore(element, node(index));
}
//检查下标是否越界和index是否小于0
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}
  1. addAll方法，带参构造函数中也调用此方法
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
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
    //检查下标是否越界
    checkPositionIndex(index);
	//得到指定插入的元素
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;
	//获取插入位置的前驱和后继节点
    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }
	//for循环插入指定元素,并且设置好上面的前驱和后继节点
    for (Object o : a) {
        E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }
    size += numNew;
    modCount++;
    return true;
}

Get

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
//返回头节点元素内容
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;
}
//获取指定下标的元素
public E get(int index) {
    checkElementIndex(index);
    //折半for循环查找指定下标的元素
    return node(index).item;
}
//检查下标是否越界和index是否小于0
private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

Remove

LinkedList的删除方法的核心是unlink(Node<E> x)、unlinkFirst(Node<E> f)和unlinkLast(Node<E> l)

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
//要求参数 x 不能为null
E unlink(Node<E> x) {
    //得到需要删除节点的内容、前驱节点和后继节点
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
	
    if (prev == null) {
        //该节点是头结点的情况
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        //该节点是尾节点的情况
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;
    size--;
    modCount++;
    return element;
}

private E unlinkFirst(Node<E> f) {
    // 要求f是头节点并且不为null
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        //链表元素只有一个的情况
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

private E unlinkLast(Node<E> l) {
    // 要求l是尾节点并且不为null
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        //链表元素只有一个的情况
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}
  1. remove()移除第一个节点，即当前头节点
  2. remove(int index)移除下标是index的节点，先检查下标是否越界，再利用node(int index)方法得到节点，最后用unlink(Node<E> x)移除
  3. removeFirst()和removeLast()方法。根据名称可知作用，如果头结点/尾节点为null的情况，即链表为空的情况会抛出NoSuchElementException，然后各自调用unlinkFirst和unlinkLast删除节点
  4. remove(Object o)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//删除指定元素的节点，利用for循环便利链表，找到第一个配对的元素删除
//注意：如果链表有多个相同的元素，该方法只会删除第一个
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

Set

1
2
3
4
5
6
7
8
9
public E set(int index, E element) {
    //检查下标是否越界或者index是否小于0
    checkElementIndex(index);
    //找到index下标的元素,更新该item内容后返回旧值
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

pop、poll、peek、push、offer

  1. peek获取头结点；如果链表为空则返回null
  2. pop弹出头结点，头结点会被删除。如果链表为空，那么抛出NoSuchElementException
  3. poll弹出头结点，头结点会被删除。如果链表为空则返回null
  4. push插入元素作为头结点
  5. offer插入节点到链表末尾，相当于入队操作

peek和pop方法的区别是：peek方法和pop方法都是返回头节点的元素，但是peek方法不会删除头结点只返回null，而pop方法会删除头节点（相当于出栈）

ArrayList和LinkedList的区别

底层实现和线程安全问题

  • ArrayList
    • 底层数据结构是数组。线程不安全
  • LinkedList
    • 底层数据结构是链表。线程不安全
  • Vector
    • 底层数据结构是数组。线程安全（方法都加上了synchronized同步锁）

增删改查方面

总体来说：

  • ArrayList 查询和修改要比 LinkedList 快
  • LinkedList 增加和删除要比 ArrayList 快
注意：上面是总体而已，某些情况下不成立
  1. 如果删除元素是删除末尾元素的情况下，ArrayList 要比 LinkedList 快，因为 LinkedList 需要操作前后指针
  2. 如果删除的是中间的位置的元素，还是 ArrayList 快，因为 LinkedList 的折半查找法分别是从 头/尾 往中间找元素的，所以索引越靠近中间，LinkedList 的性能就越差
  3. 如果增加的元素一直都是在列表的最后增加， 那么 ArrayList 会比 LinkedList 快；此时的扩容操作占整体时间是很少的，而 LinkedList 还需要新建对象并且操作链表的前驱和后继节点

CopyOnWriteArrayList

​ CopyOnWriteArrayList是JUC包提供的线程安全的ArrayList，底层通过复制数组的方式来实现；CopyOnWriteArrayList在迭代器遍历的使用不会抛出ConcurrentModificationException异常（即没有快速失败机制），并且迭代器遍历的时候就不用额外加锁

​ copy-on-write是指写时复制；如果有多个调用者同时请求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变

优点是如果调用者没有修改该资源，就不会有副本（private copy）被建立，因此多个调用者只是读取操作时可以共享同一份资源

大致结构

  1. final transient ReentrantLock lock = new ReentrantLock() 该列表通过 ReentrantLock 来实现加锁操作
  2. private transient volatile Object[] array CowArrayList用来存储数据的数组

对数组的修改操作

add

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    //加锁操作
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        //复制一个新的数组，新增操作在新数组上完成
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        //将新数组设置到 array 上
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

CowArrayList通过复制一个新数组，并且增加操作在新数组上完成，最后将array指向到新数组中；跟ArrayList的区别就是：

  • CowArrayList有加锁操作
  • CowArrayList新增的操作在复制好的新数组上完成，而ArrayList是在原数组上完成

CowArrayList的set()、remove()操作都类似add()操作，都是在新数组上完成操作后将array指向新数组

剖析迭代器

​ 因为CopyOnWriteArrayList在迭代器遍历的使用不会抛出ConcurrentModificationException异常，并且迭代器遍历的时候就不用额外加锁；这个原因就在于CopyOnWriteArrayList在使用迭代器的时候，保存了一份原数组的副本

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
static final class COWIterator<E> implements ListIterator<E> {
    //原数组的副本
    private final Object[] snapshot;
    //游标
    private int cursor;
	//CopyOnWriteArrayList调用 iterator() 执行的构造函数
    private COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }
    public boolean hasNext() {
        return cursor < snapshot.length;
    }
    public boolean hasPrevious() {
        return cursor > 0;
    }

    public E next() {
        if (! hasNext())
            throw new NoSuchElementException();
        return (E) snapshot[cursor++];
    }
    public E previous() {
        if (! hasPrevious())
            throw new NoSuchElementException();
        return (E) snapshot[--cursor];
    }
    public int nextIndex() {
        return cursor;
    }
    public int previousIndex() {
        return cursor-1;
    }
	//CopyOnWriteArrayList的迭代器不支持一下方法
    public void remove() {
        throw new UnsupportedOperationException();
    }
    public void set(E e) {
        throw new UnsupportedOperationException();
    }
    public void add(E e) {
        throw new UnsupportedOperationException();
    }
}

显而易见：

​ 在调用迭代器的方法时，迭代器会保存一份原数组的副本，即snapshot。该迭代器的所有操作都是对原数组进行操作，因此也就没有线程间的读写问题了，也就不需要快速失败机制和加锁操作了，所以CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性

CopyOnWriteArrayList小结

  • 如果 CopyOnWriteArrayList 需要经常增删改列表的数据，经常要执行add()、set()、remove()的话，那是比较耗费内存的（因为都需要复制一个新数组进行增删改）
  • 数据一致性：CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性
  • 相对于ArrayList和Vector来说，遍历数组时不会受其他线程对数组操作而造成影响（读的是原数组的副本）

Set 对应的是 CopyOnWriteArraySet