close

Mr.Muzi

一只很安静的monkey

Java Collection 02 - AbstractList

字数统计: 4.8k 阅读时长: 21 mins • 分类: 源码阅读 • 标签: JDK 1.7, Java集合

  关于 java.util.AbstractList<E> 的部分笔记，AbstractList是List的默认最小化实现。在具体的使用场景中，由继承AbstractList的具体实现类完成数据的存储和操作需求。本文演示代码段的执行环境基于JDK版本1.7。

概述

  AbstractList是List接口的最小程度的实现。之所以说是最小程度，是因为AbstractList中大部分已经实现的方法基本上都是只返回了异常信息而没有做任何有效的处理操作。List有两个抽象实现，一个是AbstractList，另一个是AbstractSequentialList。AbstractList实现了一种随机访问存储数据的方案，类似于数组那样,所以其具有元素访问速度快的特点，但是由于其底层实现采用的数组的方式，所以在插入元素时会因为需要移动元素分配空间而导致元素插入速度相对较慢。而AbstractSequentialList则实现了一种顺序访问存储数据的方案，其继承类便是LinkedList。

  对于AbstractList的子类来说，如果想要处理的是不可修改的list集合，那么只需要实现AbstractList中的get(int index)和int size()方法就足够了。如果要处理的可修改list集合，那么就需要额外实现set(int index, E element)。如果想要处理一个可变长度的list集合，那么还需要实现add(int index, E element)和remove(int index)方法。

  除此之外，AbstractList自身实现了iterator和list iterator迭代器的功能。而且，像get(int index)、set(int index, E element)、add(int index, E element)和remove(int index)方法都可以通过随机访问的对集合元素进行操作处理。

 

继承关系

1
2
3
4
// AbstractList<E>
--java.lang.Object
  --java.util.AbstractCollection<E>
    --java.util.AbstractList<E>

 

实现接口

类名 实现接口
AbstractList<E> Iterable<E>, Collection<E>, List<E>

 

AbstractList

Constructor Summary

protected AbstractList()

1
2
protected AbstractList() {
}

  默认构造函数。采用protected修饰的原因是因为AbstractList不直接用于集合的初始化操作，而是在使用真正可用的list集合处理类时提供一些基础准备工作。所以这个方法不应该暴露到外界去，所以不能用public修饰。同样的原因，因为AbstractList不涉及到单例模式的设计，所以也不会是private，这样其子类也没办法继承到父类的无参构造方法。所以综上考虑，protected是最理想的选择。

部分方法

public boolean add(E e)

1
2
3
4
public boolean add(E e) {
    add(size(), e);
    return true;
}

  在集合尾部加入新的元素e。实际调用的是add(int index, E element)方法。该方法可能会限制e的类型，不满足条件的e可能无法加入到集合中。需要注意的是AbstractList中的add(int index, E element)方法需要被子类重写其实现，否则会抛出UnsupportedOperationException异常。

public void add(int index, E element)

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

  AbstractList中的add(int index, E element)方法直接抛出UnsupportedOperationException异常，需要在子类中重写实现过程。

abstract public E get(int index)

1
abstract public E get(int index);

  返回index指定的位置的元素。AbstractList中该方法被声明为抽象方法。需要子类重写实现过程。

public E set(int index, E element)

1
2
3
public E set(int index, E element) {
    throw new UnsupportedOperationException();
}

  替换list集合中index位置的元素为element。AbstractList中的set(int index, E element)方法直接抛出UnsupportedOperationException异常，需要在子类中重写实现过程。

public E remove(int index)

1
2
3
public E remove(int index) {
    throw new UnsupportedOperationException();
}

  删除index位置的元素并返回该元素。删除执行完成后index位置之后的所有元素都会向前移动一个位置。AbstractList中的remove(int index)方法直接抛出UnsupportedOperationException异常，需要在子类中重写实现过程。

public int indexOf(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
public int indexOf(Object o) {
    ListIterator<E> it = listIterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                return it.previousIndex();
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return it.previousIndex();
    }
    return -1;
}

  返回元素o在list集合中第一次出现的位置，如果list集合中尚未存储元素o，那么返回-1。如果入参元素o为null，那么就寻找list集合中第一个null元素存储的位置，否则，根据o的equals()方法寻找集合中该元素第一次出现的位置。由于在调用next()方法获取元素时，内部的cursor会自动移动到下一个位置，所以需要通过调用previousIndex()获取匹配元素的准备下标位置，方法内部会计算并返回cursor - 1的结果。

public int lastIndexOf(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
public int lastIndexOf(Object o) {
    ListIterator<E> it = listIterator(size());
    if (o==null) {
        while (it.hasPrevious())
            if (it.previous()==null)
                return it.nextIndex();
    } else {
        while (it.hasPrevious())
            if (o.equals(it.previous()))
                return it.nextIndex();
    }
    return -1;
}

  返回元素o在list集合中最后一次出现的位置，如果list集合中尚未存储元素o，那么返回-1。如果入参元素o为null，那么就寻找list集合中最后一个null元素存储的位置，否则，根据o的equals()方法寻找集合中该元素最后一次出现的位置。

public void clear()

1
2
3
public void clear() {
    removeRange(0, size());
}

  移除集合中含有的所有元素。实际调用的是removeRange(int fromIndex, int toIndex)方法，因为需要在子类中实现remove(int index)或者removeRange(int fromIndex, int toIndex)，所以直接调用AbstractList的clear()方法会抛出UnsupportedOperationException异常。removeRange(int fromIndex, int toIndex)的处理逻辑如下：

1
2
3
4
5
6
7
protected void removeRange(int fromIndex, int toIndex) {
    ListIterator<E> it = listIterator(fromIndex);
    for (int i=0, n=toIndex-fromIndex; i<n; i++) {
        it.next();
        it.remove();
    }
}

  移除list集合中从fromIndex 到 toIndex的所有元素。删除的元素中包含fromIndex位置的元素，但是不包括toIndex位置的元素。方法执行完成后会将toIndex之后的元素前移填补空缺位置。由于第5行代码调用的remove()方法底层实际调用的是remove(int index)方法，而该方法在AbstractList中直接抛出UnsupportedOperationException异常，所以子类需要重写removeRange(int fromIndex, int toIndex)或者remove(int index)。

public boolean addAll(int index, Collection<? extends E> c)

1
2
3
4
5
6
7
8
9
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);
    boolean modified = false;
    for (E e : c) {
        add(index++, e);
        modified = true;
    }
    return modified;
}

  将c中的所有元素加入到list集合中自index起的位置上，自index位置起的元素会后移以便为c中的元素提供空间。第2行代码会检查当前list集合的剩余空间情况。之后遍历c中的每个元素，调用add(int index, E element)方法将其保存到list集合中。AbstractList中的add(int index, E element)方法由于需要子类实现，所以会直接抛出UnsupportedOperationException异常。

1
2
3
4
5
6
7
8
private void rangeCheckForAdd(int index) {
    if (index < 0 || index > size())
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private String outOfBoundsMsg(int index) {
    return "Index: "+index+", Size: "+size();
}

public Iterator<E> iterator()

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

  返回一个可以遍历list集合的迭代器对象。该迭代器对象Itr是AbstractList中的一个私有类，其相关实现如下：

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
private class Itr implements Iterator<E> {
    /**
     * Index of element to be returned by subsequent call to next.
     */
    int cursor = 0;

    /**
     * Index of element returned by most recent call to next or
     * previous.  Reset to -1 if this element is deleted by a call
     * to remove.
     */
    int lastRet = -1;

    /**
     * The modCount value that the iterator believes that the backing
     * List should have.  If this expectation is violated, the iterator
     * has detected concurrent modification.
     */
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor != size();
    }

    public E next() {
        checkForComodification();
        try {
            int i = cursor;
            E next = get(i);
            lastRet = i;
            cursor = i + 1;
            return next;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            AbstractList.this.remove(lastRet);
            if (lastRet < cursor)
                cursor--;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
        }
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

  Itr是一个实现了Iterator\接口的迭代器类。Itr可以实现遍历list集合中的元素，并根据条件安全的删除其中特定元素。cursor标记了通过next()方法返回下一个元素的下标值，lastRet总是比cursor慢一个节拍（用于可能的删除操作），即在通过remove方法删除元素时，系统将直接删除lastRet位置的元素。第19行代码存在的变量需要判断当前list集合是否存在被其他迭代器修改的情况。如果当前list集合被其他迭代器修改过，那么会立即抛出异常（即fail-fast）。

  第21 ~ 23 行代码当前迭代器是否遍历到list集合尾部，如果到达了尾部会返回false，防止调用next()方法时越界溢出。

  第25 ~ 37行代码返回迭代器即将遍历的下一个元素。在返回元素之前会首先判断当前list集合是否被其他迭代器修改过，如果修改过，那么直接抛出异常。如果没有被其他迭代器修改过，通过AbstractList中的get(int index)方法获取一个元素。之后更新lastRet和cursor的值，并返回获取的元素给方法调用方。

  第39 ~ 53行代码迭代器会删除最近一次调用next()方法获取的元素。如果lastRet小于0（实际上通常为-1）表示在删除之前没有调用过next()方法，这个时候是无法调用remove()方法的。还有一种情况是在调用remove()方法前刚执行了一次remove()操作，实际上这种操作是不允许的。第42行代码判断当前list集合是否被其他迭代器修改过，如果修改过，那么直接抛出异常。第45行代码通过调用AbstractList中的remove(int index)方法直接删除lastRet位置处的元素。在删除之后lastRet会被重新置为-1。同时更新expectedModCount的值。

  需要注意的是，由于下文中的ListItr继承了Itr，而ListItr是一个可以双向遍历的迭代器，且其继承了Itr的remove()方法。所以第46 ~ 47行代码对cursor的更新做了限定，只有在lastRet < cursor时（即从前向后遍历并执行删除操作）才可以更新cursor的值。

  第55 ~ 58行代码则判断当前list集合的最近一次修改是否是由当前迭代器执行的，如果不是，则会抛出异常。

public ListIterator<E> listIterator()

1
2
3
4
5
6
7
8
9
public ListIterator<E> listIterator() {
    return listIterator(0);
}

public ListIterator<E> listIterator(final int index) {
    rangeCheckForAdd(index);

    return new ListItr(index);
}

  初始化一个list集合迭代器。其返回的迭代器对象ListItr是一个私有类，ListItr的相关实现如下：

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
private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        cursor = index;
    }

    public boolean hasPrevious() {
        return cursor != 0;
    }

    public E previous() {
        checkForComodification();
        try {
            int i = cursor - 1;
            E previous = get(i);
            lastRet = cursor = i;
            return previous;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }

    public int nextIndex() {
        return cursor;
    }

    public int previousIndex() {
        return cursor-1;
    }

    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            AbstractList.this.set(lastRet, e);
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    public void add(E e) {
        checkForComodification();

        try {
            int i = cursor;
            AbstractList.this.add(i, e);
            lastRet = -1;
            cursor = i + 1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

  ListItr是一个既实现了Iterator\接口同时又继承了Itr的迭代器类。第2 ~ 4行代码实现了一个带参数的构造函数，该方法指定了迭代器在list集合中开始迭代的起点位置。

  第6 ~ 8行代码返回当前迭代器是否可以继续返回前驱节点元素。

  第10 ~ 21行代码则返回当前节点的一个前驱节点元素。首先通过调用checkForComodification()方法判断当前list集合的最近一次修改是否是由当前迭代器执行的，如果不是，则会抛出异常。通过AbstractList中的get(int index)方法获取一个元素并返回获取的这个元素。之后更新lastRet和cursor的值。

  第23 ~ 25行代码返回后继元素的下标值。而27 ~ 29行代码则返回前驱元素的下标值。

  第31 ~ 42行代码将lastRet位置的元素替换为参数e。如果lastRet小于0，那么认为在调用set(E e)方法之前尚未调用过next()或者previous()方法，那么此时无法通过set(E e)方法实现元素替换。接着会检查当前list集合的最近一次修改是否是由当前迭代器执行的，如果不是，则会抛出异常。如果检查通过，那么调用AbstractList中的set(int index, E element)方法完成元素的替换。最后更新expectedModCount的值标记当前迭代器对list集合做出了修改。

  第44 ~ 56行代码将新的元素e加入到cursor标识的位置上。在完成当前list集合的最近一次修改是否是由当前迭代器执行的检查后，通过AbstractList中的add(int index, E element)方法完成元素的加入。操作完成后将lastRet重置为-1，同时将cursor移动到下一个位置上。最后更新expectedModCount的值完成所有操作。

  图1描述了ListIterator中关于cursor游标是如何工作的：

图 - 1
 

public List<E> subList(int fromIndex, int toIndex)

1
2
3
4
5
public List<E> subList(int fromIndex, int toIndex) {
    return (this instanceof RandomAccess ?
            new RandomAccessSubList<>(this, fromIndex, toIndex) :
            new SubList<>(this, fromIndex, toIndex));
}

  取出当前list集合中自fromIndex（包含fromIndex）起，到toIndex（不含toIndex）为止的元素集合。根据当前list集合自身的类型会返回一个RandomAccessSubList或者一个SubList。

public boolean equals(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof List))
        return false;

    ListIterator<E> e1 = listIterator();
    ListIterator e2 = ((List) o).listIterator();
    while (e1.hasNext() && e2.hasNext()) {
        E o1 = e1.next();
        Object o2 = e2.next();
        if (!(o1==null ? o2==null : o1.equals(o2)))
            return false;
    }
    return !(e1.hasNext() || e2.hasNext());
}

  判断两个list集合是否相等。如果入参o等于自身，那么返回true。如果o的类型不是list，那么返回false。如果当前list和o的集合中存在一个及以上不一致的元素，或者包含的元素个数不一致，那么返回false。

public int hashCode()

1
2
3
4
5
6
public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    return hashCode;
}

  计算list集合的散列值。

 

SubList<E>

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
class SubList<E> extends AbstractList<E> {
    private final AbstractList<E> l;
    private final int offset;
    private int size;

    // 构造函数，完成初始化操作
    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;
        this.modCount = l.modCount;
    }

    // 用element替换到子list集合中index位置处的元素，实际调用AbstractList中的set(int index, E element)方法。
    public E set(int index, E element) {
        rangeCheck(index);
        checkForComodification();
        return l.set(index+offset, element);
    }

    // 获取index位置的元素，实际调用AbstractList中的get(int index)方法。
    public E get(int index) {
        rangeCheck(index);
        checkForComodification();
        return l.get(index+offset);
    }

    // 获取子list集合的元素总数。
    public int size() {
        checkForComodification();
        return size;
    }

    // 将element加入到子list集合中index位置处，实际调用AbstractList中的add(int index, E element)方法。
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        checkForComodification();
        l.add(index+offset, element);
        this.modCount = l.modCount;
        size++;
    }

    // 移除index位置的元素，实际调用AbstractList中的remove(int index)方法。
    public E remove(int index) {
        rangeCheck(index);
        checkForComodification();
        E result = l.remove(index+offset);
        this.modCount = l.modCount;
        size--;
        return result;
    }

    // 移除自fromIndex起到toIndex为止的元素，实际调用AbstractList中的gremoveRange(int fromIndex, int toIndex)方法。
    protected void removeRange(int fromIndex, int toIndex) {
        checkForComodification();
        l.removeRange(fromIndex+offset, toIndex+offset);
        this.modCount = l.modCount;
        size -= (toIndex-fromIndex);
    }

    // 将c中元素加入到子list集合中，实际调用AbstractList中的addAll(int index, Collection<? extends E> c)。
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

    // 将c中元素加入到子list集合中自index位置起的位置离，实际调用AbstractList中的addAll(int index, Collection<? extends E> c)。
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
        int cSize = c.size();
        if (cSize==0)
            return false;

        checkForComodification();
        l.addAll(offset+index, c);
        this.modCount = l.modCount;
        size += cSize;
        return true;
    }

    // 返回一个子list集合迭代器。
    public Iterator<E> iterator() {
        return listIterator();
    }

    public ListIterator<E> listIterator(final int index) {
        checkForComodification();
        rangeCheckForAdd(index);

        return new ListIterator<E>() {
            private final ListIterator<E> i = l.listIterator(index+offset);

            public boolean hasNext() {
                return nextIndex() < size;
            }

            public E next() {
                if (hasNext())
                    return i.next();
                else
                    throw new NoSuchElementException();
            }

            public boolean hasPrevious() {
                return previousIndex() >= 0;
            }

            public E previous() {
                if (hasPrevious())
                    return i.previous();
                else
                    throw new NoSuchElementException();
            }

            public int nextIndex() {
                return i.nextIndex() - offset;
            }

            public int previousIndex() {
                return i.previousIndex() - offset;
            }

            public void remove() {
                i.remove();
                SubList.this.modCount = l.modCount;
                size--;
            }

            public void set(E e) {
                i.set(e);
            }

            public void add(E e) {
                i.add(e);
                SubList.this.modCount = l.modCount;
                size++;
            }
        };
    }

    public List<E> subList(int fromIndex, int toIndex) {
        return new SubList<>(this, fromIndex, toIndex);
    }

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

    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    private void checkForComodification() {
        if (this.modCount != l.modCount)
            throw new ConcurrentModificationException();
    }
}

 

RandomAccessSubList<E>

1
2
3
4
5
6
7
8
9
class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
    RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
        super(list, fromIndex, toIndex);
    }

    public List<E> subList(int fromIndex, int toIndex) {
        return new RandomAccessSubList<>(this, fromIndex, toIndex);
    }
}

  RandomAccessSubList继承了上文提到的SubList，同时实现了RandomAccess接口，实现了一种类似于数组的以常量时间复杂度获取元素的操作方法。在RandomAccessSubList中目前只实现了获取子集合的方法。

  鉴于RandomAccessSubList实现了RandomAccess接口，而RandomAccess本身仅仅起到了一个打标的作用，内部没有任何需要实现的方法，任何实现了RandomAccess的类都可以使用更加高效的、可以使用随机访问的算法来访问集合内部元素。在list集合同时存在随机访问和顺序访问两种方案，前者以ArrayList为代表，LinkedList则采用了顺序访问的思想来访问集合内元素。而决定采用随机访问还是顺序访问的方式访问集合内元素的依据就是当前实现类是否实现了RandomAccess接口。

 

涉及基础知识点

  1. Itr和ListItr之间的不同点：
    1. Itr只能执行向后迭代遍历，ListItr可以做双向迭代遍历；
    2. Itr基于整个list集合进行迭代遍历，其初始节点位置下标从0开始。ListItr可以从list集合中的某个特定节点开始遍历，其初始节点位置下标可以被设置为list集合中的任意一个特定节点位置；
    3. Itr简单实现了Iterator<E>接口，而ListItr则继承Itr的同时又实现了ListIterator<E>接口。

 

参考文献

  1. 千念飞羽. 源码分析-java-AbstractList-Itr和ListItr的实现 [E]

 
 
 
 

------------- End of this article, thanks! -------------
 


  版权声明：本文由N.C.Lee创作和发表，采用署名(BY)-非商业性使用(NC)-相同方式共享(SA)国际许可协议进行许可，转载请注明作者及出处。
  本文作者为 N.C.Lee
  本文标题为 Java Collection 02 - AbstractList
  本文链接为 https://marcuseddie.github.io/2018/java-Collection-AbstractList.html