Java 集合框架系列三：JDK 1.8 List 和 AbstractList 和 AbstractSequentialList 详解

桃扇骨 2022-12-05 00:46 204阅读 0赞

## List 继承关系 ##

![在这里插入图片描述][20200908142348812.png_pic_center]  
List 是在 JDK 1.2 提供的接口，继承了 Collection 接口，List 代表有序集合，List 可以精确控制列表中每个元素的插入位置，可以通过索引访问元素，和 Set 不同得是 List 允许插入重复的元素，而且 List 的实现类如果允许插入 null 元素，那么可以存在多个 null 元素。List 在 Collection 接口的基础上添加了一系列针对其特性的方法，如通过索引操作元素。

有些 List 的实现可能对包含的元素有限制。例如有些实现禁止 null 元素，有些实现对其元素的类型有限制。尝试添加不合格的元素会引发 NullPointerException 或 ClassCastException 异常。尝试查询不合格元素是否在 List 中存在可能会引发异常，也可能只是返回 false，具体取决于实现。

## List API ##

下面只列举了 List 新增的方法，继承自 Collection 的方法可以看我的 Collection 篇。

public interface List<E> extends Collection<E> { 
        //在指定位置，将指定的集合插入到当前的集合中 将当前位于该位置的元素（如果有）和后续元素向右移动（增加其索引）
        // UnsupportedOperationException 不支持此操作
        // ClassCastException c 中的元素类型与当前 List 中的元素类型不匹配
        // NullPointerException 指定的 c 为 null 或者 c 中包含 null 元素且当前 List 不允许 null
    	// IllegalArgumentException c 中的元素某些特征阻止将其添加到当前 List
    	// IndexOutOfBoundsException 指定的 index 越界 
        boolean addAll(int index, Collection<? extends E> c);
    
        //这是一个默认实现的方法，会通过 Iterator 对每个元素进行指定的操作
        default void replaceAll(UnaryOperator<E> operator) { 
            Objects.requireNonNull(operator);
            final ListIterator<E> li = this.listIterator();
            while (li.hasNext()) { 
            	// 对当前元素进行处理并重新 set
                li.set(operator.apply(li.next()));
            }
        }
    
        //排序，依据指定的规则对当前集合进行排序，可以看到，排序是通过Arrays这个工具类完成的
        default void sort(Comparator<? super E> c) { 
            Object[] a = this.toArray();
            // 对数组自然排序
            Arrays.sort(a, (Comparator) c);
            ListIterator<E> i = this.listIterator();
            for (Object e : a) { 
                i.next();
                // set 排序后的元素
                i.set((E) e);
            }
        }
    
        //获取指定位置的元素
        E get(int index);
    
        //修改指定位置元素的值
        E set(int index, E element);
    
        //将指定元素添加到指定的位置
        void add(int index, E element);
    
        //将指定位置的元素移除
        E remove(int index);
    
        //返回一个元素在集合中首次出现的位置
        int indexOf(Object o);
    
        //返回一个元素在集合中最后一次出现的位置
        int lastIndexOf(Object o);
    
        //返回一个 ListIterator，默认是 List 开头的位置
        ListIterator<E> listIterator();
    
        //从指定位置开始，返回一个ListIterator 可以选择向前或者向后迭代
        ListIterator<E> listIterator(int index);
    
        //返回一个子集合[fromIndex, toIndex)，非结构性的修改返回值会反映到原表，反之亦然。
        //如果原表进行了结构修改，则返回的子列表可能发生不可预料的事情
        List<E> subList(int fromIndex, int toIndex);
        
    }

## AbstractList 继承关系 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center]  
AbstractList 是 JDK 1.2 提供的抽象类，直接继承了 AbstractCollection 并实现了 List 接口。与 AbstractCollection 一样，是对 List 的通用实现。AbstractList 适合于底层支持随机访问的数据结构（如数组），针对顺序存储的数据结构（如链表），应该优先考率 AbstractSequentialList 类。

如果希望实现一个不可修改的 List ，需要重写 AbstractList 的 get(int) 方法和 List 的 size() 方法。

// AbstractList 唯一的抽象方法
    	abstract public E get(int index);

如果希望实现一个可修改的 List，需要重写 AbstractList 的 set(int, E) 方法。

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

如果希望实现一个支持动态调整大小的 List，需要重写 AbstractList 的 add(int, E) 和 remove(int) 方法。

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

AbstractList 没有重写 AbstractCollection 的 add、set、remove 方法。

public boolean add(E e) { 
            add(size(), e);
            return true;
        }
    	public void add(int index, E element) { 
            throw new UnsupportedOperationException();
        }

## AbstractList API ##

看一下 AbstractList 中的一些常用方法。

// 内部调用 add(int,E) 方法
    	public boolean add(E e) { 
            add(size(), e);
            return true;
        }
    	// 返回指定元素第一次出现的索引
    	public int indexOf(Object o) { 
    		// 使用 ListIterator 迭代
            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();
            }
            // 没有匹配返回 -1
            return -1;
        }
        // 与 indexOf 的区别就是从后往前迭代
    	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;
        }
        // 清空 List
    	public void clear() { 
            removeRange(0, size());
        }
        // 通过迭代器的 remove 方法删除
    	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();
            }
        }
    	// 内部调了 add(int,E) 方法 
    	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;
        }
        
        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();
                //这里用到了元素的 equals 方法所以应该重写元素对象的 equals方法
                if (!(o1==null ? o2==null : o1.equals(o2)))
                    return false;
            }
            return !(e1.hasNext() || e2.hasNext());
        }
        
        public int hashCode() { 
            int hashCode = 1;
            for (E e : this)
            	//这里用到了元素的 hashCode 方法所以应该重写元素对象的 hashCode 方法
                hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
            return hashCode;
        }

通过分析，发现 indexOf()、lastIndexOf()、clear() 方法都是通过 AbstractList 内部定义的 ListItr 迭代器实现的。在 AbstractList 内部提供了两个迭代器实现，Itr 和其子类 ListItr。

Itr 实现了 Iterator 接口，重写了 next() 和 remove() 方法

// 每次对 List 进行结构修改则 + 1，结构修改包括添加和删除元素操作
    	protected transient int modCount = 0;
    	
    	private class Itr implements Iterator<E> { 
            /** * 游标，是调用 next 方法时元素对应的索引，从 0 开始 */
            int cursor = 0;
    
            /** * 最近调用 next 或 previous 时返回的元素的索引。如果此元素被删除，则重置为 -1。 */
            int lastRet = -1;
    
            /** * 迭代器期望的 modCount，如果此值与 modCount 不想等说明发生了并发结构修改 * 改查都不涉及长度的变化，而增删就涉及到动态调整大小的问题 */
            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() { 
                // 还没有调用 next() 方法就调用此方法就抛出 IllegalStateException
                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();
            }
        }

modCount 是 AbstractList 的一个属性，AbstractList 的子类 ArrayList 中的方法 add、remove、set 中都会对 modCount 执行 ++ 操作，每当返回迭代器时就会记录当前的 modCount 给 expectedModCount 属性，如果在迭代期间并发修改了集合元素，那么 modCount 就不会和 expectedModCount 相等，迭代器就会抛出ConcurrentModificationException，也就是 fail-fast 策略。

ListItr 是 Itr 的子类并且实现了 ListIterator 接口，在 Itr 的基础上增强了对元素的操作：指定索引的赋值，以及向前读取。也就是 Itr 是对 Iterator 的实现而 ListItr 是对 ListIterator 的实现，所以 ListItr 功能更强大。

private class ListItr extends Itr implements ListIterator<E> { 
            // 指定游标的位置
            ListItr(int index) { 
                cursor = index;
            }
    		// 游标不是 0 说明存在前面的元素
            public boolean hasPrevious() { 
                return cursor != 0;
            }
    
            public E previous() { 
                checkForComodification();
                try { 
                    int i = cursor - 1;
                    E previous = get(i);
                    // 先把 cursor 赋给 lastRet，再把 i 赋给 cursor
                    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();
                }
            }
        }

AbstractList 类中提供了对应的方法可以返回 Itr 和 ListItr 迭代器对象。

public Iterator<E> iterator() { 
            return new Itr();
        }
    
        public ListIterator<E> listIterator() { 
            return listIterator(0);
        }
    
        public ListIterator<E> listIterator(final int index) { 
            rangeCheckForAdd(index);
    
            return new ListItr(index);
        }
    
    	private void rangeCheckForAdd(int index) { 
            if (index < 0 || index > size())
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

AbstractList 提供了两个子类，可用于切分集合，这两个类是 **SubList** 和 **RandomAccessSubList** 。

**SubList** 并不是新建了一个集合，只是持有了当前集合的引用，然后控制一下用户可以操作的范围，所以在接口定义时就说明了对其更改会直接反应到原集合中。`SubList`定义在`AbstractList`内部，并且是`AbstractList`的子类。在`AbstractList`的基础上增加了对可选范围的控制。

SubList 的方法实现都是调用了 AbstractList 的方法实现。

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;
        }
    }

RandomAccessSubList 是 SubList 的子类，内部实现直接沿用父类，只是实现了 RandomAccess 接口，RandomAccess 是一个标识接口并没有定义方法。它的作用是用于标识某个类是否支持 **随机访问**（相对比“按顺序访问”）。支持随机访问的类可以使用更加高效的算法。

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);
        }
    }

## AbstractSequentialList 继承关系 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center 1]  
AbstractSequentialList 是 JDK 1.2 提供的抽象类，它继承了 AbstractList， Sequential 是`顺序`的意思。AbstractSequentialList 是对 List 支持顺序访问的通用实现。对于随机访问数据建议使用上面介绍的 AbstractList。想要实现一个支持按顺序访问的 List 只需要继承这个抽象类，重写 listIterator 和 size 方法即可。

如果希望实现一个不可修改的列表，只需要实现迭代器的 hasNext、next、hasPrevious、previous 和 index 方法。

如果希望实现一个可修改的列表，还需要另外实现迭代器的 set 方法。对于容量可变的 List 实现，还需要另外重写迭代器的 remove 和 add 方法。

## AbstractSequentialList API ##

接下来看一下 AbstractSequentialList 提供了哪些 API 来支持顺序访问。

public abstract class AbstractSequentialList<E> extends AbstractList<E> { 
    	// 供子类调用
        protected AbstractSequentialList() { 
        }
    
        /** * 返回指定索引的元素 * 此实现通过迭代器的 ListIterator.next 方法获取指定索引的元素 */
        public E get(int index) { 
            try { 
                return listIterator(index).next();
            } catch (NoSuchElementException exc) { 
                throw new IndexOutOfBoundsException("Index: "+index);
            }
        }
    
        /** * 替换指定索引的元素，内部是通过 ListIterator.next 和 ListIterator.set * 方法实现，对于没有实现 ListIterator.set 方法的实现抛出 UnsupportedOperationException */
        public E set(int index, E element) { 
            try { 
                ListIterator<E> e = listIterator(index);
                E oldVal = e.next();
                e.set(element);
                return oldVal;
            } catch (NoSuchElementException exc) { 
                throw new IndexOutOfBoundsException("Index: "+index);
            }
        }
    
        /** * 在列表中指定的位置插入元素。将位于该位置的元素（如果有）和后续元素向右移动。 * 如果 listirator 没有实现 add 方法，将抛出一个 UnsupportedOperationException。 */
        public void add(int index, E element) { 
            try { 
                listIterator(index).add(element);
            } catch (NoSuchElementException exc) { 
                throw new IndexOutOfBoundsException("Index: "+index);
            }
        }
    
        /** * 删除指定索引的元素，并将后续元素向左移动一个位置，返回被删除的元素 * 通过 ListIterator.remove 实现删除操作，如果 ListIterator 没有实现 * remove 操作则抛出 UnsupportedOperationException */
        public E remove(int index) { 
            try { 
                ListIterator<E> e = listIterator(index);
                E outCast = e.next();
                e.remove();
                return outCast;
            } catch (NoSuchElementException exc) { 
                throw new IndexOutOfBoundsException("Index: "+index);
            }
        }
        
        // Bulk Operations
        
        /** * 添加指定集合的所有元素到当前集合中 * 依然是通过 listIterator 操作 */
        public boolean addAll(int index, Collection<? extends E> c) { 
            try { 
                boolean modified = false;
                ListIterator<E> e1 = listIterator(index);
                Iterator<? extends E> e2 = c.iterator();
                while (e2.hasNext()) { 
                    e1.add(e2.next());
                    modified = true;
                }
                return modified;
            } catch (NoSuchElementException exc) { 
                throw new IndexOutOfBoundsException("Index: "+index);
            }
        }
    
        // Iterators
        
        public Iterator<E> iterator() { 
            return listIterator();
        }
        // 将此方法抽象，以期有更符合场景的实现
        public abstract ListIterator<E> listIterator(int index);
    }

[20200908142348812.png_pic_center]: /images/20221123/7971a093a91a49449fac22ff72a75634.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/c0a7778647224b93be9180493421ba30.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/88d4c5f1a67c405da001acfa5ad01c28.png