AbstractList

类关系图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
 继承自父类AbstractCollection<E>
        两个抽象方法，子类必须实现
        public abstract Iterator<E> iterator();
        public abstract int size();
 
 实现了List<E>接口
    public interface List<E> extends Collection<E>
        int size();
        boolean isEmpty();
        boolean contains(Object o);
        Object[] toArray();
        void add(int index, E element);
        E remove(int index);
        int indexOf(Object o);
        ...
*/
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

构造器

1
2
protected AbstractCollection() {
}

方法

  • 提供了抽象方法 abstract public E get(int index); 子类必须实现
  • 默认不支持的 add(), set(),remove(),子类要想实现元素的修改必须重写这些方法
    1
    2
    3
    4
    5
    6
    7
    public E set(int index, E element) {throw new UnsupportedOperationException();}    

    public void add(int index, E element) {
        throw new UnsupportedOperationException();
    }

    public E remove(int index) {throw new UnsupportedOperationException();}
  • 全部/局部删除
    public void clear() {removeRange(0, size());}
    protected void removeRange(int fromIndex, int toIndex)

内部类

1
2
3
4
5
6
7
private class Itr implements Iterator<E>

private class ListItr extends Itr implements ListIterator<E>

class SubList<E> extends AbstractList<E>

class RandomAccessSubList<E> extends SubList<E> implements RandomAccess

ArrayList

类的关系图

1
2
3
4
5
6
7
/*
    List<E>接口：提供了一些基本的增、删、改、查方法
    RandomAccess接口：说明改方法支持随机访问，get、set等方法时间复杂度为 O(1)
    Serializable接口：可序列化接口
*/
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

成员变量

==底层是一个Object数组==

1
2
3
4
5
6
7
8
9
10
11
12
13
private static final long serialVersionUID = 8683452581122892189L;

//初始默认容量
private static final int DEFAULT_CAPACITY = 10;

//容量为0的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//容量为默认容量的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient Object[] elementData;
//所含元素的数量
private int size;

构造器

方法

  • 修剪容量
    1
    2
    3
    4
    5
    6
    7
    8
    9
    public void trimToSize() {
        //结构性修改数组的次数加一
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }
  • 扩容
    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
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
        }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        //新的容量是旧容量的1.5倍
        //向右位移运算，提升处理速度
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //仍要小于最少需要的容量，则 新容量=最少需要的容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
  • 判断是否包含元素o 
    1
    2
    //若不包含该元素，indexOf会返回-1
    public boolean contains(Object o) {return indexOf(o) >= 0;}

LinkedList

类关系图

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

成员变量

1
2
3
4
5
transient int size = 0;

transient Node<E> first;

transient Node<E> last;

构造器

方法

  • 连接的相关方法
    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
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    //将元素e连接到链表头
    private void linkFirst(E e) {
        final Node<E> f = first;    //设置变量存储原来的链表头
        final Node<E> newNode = new Node<>(null, e, f); //根据元素e新建节点
        first = newNode;    //将新建的节点设为链表的头
        if (f == null)  //如果原来的链表头是空的，则将新的节点也设成链表的尾部
            last = newNode;
        else    //否则，连接旧头和新头
            f.prev = newNode;
        size++;
        modCount++;
    }

    //将元素e连接到链表尾，与linkFirst同理
    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++;
    }

    /*将节点e连接到某个非空节点前
      思路：设置新的节点存储目标节点的前一个节点，然后将目标节点的前一个节点的next指向元素e的节点，
            succ.prev = newNode
            如果目标节点的前一个节点为空，则将头节点设置为 e节点
    */
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

    //相当于删除第一个节点
    private E unlinkFirst(Node<E> f) {
        // assert f == first && 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) {
        // assert l == last && 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;
    }

    //删除不为空的节点x
    //前面的值指向后面的值，后面的值指向前面的值
    E unlink(Node<E> x) {
        // assert x != null;
        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;
    }