java 数组和集合框架 (II) - 集合框架, 迭代器 iterator, 列表

集合框架：

用于存储数据的容器。

Java 集合框架概述

一方面，面向对象语言对事物的体现都是以对象的形式，为了方便对多个对象的操作，就要对对象进行存储。另一方面，使用Array存储对象方面具有一些弊端，而Java 集合就像一种容器，可以动态地把多个对象的引用放入容器中。

数组在内存存储方面的特点：

数组初始化以后，长度就确定了。

数组声明的类型，就决定了进行元素初始化时的类型

数组在存储数据方面的弊端：

数组初始化以后，长度就不可变了，不便于扩展

数组中提供的属性和方法少，不便于进行添加、删除、插入等操作，且效率不高。同时无法直接获取存储元素的个数

数组存储的数据是有序的、可以重复的。---->存储数据的特点单一

Java 集合类可以用于存储数量不等的多个对象，还可用于保存具有映射关系的关联数组。

Java 集合可分为Collection 和Map 两种体系

Collection接口：单列数据，定义了存取一组对象的方法的集合

List：元素有序、可重复的集合

Set：元素无序、不可重复的集合

Map接口：双列数据，保存具有映射关系“key-value对”的集合

Collection接口继承树

Map接口继承树

Collection 接口

Collection 接口内容

Collection 接口是List、Set 和Queue 接口的父接口，该接口里定义的方法既可用于操作Set 集合，也可用于操作List 和Queue 集合。

JDK不提供此接口的任何直接实现，而是提供更具体的子接口(如：Set和List)实现。

在Java5 之前，Java 集合会丢失容器中所有对象的数据类型，把所有对象都当成Object 类型处理；从JDK 5.0 增加了泛型以后，Java 集合可以记住容器中对象的数据类型。

Collection 接口方法

1，添加：
add(object)：添加一个元素
addAll(Collection) ：添加一个集合中的所有元素。

2，获取：
int size()：集合中有几个元素。

3，清空集合
clear()：将集合中的元素全删除。

4，是否为空
boolean isEmpty()：集合中是否有元素。

5，判断是否包含指定元素：
boolean contains(obj) ：是通过元素的 equals，
     equals 方法来判断是否方法来判断是否是同一个对象 。
boolean containsAll(Collection) ：集合中是否包含指定的多个元素，
    也是调用元素的 equals方法来比较的。拿两个集合的元素挨比较 。。

6，删除：
remove(obj) ：删除集合中指定的对象。注意：删除成功，集合的长度会改变。
removeAll(collection) ：删除部分元素。部分元素和传入Collection一致。

7，取交集：
boolean  retainAll(Collection) ：对当前集合中保留和指定集合中的相同的元素。
如果两个集合元素相同，返回flase；如果retainAll修改了当前集合，返回true。

8，集合是否相等
boolean equals(Object obj)

9，获取集合对象的哈希值hashCode()
10，获取集合中所有元素：
  Iterator  iterator()：迭代器

11，将集合变成数组：
toArray();

Iterator迭代器接口：

迭代器：

Iterator对象称为迭代器 (设计模式的一种 )，是一个接口。主要用于遍历 Collection集合中元素。

Collection接口继承了java.lang.Iterable接口，该接口有一个iterator()方法，那么所有实现了Collection接口的集合类都有一个iterator()方法，用以返回一个实现了Iterator接口的对象。

Iterator 仅用于遍历集合，Iterator本身并不提供承装对象的能力。如果需要创建Iterator 对象，则必须有一个被迭代的集合。

集合对象每次调用iterator()方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前。

Iterator接口的方法

boolean	hasNext()  如果仍有元素可以迭代，则返回 true。
E	next()   返回迭代的下一个元素。
void	remove()  从迭代器指向的 collection 中移除迭代器返回的最后一个元素（可选操作）。

在调用it.next()方法之前必须要调用it.hasNext()进行检测。若不调用，且下一条记录无效，直接调用it.next()会抛出NoSuchElementException异常。

@Test
public void IteratorTest01() {
    Collection coll = new ArrayList();
    coll.add("abc0");
    coll.add("abc1");
    coll.add("abc2");
    coll.add("Tom");
    //--------------方式1----------------------
    Iterator iter = coll.iterator();
    while(iter.hasNext()){
       Object obj= iter.next();
       if(obj.equals("Tom")){
           System.err.println(obj);
           iter.remove();
       }
    }
    //---------------方式2用此种----------------------
    for(Iterator it = coll.iterator();it.hasNext(); ){
       System.out.println(it.next());
    }
}

数组既可以存储基本数据类型，也可以存储引用类型。它存储引用类型的时候的数组就叫对象数组。

注意：

Iterator可以删除集合的元素，但是是遍历过程中通过迭代器对象的remove方法，不是集合对象的remove方法。

如果还未调用next()或在上一次调用next方法之后已经调用了remove方法，再调用remove都会报IllegalStateException。

List集合遍历

@Test
public void IteratorTest02() {
    ArrayList<String> coll = new ArrayList();
    coll.add("abc0");
    coll.add("abc1");
    coll.add("abc2");
    coll.add("Tom");

    //--------------方式1 迭代器遍历----------------------
    Iterator iter = coll.iterator();
    while(iter.hasNext()){
        Object obj= iter.next();
        System.out.println("方式1 迭代器遍历    "+obj);
    }

    //---------------方式2 普通for循环----------------------
    for(int i = 0; i<coll.size(); i++){
        System.err.println("方式2 普通for循环  "+coll.get(i));
    }

    //---------------方式3 增强for循环----------------------
    for(String s:coll){
        System.out.println("方式3 增强for循环  "+s);
    }
}

contains产生10个1-20之间的随机数，要求随机数不能重复

//产生10个1-20之间的随机数，要求随机数不能重复

@Test
public void IteratorTest03() {

    Random r = new Random();
    ArrayList<Integer> coll = new ArrayList();
    int count =0;

    while (count<10){
        int i = r.nextInt(20) + 1;
        if (!coll.contains(i)){
            coll.add(i);
            count++;
        }
    }
    System.out.println(coll.toString());
}

List接口：

List本身是Collection接口的子接口，具备了Collection的所有方法。现在学习List体系特有的共性方法，查阅方法发现List的特有方法都有索引，这是该集合最大的特点。

LIST的间接实现类：

LinkedList（双向链表）

Vector（向量）

功能和ArrayList一样，线程安全，Stack（栈）， 表示后进先出（LIFO）的对象堆栈

List：有序(元素存入集合的顺序和取出的顺序一致)，元素都有索引。元素可以重复。

• |--ArrayList：数组线性表，底层的数据结构是数组,线程不同步，ArrayList替代了Vector，查询元素的速度非常快。其内部基于一个大小可变数组来存储，允许存储 null 元素
• |--LinkedList：底层的数据结构是链表，线程不同步，增删元素的速度非常快。List 接口的链接列表实现类，允许存储 null 元素
• |--Vector：底层的数据结构就是数组，功能和ArrayList一样线程安全，Stack（栈），表示后进先出（LIFO）的对象堆栈，线程同步的，Vector无论查询和增删都巨慢。

List集合方法

1，添加：
    add(index,element) ：在指定的索引位插入元素。
    addAll(index,collection) ：在指定的索引位插入一堆元素。
2，删除：
    remove(index) ：删除指定索引位的元素。 返回被删的元素。
3，获取：
    Object get(index) ：通过索引获取指定元素。
    int indexOf(obj) ：获取指定元素第一次出现的索引位，如果该元素不存在返回-1；
                     所以，通过-1，可以判断一个元素是否存在。
    int lastIndexOf(Object o) ：反向索引指定元素的位置。
    List subList(start,end) ：获取子列表。
4，修改：
    Object set(index,element) ：对指定索引位进行元素的修改。
5，获取所有元素：
    ListIterator listIterator()：list集合特有的迭代器。
List集合支持对元素的增、删、改、查。

迭代过程中对元素进行操作

在进行list列表元素迭代的时候，如果想要在迭代过程中，想要对元素进行操作的时候，比如满足条件添加新元素。会发生ConcurrentModificationException并发修改异常。

导致的原因是：

集合引用和迭代器引用在同时操作元素，通过集合获取到对应的迭代器后，在迭代中，进行集合引用的元素添加，迭代器并不知道，所以会出现异常情况。

如何解决呢？

既然是在迭代中对元素进行操作,找迭代器的方法最为合适.可是Iterator中只有hasNext,next,remove方法.通过查阅的它的子接口,ListIterator,发现该列表迭代器接口具备了对元素的增、删、改、查的动作。

ListIterator是List集合特有的迭代器。

ListIterator it = list.listIterator;//取代Iterator it = list.iterator;

方法摘要
void	add(E e) 将指定的元素插入列表（可选操作）。
boolean	hasNext() 以正向遍历列表时，如果列表迭代器有多个元素，则返回 true（换句话说，如果 next 返回一个元素而不是抛出异常，则返回 true）。
boolean	hasPrevious() 如果以逆向遍历列表，列表迭代器有多个元素，则返回 true。
E	next() 返回列表中的下一个元素。
int	nextIndex() 返回对 next 的后续调用所返回元素的索引。
E	previous() 返回列表中的前一个元素。
int	previousIndex() 返回对 previous 的后续调用所返回元素的索引。
void	remove() 从列表中移除由 next 或 previous 返回的最后一个元素（可选操作）。
void	set(E e) 用指定元素替换 next 或 previous 返回的最后一个元素（可选操作）。

可变长度数组的原理

当元素超出数组长度，会产生一个新数组，将原数组的数据复制到新数组中，再将新的元素添加到新数组中。

ArrayList：是按照原数组的50%延长。构造一个初始容量为 10 的空列表。

Vector：是按照原数组的100%延长。

注意：对于list集合，底层判断元素是否相同，其实用的是元素自身的equals方法完成的。所以建议元素都要复写equals方法，建立元素对象自己的比较相同的条件依据。

List实现类之一：ArrayList

ArrayList概述

ArrayList是List 接口的典型实现类、主要实现类, ArrayList是对象引用的一个”变长”数组

ArrayList 是List 接口的可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。

每个ArrayList 实例都有一个容量，该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList 中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造ArrayList 时指定其容量。在添加大量元素前，应用程序也可以使用ensureCapacity 操作来增加ArrayList 实例的容量，这可以减少递增式再分配的数量。

注意，此实现不是同步的。如果多个线程同时访问一个ArrayList 实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。

 相对比的，Vector 是线程安全的，其中涉及线程安全的方法皆被同步操作了。ArrayList和Vector除了线程不同步之外，大致相等。

ArrayList的实现

对于ArrayList 而言，它实现List 接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。

属性

//默认容量的大小
private static final int DEFAULT_CAPACITY = 10;

//空数组常量
private static final Object[] EMPTY_ELEMENTDATA = {};

//默认的空数组常量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//存放元素的数组，从这可以发现ArrayList的底层实现就是一个Object数组
transient Object[] elementData;

//数组中包含的元素个数
private int size;

//数组的最大上限
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

ArrayList的属性非常少，就只有这些。其中最重要的莫过于elementData了，ArrayList所有的方法都是建立在elementData之上。接下来，我们就来看一下一些主要的方法吧。

构造器：

ArrayList提供了三种方式的构造器，可以构造一个默认初始容量为10的空列表、构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表，这些元素按照该collection的迭代器返回它们的顺序排列的。

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

从构造方法中我们可以看见，默认情况下，elementData是一个大小为0的空数组，当我们指定了初始大小的时候，elementData的初始大小就变成了我们所指定的初始大小了。

读取：

因为ArrayList是采用数组结构来存储的，所以它的get方法非常简单，先是判断一下有没有越界，之后就可以直接通过数组下标来获取元素了，所以get的时间复杂度是O(1)。

//返回此列表中指定位置上的元素。

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

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

存储：

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)这些添加元素的方法。下面我们一一讲解：

//用指定的元素替代此列表中指定位置上的元素，并返回以前位于该位置上的元素。
//set方法的作用是把下标为index的元素替换成element，跟get非常类似，
//所以就不在赘述了，时间复杂度度为O(1)。

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

//ArrayList的add方法也很好理解，在插入元素之前，它会先检查是否需要扩容，然后再把元素添加到数组中最后一个元素的后面。在ensureCapacityInternal方法中，我们可以看见，如果当elementData为空数组时，它会使用默认的大小去扩容。所以说，通过无参构造方法来创建ArrayList时，它的大小其实是为0的，只有在使用到的时候，才会通过grow方法去创建一个大小为10的数组。

//第一个add方法的复杂度为O(1)，虽然有时候会涉及到扩容的操作，但是扩容的次数是非常少的，所以这一部分的时间可以忽略不计。如果使用的是带指定下标的add方法，则复杂度为O(n)，因为涉及到对数组中元素的移动，这一操作是非常耗时的。

//将指定的元素添加到此列表的尾部。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

//将指定的元素插入此列表中的指定位置。
//如果当前位置有元素，则向右移动当前位于该位置的元素以及所有后续元素（将其索引加1）。
public void add(int index, E element) {
    rangeCheckForAdd(index);
    //如果数组长度不足，将进行扩容
    ensureCapacityInternal(size + 1);  
    // Increments modCount!!
    //将elementData中从Index位置开始、长度为size-index的元素，
    //拷贝到从下标为index+1位置开始的新的elementData数组中。
    //即将当前位于该位置的元素以及所有后续元素右移一个位置。
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

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

//按照指定collection的迭代器所返回的元素顺序，将该collection中的所有元素添加到此列表的尾部。
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(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) {
    rangeCheckForAdd(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(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;
}

删除：

ArrayList提供了根据下标或者指定对象两种方式的删除功能。如下：

//移除此列表中指定位置上的元素。

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

//移除此列表中首次出现的指定元素（如果存在）。这是应为ArrayList中允许存放重复的元素。
public boolean remove(Object o) {
//由于ArrayList中允许存放null，因此下面通过两种情况来分别处理。
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
               //类似remove(intindex)，移除列表中指定位置上的元素。
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}
remove方法与add带指定下标的方法非常类似，也是调用系统的arraycopy方法来移动元素，时间复杂度为O(n)。

注意：从数组中移除元素的操作，也会导致被移除的元素以后的所有元素的向左移动一个位置。

grow方法

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

grow方法是在数组进行扩容的时候用到的，从中我们可以看见，ArrayList每次扩容都是扩1.5倍，然后调用Arrays类的copyOf方法，把元素重新拷贝到一个新的数组中去。

size方法

public int size() {
    return size;
}

size方法非常简单，它是直接返回size的值，也就是返回数组中元素的个数，时间复杂度为O(1)。这里要注意一下，返回的并不是数组的实际大小。

8、indexOf方法和lastIndexOf

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

indexOf方法的作用是返回第一个等于给定元素的值的下标。它是通过遍历比较数组中每个元素的值来查找的，所以它的时间复杂度是O(n)。

lastIndexOf的原理跟indexOf一样，而它仅仅是从后往前找起罢了。

调整数组容量：

从上面介绍的向ArrayList中存储元素的代码中，我们看到，每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。

数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。

ArrayList还给我们提供了将底层数组的容量调整为当前列表保存的实际元素的大小的功能。它可以通过trimToSize方法来实现

Fail-Fast机制：

ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险

ArrayList的JDK1.8之前与之后的实现区别？

• JDK1.7：ArrayList像饿汉式，直接创建一个初始容量为10的数组
• JDK1.8：ArrayList像懒汉式，一开始创建一个长度为0的数组，当添加第一个元素时再创建一个始容量为10的数组
• lArrays.asList(…) 方法返回的List 集合，既不是ArrayList实例，也不是Vector 实例。Arrays.asList(…)  返回值是一个固定长度的List 集合

List 实现类之二：Vector

Vector 是一个古老的集合，JDK1.0就有了。大多数操作与ArrayList相同，区别之处在于Vector是线程安全的。很多方法都跟ArrayList一样，只是多加了个synchronized来保证线程安全

在各种list中，最好把ArrayList作为缺省选择。当插入、删除频繁时，使用LinkedList；Vector总是比ArrayList慢，所以尽量避免使用。

新增方法：

void addElement(Object obj)
void insertElementAt(Object obj,intindex)
void setElementAt(Object obj,intindex)
void removeElement(Object obj)
void removeAllElements()

Vector比ArrayList多了一个属性：

protected int capacityIncrement;

这个属性是在扩容的时候用到的，它表示每次扩容只扩capacityIncrement个空间就足够了。该属性可以通过构造方法给它赋值。先来看一下构造方法：

public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

public Vector() {
    this(10);
}

public Vector(Collection<? extends E> c) {
    Object[] a = c.toArray();
    elementCount = a.length;
    if (c.getClass() == ArrayList.class) {
        elementData = a;
    } else {
        elementData = Arrays.copyOf(a, elementCount, Object[].class);
    }
}

public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

从构造方法中，我们可以看出Vector的默认大小也是10，而且它在初始化的时候就已经创建了数组了，这点跟ArrayList不一样。再来看一下grow方法：

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

从grow方法中我们可以发现，newCapacity默认情况下是两倍的oldCapacity，而当指定了capacityIncrement的值之后，newCapacity变成了oldCapacity+capacityIncrement。

List实现类之三：LinkedList

l对于频繁的插入或删除元素的操作，建议使用LinkedList类，效率较高

LinkedList的特有方法。

1. void  addFirst(Object o)，将指定数据元素插入此集合的开头,原来元素（如果有）后移；
   void addLast(Object o)，将指定数据元素插入此集合的结尾
   Object getFirst()，返回此集合的第一个数据元素
   Object getLast()，返回此集合的最后一个数据元素
   Object removeFirst()，移除并返回集合表的第一个数据元素
   Object removeLast()，移除并返回集合表的最后一个数据元素

   LinkedList：双向链表，内部没有声明数组，而是定义了Node类型的first和last，用于记录首末元素。它允许插入所有元素，包括null，同时，它是线程不同步的。同时，定义内部类Node，作为LinkedList中保存数据的基本结构。Node除了保存数据，还定义了两个变量：

双向链表每个结点除了数据域之外，还有一个前指针和后指针，分别指向前驱结点和后继结点（如果有前驱/后继的话）。另外，双向链表还有一个first指针，指向头节点，和last指针，指向尾节点。

prev变量记录前一个元素的位置

next变量记录下一个元素的位置

属性

接下来看一下 LinkedList 中的属性：

//链表的节点个数
transient int size = 0;
//指向头节点的指针
transient Node<E> first;
//指向尾节点的指针
transient Node<E> last;
LinkedList 的属性非常少，就只有这些。通过这三个属性，其实我们大概也可以猜测出它是怎么实现的了。

方法

1、结点结构

Node 是在 LinkedList 里定义的一个静态内部类，它表示链表每个节点的结构，包括一个数据域item，一个后置指针next，一个前置指针prev。

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

2、添加元素

对于链表这种数据结构来说，添加元素的操作无非就是在表头/表尾插入元素，又或者在指定位置插入元素。因为 LinkedList 有头指针和尾指针，所以在表头或表尾进行插入元素只需要 O(1) 的时间，而在指定位置插入元素则需要先遍历一下链表，所以复杂度为 O(n)。

在表头添加元素的过程如下：

当向表头插入一个节点时，很显然当前节点的前驱一定为 null，而后继结点是 first 指针指向的节点，当然还要修改 first 指针指向新的头节点。除此之外，原来的头节点变成了第二个节点，所以还要修改原来头节点的前驱指针，使它指向表头节点，源码的实现如下：

private void linkFirst(E e) {
    final Node<E> f = first;
    //当前节点的前驱指向null，后继指针原来的头节点
    final Node<E> newNode = new Node<>(null, e, f);
    //头指针指向新的头节点
    first = newNode;
    //如果原来有头节点，则更新原来节点的前驱指针，否则更新尾指针
    if (f == null)
        last = newNode;
    else
    f.prev = newNode;
    size++;
    modCount++;
}

在表尾添加元素跟在表头添加元素大同小异，如图所示：

当向表尾插入一个节点时，很显然当前节点的后继一定为 null，而前驱结点是 last 指针指向的节点，然后还要修改 last 指针指向新的尾节点。此外，还要修改原来尾节点的后继指针，使它指向新的尾节点，源码的实现如下：

void linkLast(E e) {
    final Node<E> l = last;
    //当前节点的前驱指向尾节点，后继指向null
    final Node<E> newNode = new Node<>(l, e, null);
    //尾指针指向新的尾节点
    last = newNode;
    //如果原来有尾节点，则更新原来节点的后继指针，否则更新头指针
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

最后，在指定节点之前插入，如图所示：

当向指定节点之前插入一个节点时，当前节点的后继为指定节点，而前驱结点为指定节点的前驱节点。此外，还要修改前驱节点的后继为当前节点，以及后继节点的前驱为当前节点，源码的实现如下：

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

3、删除元素

删除操作与添加操作大同小异，例如删除指定节点的过程如下图所示，需要把当前节点的前驱节点的后继修改为当前节点的后继，以及当前节点的后继结点的前驱修改为当前节点的前驱（是不是很绕？）：

删除头节点和尾节点跟删除指定节点非常类似，就不一一介绍了，源码如下：

//删除表头节点，返回表头元素的值 
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; //新头节点的前驱为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; //新尾节点的后继为null 
    size--; 
    modCount++; 
    return element; 
} 
//删除指定节点，返回指定元素的值 
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; 
} 

4、获取元素

获取元素的方法一看就懂，我就不必多加解释了。

//获取表头元素
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementExcepti