一、 LinkedList概述:

  • LinkedList双向链表实现。
  • LinkedList实现List,Deque接口，提供栈、队列、双端队列的方法。
  • LinkedList不是线程安全。
  • LinkedList实现RandomAccess, Cloneable和java.io.Serializable接口。RandomAccess支持快速随机访问。Cloneable能被克隆。Serializable支持序列化。

二、 LinkedList实现:

  • (1).LinkedList实现双向链表结构(Node)。E是泛型

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

        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).定义入口访问链表数据结构

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

    /**
 * 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;

  • (3).元素操作 - 添加到首部(addFirst)

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

         public void addFirst(E e) {
          linkFirst(e);
      }
      /**
       * Links e as first element.
       * 往首节点(first)插入新节点
       */
     private void linkFirst(E e) {
          final Node<E> f = first;
          final Node<E> newNode = new Node<>(null, e, f);
          first = newNode;
          if (f == null)
              last = newNode;
          else
              f.prev = newNode;
          size++;
          modCount++;
     }

  • 添加到尾部(addLast)

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

           public void addLast(E e) {
        linkLast(e);
       }
       /**
        * Links e as last element.
        * 往尾节点(last)插入新节点
        */
       void linkLast(E e) {
           final Node<E> l = last;
           final Node<E> newNode = new Node<>(l, e, null);
           last = newNode;
           if (l == null)
               first = newNode;
           else
               l.next = newNode;
           size++;
           modCount++;
       }

  • (4).删除

  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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198

/**
   * Unlinks non-null first node f.
   * 取消链接非空第一个节点f。
   */
  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;
      size--;
      modCount++;
      return element;
  }

  /**
   * Unlinks non-null last node l.
   * 取消链接非空最后节点f。
   */
  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;
      size--;
      modCount++;
      return element;
  }
  /**
   * Unlinks non-null node x.
   * 取消链接非空节点x。
   */
  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;
  }
  /**
   * Removes and returns the first element from this list.
   * 从此列表中删除并返回第一个元素。
   * @return the first element from this list
   * @throws NoSuchElementException if this list is empty
   */
  public E removeFirst() {
      final Node<E> f = first;
      if (f == null)
          throw new NoSuchElementException();
      return unlinkFirst(f);
  }

  /**
   * Removes and returns the last element from this list.
   * 从此列表中删除并返回最后一个元素。
   * @return the last element from this list
   * @throws NoSuchElementException if this list is empty
   */
  public E removeLast() {
      final Node<E> l = last;
      if (l == null)
          throw new NoSuchElementException();
      return unlinkLast(l);
  }
  /**
   * Removes the first occurrence of the specified element from this list,
   * if it is present.  If this list does not contain the element, it is
   * unchanged.  More formally, removes the element with the lowest index
   * {@code i} such that
   * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
   * (if such an element exists).  Returns {@code true} if this list
   * contained the specified element (or equivalently, if this list
   * changed as a result of the call).
   *从列表中删除指定元素的第一个出现（如果存在）。 如果此列表不包含该元素，则它将保持不变。 
   * @param o element to be removed from this list, if present
   * @return {@code true} if this list contained the specified element
   */
  public boolean remove(Object o) {
      if (o == null) {
          for (Node<E> x = first; x != null; x = x.next) {
              if (x.item == null) {
                  unlink(x);
                  return true;
              }
          }
      } else {
          for (Node<E> x = first; x != null; x = x.next) {
              if (o.equals(x.item)) {
                  unlink(x);
                  return true;
              }
          }
      }
      return false;
  }
  /**
   * Removes all of the elements from this list.
   * The list will be empty after this call returns.
   * 从此列表中删除所有元素。此调用返回后，列表将为空。
   */
  public void clear() {
      // Clearing all of the links between nodes is "unnecessary", but:
      // - helps a generational GC if the discarded nodes inhabit
      //   more than one generation
      // - is sure to free memory even if there is a reachable Iterator
      for (Node<E> x = first; x != null; ) {
          Node<E> next = x.next;
          x.item = null;
          x.next = null;
          x.prev = null;
          x = next;
      }
      first = last = null;
      size = 0;
      modCount++;
  }
  /**
   * Removes the element at the specified position in this list.  Shifts any
   * subsequent elements to the left (subtracts one from their indices).
   * Returns the element that was removed from the list.
   * 删除该列表中指定位置的元素。 将任何后续元素向左移动（从其索引中减去一个元素）。返回从列表中删除的元素。
   * @param index the index of the element to be removed
   * @return the element previously at the specified position
   * @throws IndexOutOfBoundsException {@inheritDoc}
   */
  public E remove(int index) {
      checkElementIndex(index);
      return unlink(node(index));
  }
  /**
   * Removes the first occurrence of the specified element in this
   * list (when traversing the list from head to tail).  If the list
   * does not contain the element, it is unchanged.
   * 删除此列表中指定元素的第一次出现（从头到尾遍历列表时）。 如果列表不包含该元素，则它不会更改。
   * @param o element to be removed from this list, if present
   * @return {@code true} if the list contained the specified element
   * @since 1.6
   */
  public boolean removeFirstOccurrence(Object o) {
      return remove(o);
  }

  /**
   * Removes the last occurrence of the specified element in this
   * list (when traversing the list from head to tail).  If the list
   * does not contain the element, it is unchanged.
   * 删除此列表中指定元素的最后一次出现（从尾到头遍历列表时）。 如果列表不包含该元素，则它不会更改。
   * @param o element to be removed from this list, if present
   * @return {@code true} if the list contained the specified element
   * @since 1.6
   */
  public boolean removeLastOccurrence(Object o) {
      if (o == null) {
          for (Node<E> x = last; x != null; x = x.prev) {
              if (x.item == null) {
                  unlink(x);
                  return true;
              }
          }
      } else {
          for (Node<E> x = last; x != null; x = x.prev) {
              if (o.equals(x.item)) {
                  unlink(x);
                  return true;
              }
          }
      }
      return false;
  }
  • (5).Iterator 迭代器实现
  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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136


  /**
   * Returns a list-iterator of the elements in this list (in proper
   * sequence), starting at the specified position in the list.
   * Obeys the general contract of {@code List.listIterator(int)}.<p>
   *
   * The list-iterator is <i>fail-fast</i>: if the list is structurally
   * modified at any time after the Iterator is created, in any way except
   * through the list-iterator's own {@code remove} or {@code add}
   * methods, the list-iterator will throw a
   * {@code ConcurrentModificationException}.  Thus, in the face of
   * concurrent modification, the iterator fails quickly and cleanly, rather
   * than risking arbitrary, non-deterministic behavior at an undetermined
   * time in the future.
   *
   * @param index index of the first element to be returned from the
   *              list-iterator (by a call to {@code next})
   * @return a ListIterator of the elements in this list (in proper
   *         sequence), starting at the specified position in the list
   * @throws IndexOutOfBoundsException {@inheritDoc}
   * @see List#listIterator(int)
   */
  public ListIterator<E> listIterator(int index) {
      checkPositionIndex(index);
      return new ListItr(index);
  }

  private class ListItr implements ListIterator<E> {
      private Node<E> lastReturned = null;
      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++;
      }

      final void checkForComodification() {
          if (modCount != expectedModCount)
              throw new ConcurrentModificationException();
      }
  }
  /**
   * @since 1.6
   */
  public Iterator<E> descendingIterator() {
      return new DescendingIterator();
  }

  /**
   * Adapter to provide descending iterators via ListItr.previous
   */
  private class DescendingIterator implements Iterator<E> {
      private final ListItr itr = new ListItr(size());
      public boolean hasNext() {
          return itr.hasPrevious();
      }
      public E next() {
          return itr.previous();
      }
      public void remove() {
          itr.remove();
      }
  }

  • (6).subList实现只是一个视图

    • 继承AbstractList

  • (7).转换数组对象

 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

  /**
   * Returns an array containing all of the elements in this list
   * in proper sequence (from first to last element).
   *
   * <p>The returned array will be "safe" in that no references to it are
   * maintained by this list.  (In other words, this method must allocate
   * a new array).  The caller is thus free to modify the returned array.
   *
   * <p>This method acts as bridge between array-based and collection-based
   * APIs.
   * 以适当的顺序（从第一个到最后一个元素）返回一个包含此列表中所有元素的数组。
   * <p>返回的数组将是“安全的”，因为该列表不保留对其的引用。（换句话说，这个方法必须分配一个新的数组）。 调用者因此可以自由地修改返回的数组。
   * <p>此方法充当基于数组和基于集合的API之间的桥接。
   * @return an array containing all of the elements in this list
   *         in proper sequence
   */
  public Object[] toArray() {
      Object[] result = new Object[size];
      int i = 0;
      for (Node<E> x = first; x != null; x = x.next)
          result[i++] = x.item;
      return result;
  }

  /**
   * 先判断出入的数组a的大小是否足够，若大小不够则拓展。这里用到了发射的方法，重新实例化了一个大小为size的数组。之后将数组a赋值给数组result，
   * 遍历链表向result中添加的元素。最后判断数组a的长度是否大于size，若大于则将size位置的内容设置为null。返回a。
   */
  @SuppressWarnings("unchecked")
  public <T> T[] toArray(T[] a) {
      if (a.length < size)
          a = (T[])java.lang.reflect.Array.newInstance(
                              a.getClass().getComponentType(), size);
      int i = 0;
      Object[] result = a;
      for (Node<E> x = first; x != null; x = x.next)
          result[i++] = x.item;

      if (a.length > size)
          a[size] = null;

      return a;
  }

三、 总结:

  • 插入和删除操作时比ArrayList更加高效，因为它是基于链表的。
  • 查询元素比ArrayList慢，最坏情况都要遍历size/2(size»1)。 - 按索引查询时，先判断索引位置，size的一半就用fist遍历，否就是用last遍历
  • LinkedList双链表。next下节点,prev上节点。
  • 也实现fail-fast机制实现，逻辑跟ArrayList一样。都是modCount做判断。
  • SubList只是一个LinkedList视图，实现AbstractList。