您的位置: 首页  >  文章  >  03 java list 源码浅析

03 java list 源码浅析

分类: 文章 • 2025-01-15 19:20:22

三大数据结构链表、树和图，顺序表作为其中的一种，可以说是平时编程中最长使用到的。List接口是顺序表在java中的实现，它有很多子接口和实现类，平时的编程中使用起来非常方便。但是更进一步，我们有必要对其实现和原理进行理解，并和数据结构中所学比较，并应用于平时的编程中，编写出高效率的代码。

首先看下list接口的层次关系，下图由本人根据jdk的类结构简单画的：

03 java list 源码浅析

从上图可以看出，list接口有Collection接口衍生而出，那么首先了解下Collection接口。

Collection

collection 是集合框架的根，他定义的集合操作的通用行为，如添加元素、批量添加、删除、批量删除、集合大小、包含、迭代器等。它的接口定义这里不再贴，在关系上，Collection是继承于Iterable接口的，其只有一个方法：

[java] view plain copy
  1. public interface Iterable<T> {  
  2.    
  3.     /** 
  4.      * Returns an {@link Iterator} for the elements in this object. 
  5.      * 
  6.      * @return An {@code Iterator} instance. 
  7.      */  
  8.     Iterator<T> iterator();  
  9. }  

其中Iterator如下：

[java] view plain copy
  1. public interface Iterator<E> {  
  2.     
  3.     public boolean hasNext();  
  4.    
  5.      
  6.     public E next();  
  7.    
  8.     
  9.     public void remove();  
  10. }  

AbstractCollection

AbstractCollection 是Collection接口的抽象实现，实现了其中大部分的功能。如下所示，我们实现自己的Collection只需要实现三个方法即可：

[java] view plain copy
  1. Collection<String> c =  
  2.            /** 
  3.         * 
  4.         *自定义实现示例，在AbstractCollection 中的一些方法的实现中，如Clear，调用了 
  5.         *iterator()方法，而在这些方法在子类中，实现这是典型的template模式。 
  6.         * 
  7.         */  
  8.        new AbstractCollection<String>() {  
  9.    
  10.            /* * 
  11.             * 迭代器 
  12.             */  
  13.            @Override  
  14.            public Iterator<String> iterator() {  
  15.               // TODO Auto-generated method stub  
  16.               return null;  
  17.            }  
  18.    
  19.            /* 
  20.             * 大小 
  21.             */  
  22.            @Override  
  23.            public int size() {  
  24.               // TODO Auto-generated method stub  
  25.               return 0;  
  26.            }  
  27.             
  28.            /* 
  29.             * 抽象实现是抛出异常，我们需要自己实现 
  30.             */  
  31.            @Override  
  32.            public boolean add(String e) {  
  33.               return true;  
  34.            }  
  35.        };  

如下代码片段摘自AbstractCollection，调用了iterator方法，其中有很多类似代码,如addAll、removeAll、contains、toArray()等，这些实现只是基本的实现，子类中有更有效率的就会覆盖它。典型的可见后面的Arraylist的toArray()。

[java] view plain copy
  1. public void clear() {  
  2.     Iterator<E> e = iterator();  
  3.     while (e.hasNext()) {  
  4.         e.next();  
  5.         e.remove();  
  6.     }  
  7.     }  

List

List接口表示数据结构中的链表，其继承collection接口，又往里面添加了一些链表操作的方法，主要是随机访问、删除、查找、专用的迭代器等，如下所示：

[java] view plain copy
  1. /** 
  2.    随机获取 
  3. */  
  4. E get(int index);  
  5.    
  6.     /** 
  7.      * 随机设置值 
  8.      */  
  9.     E set(int index, E element);  
  10.    
  11.     /** 
  12.      * 随机添加 
  13.      */  
  14.     void add(int index, E element);  
  15.    
  16.     /** 
  17.      *随机移除 
  18.      */  
  19.     E remove(int index);  
  20.    
  21.    
  22.     // Search Operations  
  23.    
  24.     /** 
  25.      * 查找 
  26.      */  
  27.     int indexOf(Object o);  
  28.    
  29.     /** 
  30.      * 从后查找 
  31.      */  
  32.     int lastIndexOf(Object o);  
  33.    
  34.    
  35.     // List Iterators  
  36.    
  37.     /** 
  38.      *专用迭代 
  39.      */  
  40.     ListIterator<E> listIterator();  
  41.    
  42.     /** 
  43.      * 从某个位置迭代 
  44.      */  
  45.     ListIterator<E> listIterator(int index);  
  46.    
  47.     // View  
  48.    
  49.     /** 
  50.      * 子列表 
  51.      */  
  52.     List<E> subList(int fromIndex, int toIndex);  

AbstractList

这是List接口的抽象实现，和AbstractCollection类似，实现了基本的功能而把关键的方法延迟到子类中实现。如下所示一个示意子类：

[java] view plain copy
  1. List<String>  l = /** 
  2.         * 
  3.         *示例实现 
  4.         */  
  5.        new AbstractList<String>() {  
  6.    
  7.            /* 
  8.             * 随机获取 
  9.             */  
  10.            @Override  
  11.            public String get(int index) {  
  12.               return null;  
  13.            }  
  14.    
  15.            /* 
  16.             * 大小 
  17.             */  
  18.            @Override  
  19.            public int size() {  
  20.               return 0;  
  21.            }  
  22.             
  23.            /* 
  24.             * 超类中实现抛出异常，表示不可变list 
  25.             * 
  26.             * 自己实现后变为可变 
  27.             */  
  28.            @Override  
  29.            public String set(int index, String element) {  
  30.               return null;  
  31.            }  
  32.             
  33.             
  34.            /* 
  35.             * 默认实现抛出异常 
  36.             */  
  37.             
  38.            @Override  
  39.            public void add(int index, String element) {  
  40.            }  
  41.             
  42.            /** 
  43.             * 默认实现抛出异常 
  44.             */  
  45.            @Override  
  46.            public String remove(int index) {  
  47.                
  48.               return null;  
  49.            }  
  50.             
  51.        };  

ListIterator

List接口添加了新的方法，其中一个方法就是返回ListIterator,其扩展了iterator，增加了向前遍历的方法。主要链表是有序的。

其实现不多说，需要注意的就是迭代器失效问题，在list实现中，维护了一个字段modCount，当此list进行改变操作，如add/remove等的时候，此值会进行改变，当构造迭代器的时候，此值会在迭代器中保留一个副本，使用迭代器中的方法都会检查副本和list中的modCount是否一致，如果不一致，抛出迭代器异常。需要注意的是，java中的for each语法，经过编译后，是使用的迭代器。

如下部分源码示例：

[java] view plain copy
  1. private class Itr implements Iterator<E> {  
  2.     /** 此类是个内部类，直接访问abstractList的字段 
  3.      * Index of element to be returned by subsequent call to next. 
  4.      */  
  5.     int cursor = 0;  
  6.    
  7.     /** 
  8.      * Index of element returned by most recent call to next or 
  9.      * previous.  Reset to -1 if this element is deleted by a call 
  10.      * to remove. 
  11.      */  
  12.     int lastRet = -1;  
  13.    
  14.     /** 
  15.      * 注意这点 
  16.      */  
  17.     int expectedModCount = modCount;  
  18.    
  19.      
  20. /** 
  21.      *迭代器的next方法 
  22.      */  
  23.    
  24.     public E next() {  
  25.    
  26. /** 
  27.      *操作前进行检查 
  28.      */  
  29.             checkForComodification();  
  30.         try {  
  31.        E next = get(cursor);  
  32.        lastRet = cursor++;  
  33.        return next;  
  34.         } catch (IndexOutOfBoundsException e) {  
  35.        checkForComodification();  
  36.        throw new NoSuchElementException();  
  37.         }  
  38.     }  
  39. /** 
  40.      *检查迭代器失效问题。 
  41.      */  
  42.     final void checkForComodification() {  
  43.         if (modCount != expectedModCount)  
  44.        throw new ConcurrentModificationException();  
  45.     }  
  46.     }  

ArrayList

这是一般编程中最长使用的数据结构，基于数组实现的顺序表，但是数组可自动扩容。它直接继承于abstractList,故只研究其关键实现和方法。

数组存储

ArrayList是基于数组的存储，默认构造初始大小是10，后面我们会看到这个初始大小会一定程度上影响其性能：

[java] view plain copy
  1. /** 
  2.      * The array buffer into which the elements of the ArrayList are stored. 
  3.      * The capacity of the ArrayList is the length of this array buffer. 
  4.      */  
  5. private transient Object[] elementData;  
  6. public ArrayList(int initialCapacity) {  
  7.     super();  
  8.         if (initialCapacity < 0)  
  9.             throw new IllegalArgumentException("Illegal Capacity: "+  
  10.                                                initialCapacity);  
  11.     this.elementData = new Object[initialCapacity];  
  12.     }  
  13.    
  14.     /** 
  15.      * Constructs an empty list with an initial capacity of ten. 
  16.      */  
  17.     public ArrayList() {  
  18.     this(10);  
  19.     }  

Add方法

  List接口有两个add的重载方法，第一个是在list的末尾添加元素，第二个是随机位置添加元素，其自动扩展数据容量的方法是ensureCapacity(int),保证大小：

[java] view plain copy
  1. /** 
  2.      * 此方法在父类中已经实现，但是arralylist覆盖了其实现，采用更加有效率的实现 
  3.      */  
  4.     public boolean add(E e) {  
  5.        ensureCapacity(size + 1);  // Increments modCount!!  
  6.        elementData[size++] = e;  
  7.        return true;  
  8.         }  
  9.    
  10.         /** 
  11.          * 任意位置添加元素，相应的元素后移，保持链表的特性。 
  12.          * 其中System.arrayCopy效率较高。 
  13.          * 
  14.          */  
  15.         public void add(int index, E element) {  
  16.        if (index > size || index < 0)  
  17.            throw new IndexOutOfBoundsException(  
  18.            "Index: "+index+", Size: "+size);  
  19.    
  20.        ensureCapacity(size+1);  // Increments modCount!!  
  21.        System.arraycopy(elementData, index, elementData, index + 1,  
  22.                size - index);  
  23.        elementData[index] = element;  
  24.        size++;  
  25.         }  
  26.          
  27.          
  28.         /** 
  29.          * 保证list链表的大小，如果不足则扩容。 
  30.          * 这个方法比较消耗性能，因此，如果实现可以知道或者预估AyyayList的大小，那么 
  31.          * 可以在构造的时候设定合适的初始容量。 
  32.          */  
  33.         public void ensureCapacity(int minCapacity) {  
  34.        modCount++;  
  35.        //获取旧的数组大小  
  36.        int oldCapacity = elementData.length;  
  37.        //比较，如果不足则扩容  
  38.        if (minCapacity > oldCapacity) {  
  39.            Object oldData[] = elementData;  
  40.            int newCapacity = (oldCapacity * 3)/2 + 1;  
  41.             if (newCapacity < minCapacity)  
  42.            newCapacity = minCapacity;  
  43.                 // 调用效率较高的arraycopy  
  44.                 elementData = Arrays.copyOf(elementData, newCapacity);  
  45.        }  
  46.         }  

Vector

实现和ArraaylIst基本一致，只是在方法上加了同步操作，但需要注意其线程安全是相对的，比如一个线程进行add操作，另外一个线程迭代，肯定会出异常。

另外有个Stack继承Vector，添加了栈的相关方法，如push,和pop。

LinkedList

基于链表的顺序表，和ArrayList相比，其随机插入和删除的效率较高，因为其不需要扩容和移动元素操作，但是随机访问效率较低（随机访问需要从头节点遍历）。

AbstractSequentialList

LinkedList其继承于AbstractSequentialList，而其中AbstractSequentialList实现了abstractlist中的抽象方法，都是基于迭代器实现的，它同时把返回迭代器的方法覆盖为抽象方法。故LinkedList实现的关键在于迭代器，如下所示：

[java] view plain copy
  1. public abstract class AbstractSequentialList<E> extends AbstractList<E> {  
  2.      
  3.    
  4.     /** 
  5.           *基于迭代器实现的get 
  6.      */  
  7.     public E get(int index) {  
  8.         try {  
  9.             return listIterator(index).next();  
  10.         } catch (NoSuchElementException exc) {  
  11.             throw new IndexOutOfBoundsException("Index: "+index);  
  12.         }  
  13.     }  
  14.    
  15.     /** 
  16.      *基于迭代器实现的set 
  17.      */  
  18.     public E set(int index, E element) {  
  19.     try {  
  20.         ListIterator<E> e = listIterator(index);  
  21.         E oldVal = e.next();  
  22.         e.set(element);  
  23.         return oldVal;  
  24.     } catch (NoSuchElementException exc) {  
  25.         throw new IndexOutOfBoundsException("Index: "+index);  
  26.     }  
  27.     }  
  28.    
  29. /* 
  30. 基于迭代器实现的add 
  31.   
  32.      */  
  33.     public void add(int index, E element) {  
  34.     try {  
  35.         listIterator(index).add(element);  
  36.     } catch (NoSuchElementException exc) {  
  37.         throw new IndexOutOfBoundsException("Index: "+index);  
  38.     }  
  39.     }  
  40.    
  41.     /** 
  42.      * 基于迭代器实现的remove 
  43.      * 
  44.      */  
  45.     public E remove(int index) {  
  46.     try {  
  47.         ListIterator<E> e = listIterator(index);  
  48.         E outCast = e.next();  
  49.         e.remove();  
  50.         return outCast;  
  51.     } catch (NoSuchElementException exc) {  
  52.         throw new IndexOutOfBoundsException("Index: "+index);  
  53.     }  
  54. }  
  55.    
  56.     public Iterator<E> iterator() {  
  57.         return listIterator();  
  58.     }  
  59.    
  60.     /** 
  61.      * Returns a list iterator over the elements in this list (in proper 
  62.      * sequence). 
  63.      * 
  64.      */  
  65.     public abstract ListIterator<E> listIterator(int index);  
  66. }  

LinkedList

Linkedlist除了实现了List接口，还实现了队列的相关接口，这里略过不提。由listiterator接口，可知linkedList也是一个可双向遍历的顺序表。

只需研究每个链表节点的结构和迭代器实现。

链表节点如下所示，是一个静态内部类：

[java] view plain copy
  1. private static class Entry<E> {  
  2.     E element;  
  3.     Entry<E> next;  
  4.     Entry<E> previous;  
  5.    
  6.     Entry(E element, Entry<E> next, Entry<E> previous) {  
  7.         this.element = element;  
  8.         this.next = next;  
  9.         this.previous = previous;  
  10.     }  
  11.     }  

其迭代器实现是一个内部类，接下来以其add操作说明，其他类似：

[java] view plain copy
  1. private class ListItr implements ListIterator<E> {  
  2.            private Entry<E> lastReturned = header;  
  3.            private Entry<E> next;  
  4.            private int nextIndex;  
  5.            private int expectedModCount = modCount;  
  6.    
  7.            /** 
  8.             * 构造的时候采用一个优化技巧，根据index决定从前还是从后遍历。 
  9.             */  
  10.            ListItr(int index) {  
  11.                if (index < 0 || index > size)  
  12.               throw new IndexOutOfBoundsException("Index: "+index+  
  13.                                 ", Size: "+size);  
  14.                if (index < (size >> 1)) {  
  15.               next = header.next;  
  16.                for (nextIndex=0; nextIndex<index; nextIndex++)  
  17.                   next = next.next;  
  18.                } else {  
  19.               next = header;  
  20.               for (nextIndex=size; nextIndex>index; nextIndex--)  
  21.                   next = next.previous;  
  22.                }  
  23.            }  
  24.    
  25.    
  26.            /* 
  27.             * 链表插入，在构造此迭代器的时候，index就是插入的位置，故直接插入元素即可 
  28.             * 
  29.             * addbefor是ArrayList的方法，就是链表插入，指针改变的过程，这里不赘述。 
  30.             */  
  31.            public void add(E e) {  
  32.                checkForComodification();  
  33.                lastReturned = header;  
  34.                addBefore(e, next);  
  35.                nextIndex++;  
  36.                expectedModCount++;  
  37.            }  
  38.    
  39.            final void checkForComodification() {  
  40.                if (modCount != expectedModCount)  
  41.               throw new ConcurrentModificationException();  
  42.            }  
  43.            }  
  44.        
  45.        
  46.        
  47.          
  48.        
  49.           /** 
  50.          *AbstractSequentialList的方法，随机插入。首先构造从index开始的迭代器 
  51.          */  
  52.         public void add(int index, E element) {  
  53.            try {  
  54.                listIterator(index).add(element);  
  55.            } catch (NoSuchElementException exc) {  
  56.                throw new IndexOutOfBoundsException("Index: "+index);  
  57.            }  
  58.            }  

CopyOnWriteArrayList

CopyOnWriteArrayList是java并发包中的一个工具类，在jdk1.5的时候被引入，单独一个它的内容足以写一篇文章，故这里不再展开，只是简要对其说明。

其基本思想从名称中可以看出，当进行写操作的时候，先复制复制出一个副本，写操作对副本进行。

读和遍历操作发生在操作发生的那一刻存在的副本上。

写操作的时候枷锁，读操作的时候不加锁。并通过java内存模型的语义，进行优雅的设计。

CopyOnWrite并发容器用于读多写少的并发场景。CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，请不要使用CopyOnWrite容器。

相关推荐