JDK1.8源码-06-java.util.LinkedList

字数统计: 5.3k字   |   阅读时长≈ 24分钟

JDK1.8源码-06-java.util.LinkedList

上一篇中我们介绍了List集合的一种典型实现ArrayList，我们知道ArrayList使用数组结构实现的，这一篇介绍List集合的另外一种实现LinkedList，这是一个由链表构成的数组，本篇我们将介绍 LinkedList 是如何实现的。

1. 定义

LinkedList是一个用链表实现的集合，元素有序且可以重复

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

mark

和ArrayList集合一样，LinkedList集合也实现了Cloneable接口和Serializable接口，分别用来支持克隆以及支持序列化。

注意：相对于ArrayList集合，LinkedList集合多实现了一个Deque接口，这是一个双向队列的接口，双向队列就是两端都可以进行增加和删除操作的。

2. 字段属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    // 链表节点个数（初始化）为0
transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
	// 指向第一个节点的指针
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
	// 指向最后一个节点的指针
    transient Node<E> last;

    /**
     * Constructs an empty list.
     */

注意这里出现了一个Node类，这是LinkedList一个内部类，其中每一个元素代表一个node对象，LindedList集合就是由许多个Node对象类似手拉着手的。

1
2
3
4
5
6
7
8
9
10
11
12
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;
    }
}

如下图所示：

mark

上图的LinkedList是有三个元素，也就是由3个Node对象构成，size=3,head指向第一个元素data:1,last指向最后一个节点data:2

3. 构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Constructs an empty list.
 */
public LinkedList() {
}

/**
 * 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<? extends E> c) {
    this();
    addAll(c);
}

LinkedList 有两个构造函数：

  • 第一个是默认为空的构造函数
  • 第二个是将已有的元素集合添加到Collection的实例添加到LinkedList 中， 调用该的是addAll()方法（等下会详细介绍这个方法）。
  • 注意：LinkedList是没有初始化链表大小的构造函数，因为链表不像数组，一个定义好的数组是必须要有确定的大小的，然后去分配内存空间，而链表不一样，它没有确定的大小，通过指针的移动来指向下一个内存分配的地址。

4. 添加元素

4.1 addFirst(E 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
   /**
    * Inserts the specified element at the beginning of this list.
    *
    * @param e the element to add
    */
// 将指定的元素附加到链表头节点
   public void addFirst(E e) {
       linkFirst(e);
   }

   /**
    * Links e as first element.
    */
   private void linkFirst(E e) {
       // 将头结点赋值给f
       final Node<E> f = first;
       // 将指定元素构造成一个新节点，此节点的指向下一个节点的引用为头结点
       final Node<E> newNode = new Node<>(null, e, f);
       // 将新节点设为头结点，那么原先的f变成第二个节点
       first = newNode;
       // 如果第二个节点为空，也就是原先链表是空的
       if (f == null)
           last = newNode;
       else
           // 将元素的头结点的上一个节点指向新节点
           f.prev = newNode;
       size++; // 节点数+1
       modCount++;	// 和ArrayList中一样，iterator和listIterator方法返回的迭代器和列表迭代器实现使用。
   }

具体过程如图所示：

  1. mark

  1. 将指定元素构造成一个新节点，此节点的指向下一个节点的引用为头结点,同时将新节点设为头结点，那么原先的f变成第二个节点

mark

4.2 addLast(E e)和add(E 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
   /**
    * Appends the specified element to the end of this list.
    *
    * <p>This method is equivalent to {@link #addLast}.
    *
    * @param e element to be appended to this list
    * @return {@code true} (as specified by {@link Collection#add})
    */

// 将元素添加到链表末尾
   public boolean add(E e) {
       linkLast(e);
       return true;
   }

   /**
    * Appends the specified element to the end of this list.
    *
    * <p>This method is equivalent to {@link #add}.
    *
    * @param e the element to add
    */

// 将元素添加到链表末尾
   public void addLast(E e) {
       linkLast(e);
   }

   /**
    * Links e as last element.
    */
   void linkLast(E e) {
       // 将l设置为最后一个节点
       final Node<E> l = last;
       // 新建一个节点，节点的上一个节点是l，下一个指向null
       final Node<E> newNode = new Node<>(l, e, null);
       // 将新节点设置为尾节点
       last = newNode;
       // 如果尾节点是空，表示原来的链表是空的
       if (l == null)
           // 那么就把头结点设置为新创建的节点
           first = newNode;
       else
           // 将原来尾节点的下一个节点指向新创建的节点
           l.next = newNode;
       size++; // 节点数+1
       modCount++; // 和ArrayList中一样，iterator和listIterator方法返回的迭代器和列表迭代器实现使用。
   }

具体过程如图所示：

  1. mark

  2. 新建一个节点，节点的上一个节点是l，下一个指向null,同时将新节点设置为尾节点

mark

4.3 add(int index, E element)

  • 将指定元素插入到此列表中的指定位置
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
public void add(int index, E element) {
    //判断索引 index >= 0 && index <= size中时抛出IndexOutOfBoundsException异常
    checkPositionIndex(index);
    // 如果索引值等于链表大小
    if (index == size)
        // 将节点插入到尾节点
        linkLast(element);
    else
        linkBefore(element, node(index));
}


void linkLast(E e) {
    // 将l设置为尾节点
    final Node<E> l = last;
    // 构造一个新节点，上一个指向l，后面指向null
    final Node<E> newNode = new Node<>(l, e, null);
    // 将尾节点设置成新的节点
    last = newNode;
    // 如果尾节点为空，表示原先链表为空
    if (l == null)
        // 将头结点设置成新创建的节点
        first = newNode;
    else
        // 将原来尾节点的下一个节点引用指向新节点
        l.next = newNode;
    // 长度加1
    size++;
    //和ArrayList中一样，iterator和listIterator方法返回的迭代器和列表迭代器实现使用。
    modCount++;
}


void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 拿到待插入节点的上一个节点
    final Node<E> pred = succ.prev;
    // 新建节点，元素是e，上一个节点是pred,下一个节点是succ
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 处理头指针：将新节点设置成待插入节点的上一个节点
    succ.prev = newNode;
    
    // 处理尾指针：next指向newNode
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

4.4 addAll(Collection<? extends E> c)

按照指定集合的迭代器返回的顺序，将指定集合中的所有元素追加到此列表的末尾。

此方法还有一个addAll(int index,Collection<? extends E> c)。将集合c中的所有元素插入到指定索引处的位置。

本质上：addAll(Collection<? extends E> c) == addAll(size,Collection<? extends E> c)

1
2
3
4
    // 按照指定集合的迭代器返回的顺序，将指定集合中的所有元素追加到此列表的末尾。
public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
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
/**
 * Inserts all of the elements in the specified collection into this
 * list, starting at the specified position.  Shifts the element
 * currently at that position (if any) and any subsequent elements to
 * the right (increases their indices).  The new elements will appear
 * in the list in the order that they are returned by the
 * specified collection's iterator.
 *
 * @param index index at which to insert the first element
 *              from the specified collection
 * @param c collection containing elements to be added to this list
 * @return {@code true} if this list changed as a result of the call
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * @throws NullPointerException if the specified collection is null
 */

public boolean addAll(int index, Collection<? extends E> c) {
    // 判断索引是否有越界情况
    checkPositionIndex(index);

    // 将集合转换成一个Object类型的数组
    Object[] a = c.toArray();
    // 拿到数组的长度
    int numNew = a.length;
    // 如果传入添加的集传入合为空，直接返回false(Collection<? extends E> c这个集合)
    if (numNew == 0)
        return false;

    Node<E> pred, succ;
    // 如果插入的位置等于链表的长度，就是将原集合元素附加到链表的末尾
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    // 遍历要插入的元素
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

  • 看到上面想LinkedList集合中添加元素的各种方式，可以发现LinkedList 每次添加元素只是改变元素的上一个指针的引用和下一个指针的引用，而且都没有扩容。

  • 对比于ArrayList，需要扩容，而且在中间插入元素的时候，后面的元素都要移动一位。

  • 两种插入元素的效率差异很大。

5. 删除元素

删除元素和添加元素一样，也是通过更改指向上一个节点和指向下一个节点的引用即可。

5.1 remove()和removeFirst()

从此列表中移除并返回第一个元素

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
// 从链表中删除第一个元素
public E remove(){
    return removeFirst();
}    


public E removeFirst() {
    // 设置f是头结点
        final Node<E> f = first;
        if (f == null)
            //如果头结点为空，则抛出异常
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }


    /**
     * Unlinks non-null first node f.
     */
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        // 拿到头结点的元素
        final E element = f.item;
        // 拿到头结点的next指针
        final Node<E> next = f.next;
        // 元素置为null
        f.item = null;
        // next指针置为null
        f.next = null; // help GC
        // 将第二个节点的赋值为头结点
        first = next;
        // 如果第二个节点为空（当前链表只存在第一个元素）
        if (next == null)
            // 那么尾节点也置为 null
            last = null;
        else
            // 将第二个节点的prev指向null
            next.prev = null;
        // size-1
        size--;
        // 操作数+1
        modCount++;
        // 返回删除的元素
        return element;
    }

5.2 removeLast()

从该列表中删除并返回最后一个元素

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
public E removeLast() {
    final Node<E> l = last;
    // 如果尾节点为空，表示当前集合为空，抛出异常
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

/**
 * Unlinks non-null last node l.
 */
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    // 拿到尾节点的元素
    final E element = l.item;
    // 拿到尾节点的prev指针
    final Node<E> prev = l.prev;
    // 元素置为null
    l.item = null;
    // prev指向null
    l.prev = null; // help GC
    // 将倒数第二个节点作为最后的节点
    last = prev;
    // 如果倒数第二个节点为null
    if (prev == null)
        // 那么将头节点也置为 null
        first = null;
    else
        // 如果倒数第二个节点不为空，那么将倒数第二个节点的下一个引用置为 null
        prev.next = null;
    size--;
    modCount++;
    return element;
}

5.3 remove(int index)

删除此列表中指定位置的元素

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
public E remove(int index) {
    // 判断索引是否越界
    checkElementIndex(index);
    return unlink(node(index));
}

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; // 上一个元素的next指向当前的next
        x.prev = null; // 将prev指向null
    }

    // 表示删除最后一个节点
    if (next == null) {
        // 直接把最后一个节点换位倒数第二个节点
        last = prev;
    } else { // 不是删除最后一个节点
        next.prev = prev; // 将下一个节点的prev指向当前节点的上一个节点
        x.next = null; // next指向null,断开链接
    }

    // 元素清空，方便GC
    x.item = null;
    // 长度-1
    size--;
    modCount++;
    return element;
}

5.4 remove(Object o)

如果存在要删除的这个对象，则从该列表中删除指定元素的第一次出现的节点。

此方法本质上和remove(int index)没多大区别。通过循环判断元素是否进行删除，需要注意的是，这个只删除第一次出现的元素，并不是删除所有。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean remove(Object o) {
    if (o == null) { // 删除null
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x); // 调用unlink(x)
                return true;
            }
        }
    } else { // 不是删除null
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

6. 修改元素

通过调用set(int index,E element) 方法，用指定的元素替换此列表中指定位置的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Replaces the element at the specified position in this list with the
 * specified element.
 *
 * @param index index of the element to replace
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */

public E set(int index, E element) {
    // 判断索引index >= 0 && index <= size抛出IndexOutOfBoundsException异常
    checkElementIndex(index);
    // 获得指定索引处的元素
    Node<E> x = node(index);
    // 在上一步拿到指定索引处元素的基础上，拿到元素的val(item)
    E oldVal = x.item;
    // 修改元素的(item = element)
    x.item = element;
    // 返回指定索引位置原来的元素
    return oldVal;
}

这里主要是通过 node(index) 方法获取指定索引位置的节点，然后修改此节点位置的元素即可。

7. 查找元素

7.1 getFirst()

返回此列表的第一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * Returns the first element in this list.
 *
 * @return the first element in this list
 * @throws NoSuchElementException if this list is empty
 */
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    // 返回此列表的第一个元素
    return f.item;
}

7.2 getLast()

返回此列表中的最后一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * Returns the last element in this list.
 *
 * @return the last element in this list
 * @throws NoSuchElementException if this list is empty
 */
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    // 返回此列表中的最后一个元素
    return l.item;
}

7.3 get(int index)

返回指定索引处的元素

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * Returns the element at the specified position in this list.
 *
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    checkElementIndex(index);
    // 返回指定索引处的元素
    return node(index).item;
}

7.4 indexOf(Object o)

返回列表中指定元素第一次出现的索引，如果此列表不包含这个元素，则返回-1

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
   /**
    * Returns the index of the first occurrence of the specified element
    * in this list, or -1 if this list does not contain the element.
    * More formally, returns the lowest index {@code i} such that
    * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
    * or -1 if there is no such index.
    *
    * @param o element to search for
    * @return the index of the first occurrence of the specified element in
    *         this list, or -1 if this list does not contain the element
    */

// 返回此列表中指定元素第一次出现的索引，如果此列表不包含元素，则返回-1。
   public int indexOf(Object o) {
       int index = 0;
       // 如果查找的元素是null的话(LinkedList可以允许null值)
       if (o == null) {
     			// 从头结点开始遍历向下遍历，直到找到null
           for (Node<E> x = first; x != null; x = x.next) {
               if (x.item == null)
                   return index;
               index++;
           }
       } else { //	如果查找的元素不是null的话
           for (Node<E> x = first; x != null; x = x.next) {
               if (o.equals(x.item))
                   return index;
               index++;
           }
       }
       return -1; //找不到返回-1
   }

8. 遍历集合

8.1 普通for循环

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
    LinkedList<String> linkedList = new LinkedList<>();

    linkedList.add("A");
    linkedList.add("B");
    linkedList.add("C");
    linkedList.add("D");

    for (int i = 0; i < linkedList.size(); i++) {
        System.out.println(linkedList.get(i)); // A B C D
    }

}

代码很简单，我们就利用 LinkedList 的 get(int index) 方法，遍历出所有的元素。

但是需要注意的是， get(int index) 方法每次都要遍历该索引之前的所有元素，这句话这么理解：

比如上述的一个LinkedList 集合，我放入了 A,B,C,D是个元素。总共需要四次遍历：

  • 第一次遍历打印A:只需遍历一次。
  • 第二次遍历打印B：需要先找到 A，然后再找到 B 打印。
  • 第三次遍历打印 C：需要先找到 A，然后找到 B，最后找到 C 打印。
  • 第四次遍历打印 D：需要先找到 A，然后找到 B，然后找到 C，最后找到 D。

这样如果集合的元素很多，越查找到后面（当然此处get方法进行了优化：查找前半部分从前面开始遍历，查找后半部分从后面开始遍历）花费的时间越多。那么如何改进呢？

8.2 迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void main(String[] args) {
    LinkedList<String> linkedList = new LinkedList<>();

    linkedList.add("A");
    linkedList.add("B");
    linkedList.add("C");
    linkedList.add("D");


    // 普通迭代器
    Iterator<String> it = linkedList.iterator();
    while (it.hasNext()){
        System.out.println(it.next()); //A B C D
    }


    // 通过适配器模式实现的接口，作用是倒序打印链表
    Iterator<String> deIt = linkedList.descendingIterator();
    while (deIt.hasNext()){
        System.out.println(deIt.next()); //D C B A
    }
}

在 LinkedList 集合中也有一个内部类ListItr,方法实现大致上差不多(这里是指和ArrayList中的内部类差不多)，通过移动游标指向每一次要遍历的元素，不用在遍历某个元素之前都要从头开始。其实现方法如下：

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
public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;

    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

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

    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();

        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }

    public boolean hasPrevious() {
        return nextIndex > 0;
    }

    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();

        lastReturned = next = (next == null) ? last : next.prev;
        nextIndex--;
        return lastReturned.item;
    }

    public int nextIndex() {
        return nextIndex;
    }

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

    public void remove() {
        checkForComodification();
        if (lastReturned == null)
            throw new IllegalStateException();

        Node<E> lastNext = lastReturned.next;
        unlink(lastReturned);
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
        expectedModCount++;
    }

    public void set(E e) {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();
        lastReturned.item = e;
    }

    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }

    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (modCount == expectedModCount && nextIndex < size) {
            action.accept(next.item);
            lastReturned = next;
            next = next.next;
            nextIndex++;
        }
        checkForComodification();
    }

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

这里需要注意的是modCount字段，前面我们在增加和删除元素的时候，都会进行自增操作modCount，这是因为如果想一边迭代，一边用集合自带的方法进行删除或者新增操作的话，都会抛出异常（但是使用迭代器操作不会抛出异常）。

1
2
3
4
5
6
    // modCount
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();

        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");
        linkedList.add("D");


        // 普通迭代器
        Iterator<String> it = linkedList.iterator();
        while (it.hasNext()){
            System.out.println(it.next()); //A B C D
//            linkedList.remove(); // 此处会抛出异常
            it.remove(); // 迭代器不会抛出异常
        }
    }

8.3 迭代器forEach循环

迭代器的另一种形式就是使用 foreach 循环，底层实现也是使用的迭代器，这里我们就不做介绍了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void main(String[] args) {
    LinkedList<String> linkedList = new LinkedList<>();

    linkedList.add("A");
    linkedList.add("B");
    linkedList.add("C");
    linkedList.add("D");

    // 方式一：
    linkedList.forEach(System.out::println); // A B C D

    // 方式二
    for (String str : linkedList) {
        System.out.println(str);   // A B C D
    }
}

8.4 迭代器和for循环的效率差异

首先我们需要先知道如下两个概念：

  • 普通for循环：每次遍历一个索引的元素之前，都要访问之前所有的索引。
  • 迭代器：每次访问一个元素之后，都会用游标记录当前访问位置的元素，遍历一个元素，记录一个位置。

接下来我们来看实际的例子：

  1. 普通for循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void main(String[] args) {
    // 1 . 普通for循环实验
    LinkedList<Integer> linkedList = new LinkedList<>();

    // 存10000个元素
    for (int i = 0; i < 10000; i++) {
        linkedList.add(i);
    }

    // 记录开始时间
    long beginTime = System.currentTimeMillis();

    // 取10000个元素
    for (int i = 0; i < 10000; i++) {
        System.out.println(linkedList.get(i));
    }

    long endTime = System.currentTimeMillis();
    System.out.println("普通for循环花了" + (endTime-beginTime)+"的时间");

}

结果如下：

mark

  1. 迭代器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void main(String[] args) {
    // 2. 迭代器实验
    LinkedList<Integer> linkedList = new LinkedList<>();

    // 存10000个元素
    for (int i = 0; i < 10000; i++) {
        linkedList.add(i);
    }

    // 记录开始时间
    long beginTime = System.currentTimeMillis();

    // 取10000个元素
    Iterator<Integer> it = linkedList.iterator();
    while (it.hasNext()){
        System.out.println(it.next());
    }


    long endTime = System.currentTimeMillis();
    System.out.println("迭代器花了" + (endTime-beginTime)+"的时间");

}

结果如下所示：

mark

一万个元素两者之间都相差一倍多的时间，如果是十万，百万个元素，那么两者之间相差的速度会越来越大！！！

参考文档：https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html#

打赏
  • 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！
  • © 2019-2022 Zhuuu
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信