Java 컬렉션 프레임워크 - 목록별 설명

요약:

　List는 특히 Java Collection Framework의 중요한 멤버입니다. List Interface 및 모든 구현 클래스를 포함합니다. List 인터페이스 는 Collection 인터페이스를 상속하므로 List에는 Collection의 모든 작업이 포함됩니다. 동시에 List는 목록 유형이기 때문에 List 자체도 그 자체에 적합한 몇 가지 메서드를 제공합니다. ArrayList는 동적 배열으로, 배열의 동적 확장을 실현하고 높은 랜덤 액세스 효율성을 갖습니다. LinkedList는 이중 연결 리스트, 랜덤입니다. 삽입 및 삭제 는 효율적이며 대기열의 구현으로 사용할 수 있습니다.

---

1. 핵심 사항

1. 기본 기능 및 프레임워크

2. ArrayList 나열: 동적 배열

3. LinkedList: 양방향LoopLinked List

---

기본 기능 및 프레임워크 나열

1. 목록 특수 연산

목록에는 목록 인터페이스와 목록 인터페이스의 모든 구현 클래스가 포함됩니다. (ArrayList , LinkedList, Vector, Stack), 여기서 Vector 및 Stack은 더 이상 사용되지 않습니다. List 인터페이스는 Collection 인터페이스를 구현하기 때문에(코드 1 참조) List 인터페이스에는 Collection 인터페이스에서 제공하는 모든 공통 메서드가 있습니다. 동시에 List는 목록 유형이므로 List 인터페이스도 몇 가지 공통 메서드를 제공합니다. 표 1과 같이 그 자체에 적합합니다.

// 代码 1public interface List<E> extends Collection<E> { ... }

---

　　　　　표 1. 목록별 메서드(AbstractList를 예로 사용)

Function	Introduction	Note
boolean addAll(int index, Collection extends E> c)	将指定 collection 中的所有元素都插入到列表中的指定位置	可选操作
E get(int index)| 返回列表中指定位置的元素	在 AbstractList 中以抽象方法 abstract public E get(int index); 存在	AbstractList 中唯一的抽象方法
E set(int index, E element)	用指定元素替换列表中指定位置的元素	可选操作，set 操作是 List 的特有操作
void add(int index, E element)	在列表的指定位置插入指定元素	可选操作
E remove(int index)	移除列表中指定位置的元素	可选操作
int indexOf(Object o)	返回此列表中第一次出现的指定元素的索引；如果此列表不包含该元素，则返回 -1	在 AbstractList 中默认实现；在 ArrayList，LinkedList中分别重写；
int lastIndexOf(Object o)	返回此列表中最后出现的指定元素的索引；如果列表不包含此元素，则返回 -1	在 AbstractList 中默认实现；在 ArrayList，LinkedList中分别重写；
ListIterator listIterator()	返回此列表元素的列表迭代器（按适当顺序）	在 AbstractList 中默认实现，ArrayList，Vector和Stack使用该默认实现，LinkedList重写该实现；
ListIterator  listIterator(int index)	返回列表中元素的列表迭代器（按适当顺序），从列表的指定位置开始	在 AbstractList 中默认实现，ArrayList，Vector和Stack使用该默认实现，LinkedList重写该实现；
List  subList(int fromIndex, int toIndex)	返回列表中指定的 fromIndex（包括 ）和 toIndex（不包括）之间的视图	在 AbstractList 中默认实现（ArrayList，LinkedList使用该默认实现）；之所以说是视图，是因为实际上返回的 list 是靠原来的 list 支持的;

---

특히 List의 경우:

• AbstractList는 iterator() 메소드의 일반적인 구현을 제공합니다 , next() 및 Remove() 메소드의 하단 레이어는 각각 get(int index) 및 Remove(int index) 메소드 에 의해 구현됩니다.

• subList 메소드의 경우 원래 목록 및 sublist는 을 non- 구조 성적 변형(목록 크기의 변화를 수반하지 않는 변형)은 서로 영향을 미칩니다. 구조적 변형의 경우: 구조적 변형의 경우 발생이 반환된 하위 목록인 경우 원래 목록의 크기도 변경됩니다(modCount 및 ExpectModCount가 동시에 변경되면 빠른 실패 메커니즘이 트리거되지 않습니다); 구조적 문제가 발생하면 원본 목록이 수정됩니다(반환된 하위 목록으로 인한 변경 사항 제외). 그러면 l.modCount != ExpectModCount 판단이 TRUE를 반환하고 Fast-Fail 메커니즘을 트리거하며 Con현재 모드if처리예외. 따라서 sublist를 호출하고 하위 목록을 반환한 후 원본 목록의 크기를 수정하면 이전에 생성된 하위 목록은 유효하지 않게 됩니다.

• 목록 섹션 삭제: list.subList(from, to).clear();

　　　　　　

---

2. 목록 구조
관련 클래스를 소개합니다.

AbstractList는 List 인터페이스를 구현하고 AbstractCollection을 상속하는

추상 클래스
• 입니다.

  "순서대로 요소를 탐색하고 액세스"하려면 List의 Iterator를 사용할 수 있습니다. 추상 클래스 AbstractList는 특정 위치의 요소에 액세스하는 동안(즉, 인덱스로 액세스) 이 구현을 제공합니다. , 요소의 추가 및 삭제는 List의 각 요소의 연결 관계에 관련되며 AbstractList에는 구현이 제공되지 않습니다. (List의 유형이 다르고 구현 방법도 다르기 때문에 특정 구현은 하위 클래스에 배치됩니다.) ;

  AbstractSequentialList는 AbstractList
• 에서 상속되는 추상 클래스입니다.

  AbstractSequentialList는 "인덱스 인덱스 값을 기준으로 연결리스트를 동작시키는 연결리스트의 모든 함수"를 ListIterator를 통해 구현합니다. 또한 ArrayList는 System.arraycopy를 통해 "인덱스 인덱스 값에 따라 시퀀스 테이블을 동작시키는 시퀀스 테이블의 모든 함수"를 구현합니다(요소 이동 완료). ArrayList, LinkedList, Vector 및 Stack은 List의 네 가지 구현 클래스입니다.

• ArrayList는

  동적입니다. 배열

• .

  배열로 구현되며 무작위 액세스 효율성은 높지만 무작위 삽입 및 무작위 삭제 효율성은 낮습니다. LinkedList는 이중 연결 리스트(시퀀스 테이블)

  .

• LinkedList는 무작위 접근 효율성이 낮지만, 무작위 삽입, 무작위 삭제 효율성이 높습니다. 스택, 대기열 또는 이중 종료 대기열로 작동할 수 있습니다. 벡터는 ArrayList와 마찬가지로 동적 배열이기도 합니다. . 배열 으로 구현됩니다. 그러나 ArrayList는 스레드가 아닙니다

  안전
. 반면 Vector는 스레드로부터 안전합니다.

• 스택은 스택입니다. Vector에서 상속됩니다. 특징은 FILO, First In Last Out입니다.

• 목록 특징:

  • Java의 목록은 배열의 효과적인 확장입니다. 제네릭이 사용되지 않는 경우 모든 유형의 요소를 수용할 수 있는 구조입니다. 일반으로 지정됩니다. 배열(배열은 제네릭을 지원하지 않음)에 비해 List의 용량은 동적으로 확장될 수 있습니다.

  • 목록의 요소는 "정렬"되어 있습니다. 여기서 "순서 지정"은 정렬을 의미하는 것이 아니라 컬렉션 , 에 포함된 요소의 위치를 ​​지정할 수 있음을 의미합니다. 삽입에 대한 정확한 제어 목록에 있는 각 요소의 위치, 정수 인덱스(목록의 위치)를 기준으로 요소에 액세스하고 목록에서 요소를 검색합니다.

  • List의 요소는 순서가 지정된 데이터 구조이므로 반복될 수 있습니다.

  • List에서 일반적으로 사용되는 컬렉션객체 는 다음과 같습니다. ArrayList, Vector, LinkedList 중 전자는 배열 기반으로 저장되고, 후자는 연결리스트 기반으로 저장됩니다. 그중 Vector는 스레드로부터 안전하지만 나머지 두 개는 그렇지 않습니다.

  • 목록에는 null이 포함될 수 있습니다.

  • List 인터페이스는 Iterator 인터페이스에서 제공하는 일반 작업을 허용하는 것 외에도 ListIterator라는 특수 반복자를 제공합니다. 반복자는 요소 삽입 및 교체뿐만 아니라 양방향 액세스도 허용합니다.

  ---

  3. ArrayList

  1. ArrayList 기본

  　ArrayList는 List의 모든 선택적 작업을 구현하고 NULL을 포함한 모든 요소를 ​​허용합니다. List 인터페이스 구현 외에도 이 클래스는 지원 배열의 크기를 조작하는 메서드도 제공합니다. ArrayList는 배열을 기반으로 구현되며, 용량이 자동으로 증가할 수 있는 동적 배열입니다. 크기 속성 은 압축된 배열의 크기가 아닌 컨테이너의 요소 수를 식별하는 데 사용됩니다. 각 ArrayList 인스턴스에는 목록의 요소를 저장하는 데 사용되는 배열의 크기인 용량이 있으며, 이는 항상 목록의 크기 이상입니다. ArrayList에 요소가 추가되면 용량이 자동으로 늘어납니다. 자동 증가로 인해 데이터가 새 어레이에 다시 복사됩니다. 따라서 데이터의 양을 예측할 수 있다면 ArrayList를 구성할 때 해당 용량을 지정할 수 있습니다. 애플리케이션은 또한 수많은 요소를 추가하기 전에 verifyCapacity 작업을 사용하여 ArrayList 인스턴스의 용량을 늘릴 수 있으므로 증분 재할당량을 줄일 수 있습니다. 이 구현은 동기식 이 아닙니다. 여러 스레드가 동시에 ArrayList 인스턴스에 액세스하고 스레드 중 하나 이상이 이를 구조적으로 수정하는 경우(구조적 수정은 하나 이상의 요소를 추가 또는 제거하거나 기본 배열의 크기를 명시적으로 조정하는 모든 작업을 의미함) ; 단순히 요소의 값을 설정하는 것은 구조적 수정이 아닙니다.) 목록이 수정되면 외부적으로 동기화를 유지해야 합니다.

  ---

  　ArrayList는 직렬화 가능 인터페이스를 구현하므로 직렬화를 지원하며 직렬화를 통해 전송할 수 있습니다. 소스 코드를 읽어보면 ArrayList의 내장 배열이 serialize되지 않음을 나타내기 위해 Transient 키워드로 수정되었음을 알 수 있습니다. 물론 ArrayList의 요소는 직렬화/역직렬화 중에 ArrayList의 writeObject()/readObject() 메서드가 호출되고 ArrayList의 요소(예: 0 . ..size-1 첨자) 및 capacity size 에 해당하는 요소는 스트림에 쓰거나 읽습니다. 이것의 장점은 실질적으로 중요한 요소들만 저장/전송되므로 저장, 전송 및 처리 오버헤드가 최대한 절약된다는 것입니다.

  ---

  　　　ArrayList 实现了 RandomAccess 接口， 支持快速随机访问，实际上就是通过下标序号进行快速访问(于是否支持get(index)访问不同)。RandomAccess 接口是 List 实现所使用的标记接口，用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。特别地，在对List的遍历算法中，要尽量来判断是属于 RandomAccess(如ArrayList) 还是 SequenceAccess(如LinkedList），因为适合RandomAccess List的遍历算法，用在SequenceAccess List上就差别很大，即对于实现了RandomAccess接口的类实例而言，此循环

       for (int i=0, i<list.size(); i++)
         list.get(i);

  的运行速度要快于以下循环：

       for (Iterator i=list.iterator(); i.hasNext(); )
          i.next();

  　　　所以，我们在遍历List之前，可以用  if( list instanceof RamdomAccess ) 来判断一下，选择用哪种遍历方式。

  ---

  　　　ArrayList 实现了Cloneable接口，能被克隆。Cloneable 接口里面没有任何方法，只是起一个标记作用，表明当一个类实现了该接口时，该类可以通过调用clone()方法来克隆该类的实例。

  ---

  　　　ArrayList不是线程安全的，只能用在单线程环境下，多线程环境下可以考虑用 Collections.synchronizedList(List l) 函数返回一个线程安全的ArrayList类，也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类。

  ---

  2、ArrayList在JDK中的定义

  　　　我们可以从 ArrayList 的源码看到，其包括 两个域 和 三个构造函数 , 源码如下：

  • private transient Object[] elementData ： 支撑数组

  • private int size ： 元素个数

  ---

  • public ArrayList(int initialCapacity){ … } ： 给定初始容量的构造函数；

  • public ArrayList() { … } ： Java Collection Framework 规范-默认无参的构造函数 (初始容量指定为10)；

  • public ArrayList(Collectionc extends E>) { … } ： Java Collection Framework 规范-参数为指定容器的构造函数

  ---

  public class ArrayList<E> extends AbstractList<E>        
  implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
      private static final long serialVersionUID = 8683452581122892189L;    
      /**
       * The array buffer into which the elements of the ArrayList are stored.（ArrayList 支撑数组）
       * The capacity of the ArrayList is the length of this array buffer.（ArrayList 容量的定义）
       */
      private transient Object[] elementData;                 
      // 瞬时域
  
      /**
       * The size of the ArrayList (the number of elements it contains).（ArrayList 大小的定义）
       */
      private int size;    /**
       * Constructs an empty list with the specified initial capacity
       */
      public ArrayList(int initialCapacity) {                     
      // 给定初始容量的构造函数
      super();        
      if (initialCapacity < 0)            
      throw new IllegalArgumentException("Illegal Capacity: "+
                                                 
      initialCapacity);    
                                                 
      this.elementData = new Object[initialCapacity];           
      // 泛型与数组不兼容
      }    /**
       * Constructs an empty list with an initial capacity of ten.
       */
      public ArrayList() {                
      // Java Collection Framework 规范：默认无参的构造函数
      this(10);
      }    
      /**
       * Constructs a list containing the elements of the specified
       * collection, in the order they are returned by the collection&#39;s
       * iterator.
       */
      public ArrayList(Collection<? extends E> c) { 
      // Java Collection Framework 规范：参数为指定容器的构造函数
      elementData = c.toArray();
      size = elementData.length;    
      // c.toArray might (incorrectly) not return Object[] (see 6260652)
      if (elementData.getClass() != Object[].class)
          elementData = Arrays.copyOf(elementData, size, Object[].class);
      }

  ---

  3、ArrayList 基本操作的保证

  • 边界检查（即检查 ArrayList 的 Size）：涉及到 index 的操作

  // 边界检查private void RangeCheck(int index) {  
  if (index >= size)    
  throw new IndexOutOfBoundsException(    
  "Index: "+index+", Size: "+size);
      }

  ---

  • 调整数组容量（增加容量）：向 ArrayList 中增加元素

  // 调整数组容量
   public void ensureCapacity(int minCapacity) {
      modCount++;    
      int oldCapacity = elementData.length;    
      if (minCapacity > oldCapacity) {
          Object oldData[] = elementData;        
          int newCapacity = (oldCapacity * 3)/2 + 1;            
          if (newCapacity < minCapacity)
          newCapacity = minCapacity;            
          // minCapacity is usually close to size, so this is a win:
              elementData = Arrays.copyOf(elementData, newCapacity);
      }
      }

  　　向 ArrayList 中增加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度。如果超出，ArrayList 将会进行扩容，以满足添加数据的需求。数组扩容通过一个 public 方法 ensureCapacity(int minCapacity) 来实现 : 在实际添加大量元素前，我也可以使用 ensureCapacity 来手动增加 ArrayList 实例的容量，以减少递增式再分配的数量。
  　　 　　 　　 　　 　　 　　 　　 　　 　　 　　 　　 　　 　　 　　 　　 　　 　　 　　
  　　ArrayList 进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长为其原容量的 1.5 倍 + 1。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用 ensureCapacity 方法来手动增加ArrayList实例的容量。

  ---

  　　在 ensureCapacity 的源代码中有这样一段代码：

  Object oldData[] = elementData;   //为什么要用到oldData[]

  　　乍一看，后面并没有用到oldData，这句话显得多此一举！但是这牵涉到了一个内存管理的问题. 而且，为什么这一句还在 if 的内部? 这是跟 elementData = Arrays.copyOf(elementData, newCapacity); 这句是有关系的，在下面这句 Arrays.copyOf
  的实现时，新创建了 newCapacity 大小的内存，然后把老的 elementData 放入。这样，由于旧的内存的引用是elementData， 而 elementData 指向了新的内存块，如果有一个局部变量 oldData 变量引用旧的内存块的话，在copy的过程中就会比较安全，因为这样证明这块老的内存依然有引用，分配内存的时候就不会被侵占掉。然后，在copy完成后，这个局部变量的生命周期也过去了，此时释放才是安全的。否则的话，在 copy 的时候万一新的内存或其他线程的分配内存侵占了这块老的内存，而 copy 还没有结束，这将是个严重的事情。

  ---

  • 调整数组容量（减少容量）：将底层数组的容量调整为当前列表保存的实际元素的大小

    　　在使用 ArrayList 过程中，由于 elementData 的长度会被拓展，所以经常会出现 size 很小但 elementData.length 很大的情况，造成空间的浪费。 ArrayList 通过 trimToSize 方法返回一个新的数组给 elementData ，其中：元素内容保持不变，length 和size 相同。

  public void trimToSize() {  
     modCount++;  
     int oldCapacity = elementData.length;  
     if (size < oldCapacity) {  
         elementData = Arrays.copyOf(elementData, size);  
     }  
  }

  ---

  • Fail-Fast机制

    　　动机： 在 Java Collection 中，为了防止在某个线程在对 Collection 进行迭代时，其他线程对该 Collection 进行结构上的修改。换句话说，迭代器的快速失败行为仅用于检测代码的 bug。
    　　
    　　本质： Fail-Fast 是 Java 集合的一种错误检测机制。
    　　
    　　作用场景： 在使用迭代器时，Collection 的结构发生变化，抛出 ConcurrentModificationException 。当然，这并不能说明 Collection对象 已经被不同线程并发修改，因为如果单线程违反了规则，同样也有会抛出该异常。
    　　
    　　当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast机制。例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会触发fail-fast机制，抛出 ConcurrentModificationException 异常。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
    　　
    　　我们知道 fail-fast 产生的原因就在于：程序在对 collection 进行迭代时，某个线程对该 collection 在结构上对其做了修改。要想进一步了解 fail-fast 机制，我们首先要对 ConcurrentModificationException 异常有所了解。当方法检测到对象的并发修改，但不允许这种修改时就抛出该异常。同时需要注意的是，该异常不会始终指出对象已经由不同线程并发修改，如果单线程违反了规则，同样也有可能会抛出改异常。诚然，迭代器的快速失败行为无法得到保证，它不能保证一定会出现该错误，但是快速失败操作会尽最大努力抛出 ConcurrentModificationException 异常，所以，为提高此类操作的正确性而编写一个依赖于此异常的程序是错误的做法，正确做法是：ConcurrentModificationException 应该仅用于检测 bug。
    　　
    　　下面我们以 ArrayList 为例进一步分析 fail-fast 产生的原因:

  private class Itr implements Iterator<E> {  
          int cursor;  
          int lastRet = -1;  
          int expectedModCount = ArrayList.this.modCount;  
  
          public boolean hasNext() {  
              return (this.cursor != ArrayList.this.size);  
          }  
  
          public E next() {  
              checkForComodification();  
              /** 省略此处代码 */  
          }  
  
          public void remove() {  
              if (this.lastRet < 0)  
                  throw new IllegalStateException();  
              checkForComodification();  
              /** 省略此处代码 */  
          }  
  
          final void checkForComodification() {  
              if (ArrayList.this.modCount == this.expectedModCount)  
                  return;  
              throw new ConcurrentModificationException();  
          }  
      }

  　　从上面的源代码我们可以看出，迭代器在调用 next() 、 remove() 方法时都是调用 checkForComodification() 方法，该方法用于判断 “modCount == expectedModCount”：若不等，触发 fail-fast 机制，抛出 ConcurrentModificationException 异常。所以，要弄清楚为什么会产生 fail-fast 机制，我们就必须要弄明白 “modCount != expectedModCount” 什么时候发生，换句话说，他们的值在什么时候发生改变的。
  　　
  　　expectedModCount 是在 Itr 中定义的：“int expectedModCount = ArrayList.this.modCount;”，所以它的值是不可能会修改的，所以会变的就是 modCount。modCount 是在 AbstractList 中定义的，为全局变量：

  protected transient int modCount = 0;

  　　从 ArrayList 源码中我们可以看出，我们直接或间接的通过 RemoveRange 、 trimToSize 和 ensureCapcity（add，remove，clear） 三个方法完成对 ArrayList 结构上的修改,所以 ArrayList 实例每当调用一次上面的方法，modCount 的值就递增一次。所以,我们这里可以判断:由于expectedModCount 的值与 modCount 的改变不同步，导致两者之间不等，从而触发fail-fast机制。我们可以考虑如下场景：
  　　 有两个线程（线程A，线程B），其中线程A负责遍历list、线程B修改list。线程A在遍历list过程的某个时候（此时expectedModCount = modCount=N），线程启动，同时线程B增加一个元素，这是modCount的值发生改变（modCount + 1 = N + 1）。线程A继续遍历执行next方法时，通告checkForComodification方法发现expectedModCount  = N  ，而modCount = N + 1，两者不等，这时触发 fail-fast机制。

  ---

  3、元素的增、改、删、查

  • 元素的增和改

    　　　ArrayList 提供了 set(int index, E element) 用于修改元素，提供 add(E e)、add(int index, E element)、addAll(Collection extends E> c)、addAll(int index, Collection extends E> c) 这些方法用于添加元素。
    　　

  // 用指定的元素替代此列表中指定位置上的元素，并返回以前位于该位置上的元素  
  public E set(int index, E element) {  
     RangeCheck(index);  
  
     E oldValue = (E) elementData[index];  
     elementData[index] = element;  
     return oldValue;  
  }    
  
  // 将指定的元素添加到此列表的尾部public boolean add(E e) {  
     ensureCapacity(size + 1);   
     elementData[size++] = e;  
     return true;  
  } 
  
  // 将指定的元素插入此列表中的指定位置。  
  // 如果当前位置有元素，则向右移动当前位于该位置的元素以及所有后续元素（将其索引加1）。  
  public void add(int index, E element) {  
     if (index > size || index < 0)  
         throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);  
     // 如果数组长度不足，将进行扩容。  
     ensureCapacity(size+1);  // Increments modCount!!  
     // 将 elementData中从Index位置开始、长度为size-index的元素，  
     // 拷贝到从下标为index+1位置开始的新的elementData数组中。  
     // 即将当前位于该位置的元素以及所有后续元素右移一个位置。  
     System.arraycopy(elementData, index, elementData, index + 1, size - index);  
     elementData[index] = element;  
     size++;  
  }    
  
  // 按照指定collection的迭代器所返回的元素顺序，将该collection中的所有元素添加到此列表的尾部。  
  public boolean addAll(Collection<? extends E> c) {  
     Object[] a = c.toArray();  
     int numNew = a.length;  
     ensureCapacity(size + numNew);  // Increments modCount  
     System.arraycopy(a, 0, elementData, size, numNew);  
     size += numNew;  
     return numNew != 0;  
  }    
  
  // 从指定的位置开始，将指定collection中的所有元素插入到此列表中。  
  public boolean addAll(int index, Collection<? extends E> c) {  
     if (index > size || index < 0)  
         throw new IndexOutOfBoundsException(  
             "Index: " + index + ", Size: " + size);  
  
     Object[] a = c.toArray();  
     int numNew = a.length;  
     ensureCapacity(size + numNew);  // Increments modCount  
  
     int numMoved = size - index;  
     if (numMoved > 0)  
         System.arraycopy(elementData, index, elementData, index + numNew, numMoved);  
  
     System.arraycopy(a, 0, elementData, index, numNew);  
     size += numNew;  
     return numNew != 0;  
     }

  ---

  • 元素的读取

   // 返回此列表中指定位置上的元素。  
   public E get(int index) {  
      RangeCheck(index);  
      return (E) elementData[index];  
    }

  ---

  • 元素的删除

    ArrayList 共有 根据下标或者指定对象两种方式的删除功能。

  romove(int index): 首先是检查范围，修改modCount，保留将要被移除的元素，将移除位置之后的元素向前挪动一个位置，将list末尾元素置空（null），返回被移除的元素。

  // 移除此列表中指定位置上的元素
   public E remove(int index) {  
      RangeCheck(index);  
  
      modCount++;  
      E oldValue = (E) elementData[index];  
  
      int numMoved = size - index - 1;  
      if (numMoved > 0)  
          System.arraycopy(elementData, index+1, elementData, index, numMoved);  
      elementData[--size] = null; // Let gc do its work  
  
      return oldValue;  
   }

  　　
  remove(Object o)：

  // 移除此列表中 “首次” 出现的指定元素（如果存在）。这是因为 ArrayList 中允许存放重复的元素。  
   public boolean remove(Object o) {  
      // 由于ArrayList中允许存放null，因此下面通过两种情况来分别处理。  
      if (o == null) {  
          for (int index = 0; index < size; index++)  
              if (elementData[index] == null) {  
                  // 类似remove(int index)，移除列表中指定位置上的元素。  
                  fastRemove(index);  
                  return true;  
              }  
      } else {  
          for (int index = 0; index < size; index++)  
              if (o.equals(elementData[index])) {  
                  fastRemove(index);  
                  return true;  
              }  
          }  
          return false;  
      } 
  }

  　　首先通过代码可以看到，当移除成功后返回true，否则返回false。remove(Object o)中通过遍历element寻找是否存在传入对象，一旦找到就调用 fastRemove 移除对象。
  　　为什么找到了元素就知道了index，不通过remove(index)来移除元素呢？因为fastRemove跳过了判断边界的处理，因为找到元素就相当于确定了index不会超过边界，而且fastRemove并不返回被移除的元素。下面是fastRemove的代码，基本和remove(index)一致。下面是 fastRemove（私有的） 的源码：

  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; // Let gc do its work  
   }

  ---

  4、小结

  　　关于ArrayList的源码，总结如下：

  • 三个不同的构造方法。无参构造方法构造的ArrayList的容量默认为10； 带有Collection参数的构造方法的实现是将Collection转化为数组赋给ArrayList的实现数组elementData。
    

  • 扩充容量的方法ensureCapacity。ArrayList在每次增加元素（可能是1个，也可能是一组）时，都要调用该方法来确保足够的容量。当容量不足以容纳当前的元素个数时，就设置新的容量为旧的容量的1.5倍加1，如果设置后的新容量还不够，则直接新容量设置为传入的参数（也就是所需的容量）。之后，用 Arrays.copyof() 方法将元素拷贝到新的数组。从中可以看出，当容量不够时，每次增加元素，都要将原来的元素拷贝到一个新的数组中，非常之耗时，也因此建议在事先能确定元素数量的情况下，才使用ArrayList，否则建议使用LinkedList。
    

  • ArrayList 的实现中大量地调用了Arrays.copyof() 和 System.arraycopy()方法 。我们有必要对这两个方法的实现做下深入的了解。首先来看Arrays.copyof()方法。它有很多个重载的方法，但实现思路都是一样的，我们来看泛型版本的源码：

  public static <T> T[] copyOf(T[] original, int newLength) {  
      return (T[]) copyOf(original, newLength, original.getClass());  
  }

  　　很明显调用了另一个 copyof 方法，该方法有三个参数，最后一个参数指明要转换的数据的类型，其源码如下：

   /**
       * @param original 源数组
       * @param newLength 目标数组的长度
       * @param newType 目标数组的类型
       */public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {  
      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;
  }

  　　这里可以很明显地看出，该方法实际上是在其内部又创建了一个长度为newlength的数组，调用System.arraycopy()方法，将原来数组中的元素复制到了新的数组中。
  　　下面来看 System.arraycopy() 方法。该方法被标记了native，调用了系统的C/C++代码，在JDK中是看不到的，但在openJDK中可以看到其源码。该函数实际上最终调用了C语言的memmove()函数，因此它可以保证同一个数组内元素的正确复制和移动，比一般的复制方法的实现效率要高很多，很适合用来批量处理数组。Java强烈推荐在复制大量数组元素时用该方法，以取得更高的效率；
  　　

  • ArrayList 基于数组实现，可以通过下标索引直接查找到指定位置的元素，因此 查找效率高，但每次插入或删除元素，就要大量地移动元素，插入删除元素的效率低；
    

  • 在查找给定元素索引值等的方法中，源码都将该元素的值分为null和不为null两种情况处理，ArrayList中允许元素为null。

  ---

  四. LinkedList

  　
  1、LinkedList 简介

  　　　LinkedList 是 List接口的双向循环链表实现。LinkedList 实现了 List 中所有可选操作，并且允许所有元素（包括 null）。除了实现 List 接口外，LinkedList 为在列表的开头及结尾进行获取(get)、删除(remove)和插入(insert)元素提供了统一的访问操作，而这些操作允许LinkedList 作为Stack(栈)、Queue(队列)或Deque(双端队列：double-ended queue)进行使用。
  　　　
  　　　注意，LinkedList 不是同步的。如果多个线程同时访问一个顺序表，而其中至少一个线程从结构上（结构修改指添加或删除一个或多个元素的任何操作；仅设置元素的值不是结构修改。）修改了该列表，则它必须保持外部同步。这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedList 方法来“包装”该列表。最好在创建时完成这一操作，以防止对列表进行意外的不同步访问，如下所示：

     List list = Collections.synchronizedList(new LinkedList(...));

  　　　
  　　　LinkedList 的 iterator 和 listIterator 方法返回的迭代器是快速失败的：在迭代器创建之后，如果从结构上对列表进行修改，除非通过迭代器自身的 remove 或 add 方法，其他任何时间任何方式的修改，都将导致ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒将来不确定的时间任意发生不确定行为的风险。  
  　　　
  　　　LinkedList 在Java中的定义如下：

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

  • LinkedList 是一个继承于AbstractSequentialList的双向循环链表。它也可以被当作堆栈、队列或双端队列进行操作；

  • LinkedList 实现 List 接口，具有 List 的所有功能；

  • LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用；

  • LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆；

  • LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输；

  • 与 ArrayList 不同，LinkedList 没有实现 RandomAccess 接口，不支持快速随机访问。

  ---

  2、LinkedList 数据结构原理

  　　LinkedList底层的数据结构是基于双向循环链表的，且头结点中不存放数据, 如下：

  　　　　　　　　　　　　　　
  　　
  既然是双向链表，那么必定存在一种数据结构——我们可以称之为节点，节点实例保存业务数据，前一个节点的位置信息和后一个节点位置信息，如下图所示：

  　　　　　　　　　　　　　　

  ---

  3、LinkedList 在JDK中的定义

  A.成员变量

  • private transient Entry header = new Entry(null, null, null);

  • private transient int size = 0;

    　　其中，header是双向链表的头节点，它是Entry的实例。Entry 包含三个成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。 size 是双向链表中节点实例的个数。首先，我们来了解节点类Entry：

  private static class Entry<E> {
      E element;
      Entry<E> next;
      Entry<E> previous;
  
      Entry(E element, Entry<E> next, Entry<E> previous) {        
      this.element = element;        
      this.next = next;        
      this.previous = previous;
     }
  }

  　　节点类 Entry 很简单，element存放业务数据，previous与next分别是指向前后节点的指针。

  ---

  B.构造函数
  　　
  - public LinkedList() { … } ： Java Collection Framework 规范：空链表
  - public LinkedList(Collection extends E> c) { … } ： Java Collection Framework 规范：参数为指定容器的构造函数

  　　LinkedList提供了两个构造方法。第一个构造方法不接受参数，将header实例的previous和next全部指向header实例（注意，这个是一个双向循环链表，如果不是循环链表，空链表的情况应该是header节点的前一节点和后一节点均为null），这样整个链表其实就只有header一个节点，用于表示一个空的链表。执行完构造函数后，header实例自身形成一个闭环，如下图所示：

  　　　　　　　　　　　　　

  　　第二个构造方法接收一个Collection参数c，调用第一个构造方法构造一个空的链表，之后通过addAll将c中的元素全部添加到链表中，代码如下：

  public class LinkedList<E>    
  extends AbstractSequentialList<E>    
  implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
      private transient Entry header = new Entry(null, null, null);    
      private transient int size = 0;    /**
       * Constructs an empty list.
       */
      public LinkedList() {
          header.next = header.previous = header;
      }    /**
       * Constructs a list containing the elements of the specified
       * collection, in the order they are returned by the collection's
       * iterator.
       *
       * @param  c the collection whose elements are to be placed into this list
       * @throws NullPointerException if the specified collection is null
       */
      public LinkedList(Collection c) {    this();
      addAll(c);
      }

  ---

  C.成员方法

  • 添加数据：add()

  // 将元素(E)添加到LinkedList中
       public boolean add(E e) {         // 将节点(节点数据是e)添加到表头(header)之前。
           // 即，将节点添加到双向链表的末端。
           addBefore(e, header);         return true;
       }     public void add(int index, E element) {
           addBefore(element, (index==size ? header : entry(index)));
       }    private Entry<E> addBefore(E e, Entry<E> entry) {
           Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
           newEntry.previous.next = newEntry;
           newEntry.next.previous = newEntry;
           size++;
           modCount++;         return newEntry;
      }

  　　addBefore(E e,Entry entry)方法是个私有方法，其先通过Entry的构造方法创建e的节点newEntry（包含了将其下一个节点设置为entry，上一个节点设置为entry.previous的操作，相当于修改newEntry的“指针”），之后修改插入位置后newEntry的前一节点的next引用和后一节点的previous引用，使链表节点间的引用关系保持正确。之后修改和size大小和记录modCount，然后返回新插入的节点。

  ---

  • 删除数据remove()
    　　几个remove方法最终都是调用了一个私有方法：remove(Entry e)，只是其他简单逻辑上的区别。下面分析remove(Entry e)方法。

  private E remove(Entry<E> e) {    
  if (e == header)        
  throw new NoSuchElementException();    // 保留将被移除的节点e的内容
      E result = e.element;   // 将前一节点的next引用赋值为e的下一节点
      e.previous.next = e.next;   // 将e的下一节点的previous赋值为e的上一节点
      e.next.previous = e.previous;   // 上面两条语句的执行已经导致了无法在链表中访问到e节点，而下面解除了e节点对前后节点的引用
     e.next = e.previous = null;  // 将被移除的节点的内容设为null
    e.element = null;  // 修改size大小
    size--;
    modCount++;  // 返回移除节点e的内容
    return result;
  }

  整个删除操作分为三步：

  • 调整相应节点的前后指针信息

    　　e.previous.next = e.next;//预删除节点的前一节点的后指针指向预删除节点的后一个节点。

    　　e.next.previous = e.previous;//预删除节点的后一节点的前指针指向预删除节点的前一个节点。

  • 清空预删除节点

    　　e.next = e.previous = null;

    　　e.element = null;

  • gc完成资源回收，删除操作结束。

    　由以上 add 和 remove 源码可知，与 ArrayList 比较而言，LinkedList的添加、删除动作不需要移动很多数据，从而效率更高。

  ---

  • 数据获取get()

   public E get(int index) {        
      try {            
      return listIterator(index).next();
          } catch (NoSuchElementException exc) {            
          throw new IndexOutOfBoundsException("Index: "+index);
          }
      }

  该方法涉及到 listIterator 的构造，我们再看listIterator 的源码。

  ---

  • listIterator 源码

  private class ListItr implements ListIterator<E> {
      // 最近一次返回的节点，也是当前持有的节点
      private Entry<E> lastReturned = header;    
      // 对下一个元素的引用
      private Entry<E> next;    
      // 下一个节点的index
      private int nextIndex;    
      private int expectedModCount = modCount;    
      // 构造方法，接收一个index参数，返回一个ListItr对象
      ListItr(int index) {        
      // 如果index小于0或大于size，抛出IndexOutOfBoundsException异常
          if (index < 0 || index > size)        
          throw new IndexOutOfBoundsException("Index: "+index+                            
          ", Size: "+size);        // 判断遍历方向
          if (index < (size >> 1)) {    // 相当于除法，但比除法效率高
          // next赋值为第一个节点
          next = header.next;        // 获取指定位置的节点
          for (nextIndex=0; nextIndex<index; nextIndex++)
              next = next.next;
          } else {// else中的处理和if块中的处理一致，只是遍历方向不同
          next = header;        for (nextIndex=size; nextIndex>index; nextIndex--)
              next = next.previous;
         }
     }    // 根据nextIndex是否等于size判断时候还有下一个节点（也可以理解为是否遍历完了LinkedList）
      public boolean hasNext() {        return nextIndex != size;
     }    // 获取下一个元素
      public E next() {
         checkForComodification();        
         // 如果nextIndex==size,则已经遍历完链表，即没有下一个节点了（实际上是有的，因为是循环链表，任何一个节点都会有上一个和下一个节点，
         这里的没有下一个节点只是说所有节点都已经遍历完了）
          if (nextIndex == size)        throw new NoSuchElementException();        
          // 设置最近一次返回的节点为next节点
          lastReturned = next;        // 将next“向后移动一位”
          next = next.next;        // index计数加1
          nextIndex++;        // 返回lastReturned的元素
          return lastReturned.element;
     }    public boolean hasPrevious() {        
     return nextIndex != 0;
     }    
     // 返回上一个节点，和next()方法相似
      public E previous() {        
      if (nextIndex == 0)        
      throw new NoSuchElementException();
  
          lastReturned = next = next.previous;
          nextIndex--;
         checkForComodification();        
         return lastReturned.element;
     }    public int nextIndex() {        
     return nextIndex;
     }    public int previousIndex() {        
     return nextIndex-1;
     }    // 移除当前Iterator持有的节点
      public void remove() {
             checkForComodification();
              Entry<E> lastNext = lastReturned.next;            
              try {
                  LinkedList.this.remove(lastReturned);
              } catch (NoSuchElementException e) {                
              throw new IllegalStateException();
             }        if (next==lastReturned)
                  next = lastNext;            
                  else
          nextIndex--;
          lastReturned = header;
          expectedModCount++;
     }    // 修改当前节点的内容
      public void set(E e) {        
      if (lastReturned == header)        
      throw new IllegalStateException();
         checkForComodification();
          lastReturned.element = e;
     }    // 在当前持有节点后面插入新节点
      public void add(E e) {
         checkForComodification();        
         // 将最近一次返回节点修改为header
          lastReturned = header;
         addBefore(e, next);
          nextIndex++;
          expectedModCount++;
     }    
     // 判断expectedModCount和modCount是否一致，以确保通过ListItr的修改操作正确的反映在LinkedList中
      final void checkForComodification() {        
      if (modCount != expectedModCount)        
      throw new ConcurrentModificationException();
     }
  }

  　　由以上 get 和 listIterator 源码可知，与 ArrayList 比较而言，LinkedList的随机访问需要从头遍历到指定位置元素，而不像ArrayList直接通过索引取值，效率更低一些。

  ---

  4、小结

  　　关于LinkedList的源码，给出几点比较重要的总结：

  • LinkedList 本质是一个双向循环链表，可用作List，Queue，Stack和Deque；

  • LinkedList 并未实现 RandomAccess 接口；

  • 相对于ArrayList，LinkedList有更好的增删效率，更差的随机访问效率；

위 내용은 Java 컬렉션 프레임워크 - 목록별 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!