LinkedList源码解析(JDK1.8)

   1 package java.util;
   2 
   3 import java.util.function.Consumer;
   4 
   5 /**
   6  * LinkedList是List和Deque接口的双向链表的实现。实现了所有可选List操作,并允许包括null值。
   7  * LinkedList既然是通过双向链表去实现的,那么它可以被当作堆栈、队列或双端队列进行操作。并且其顺序访问非常高效,而随机访问效率比较低。
   8  * 内部方法,注释会描述为节点的操作(如删除第一个节点),公开的方法会描述为元素的操作(如删除第一个元素)
   9  * 注意,此实现不是同步的。 如果多个线程同时访问一个LinkedList实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步。
  10  * LinkedList不是线程安全的,如果在多线程中使用(修改),需要在外部作同步处理。
  11  * 这通常是通过同步那些用来封装列表的对象来实现的。
  12  * 但如果没有这样的对象存在,则该列表需要运用{@link Collections#synchronizedList Collections.synchronizedList}来进行“包装”,该方法最好是在创建列表对象时完成,为了避免对列表进行突发的非同步操作。
  13  */
  14 
  15 public class LinkedList<E>
  16         extends AbstractSequentialList<E>
  17         implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
  18     /**
  19      * 元素数量
  20      */
  21     transient int size = 0;
  22 
  23     /**
  24      * 首结点引用
  25      */
  26     transient Node<E> first;
  27 
  28     /**
  29      * 尾节点引用
  30      */
  31     transient Node<E> last;
  32 
  33     /**
  34      * 无参构造方法
  35      */
  36     public LinkedList() {
  37     }
  38 
  39     /**
  40      * 通过一个集合初始化LinkedList,元素顺序有这个集合的迭代器返回顺序决定
  41      *
  42      * @param c 其元素将被放入此列表中的集合
  43      * @throws NullPointerException 如果指定的集合是空的
  44      */
  45     public LinkedList(Collection<? extends E> c) {
  46         // 调用无参构造函数
  47         this();
  48         // 添加集合中所有的元素
  49         addAll(c);
  50     }
  51 
  52     /**
  53      * 头插入,即将节点值为e的节点设置为链表首节点,内部使用
  54      */
  55     private void linkFirst(E e) {
  56         //获取当前首结点引用
  57         final Node<E> f = first;
  58         //构建一个prev值为null,节点值为e,next值为f的新节点newNode
  59         final Node<E> newNode = new Node<>(null, e, f);
  60         //将newNode作为首节点
  61         first = newNode;
  62         //如果原首节点为null,即原链表为null,则链表尾节点也设置为newNode
  63         if (f == null)
  64             last = newNode;
  65         else                //否则,原首节点的prev设置为newNode
  66             f.prev = newNode;
  67         size++;             //长度+1
  68         modCount++;         //修改次数+1
  69     }
  70 
  71     /**
  72      * 尾插入,即将节点值为e的节点设置为链表的尾节点
  73      */
  74     void linkLast(E e) {
  75         // 获取当前尾结点引用
  76         final Node<E> l = last;
  77         //构建一个prev值为l,节点值为e,next值为null的新节点newNode
  78         final Node<E> newNode = new Node<>(l, e, null);
  79         //将newNode作为尾节点
  80         last = newNode;
  81         //如果原尾节点为null,即原链表为null,则链表首节点也设置为newNode
  82         if (l == null)
  83             first = newNode;
  84         else    //否则,原尾节点的next设置为newNode
  85             l.next = newNode;
  86         size++;
  87         modCount++;
  88     }
  89 
  90     /**
  91      * 中间插入,在非空节点succ之前插入节点值e
  92      */
  93     void linkBefore(E e, Node<E> succ) {
  94         // assert succ != null;
  95         final Node<E> pred = succ.prev;
  96         //构建一个prev值为succ.prev,节点值为e,next值为succ的新节点newNode
  97         final Node<E> newNode = new Node<>(pred, e, succ);
  98         //设置newNode为succ的前节点
  99         succ.prev = newNode;
 100         //如果succ.prev为null,即如果succ为首节点,则将newNode设置为首节点
 101         if (pred == null)
 102             first = newNode;
 103         else        //如果succ不是首节点
 104             pred.next = newNode;
 105         size++;
 106         modCount++;
 107     }
 108 
 109     /**
 110      * 删除首结点,返回存储的元素,内部使用
 111      */
 112     private E unlinkFirst(Node<E> f) {
 113         // 获取首结点存储的元素
 114         final E element = f.item;
 115         // 获取首结点的后继结点
 116         final Node<E> next = f.next;
 117         // 删除首结点
 118         f.item = null;
 119         f.next = null; //便于垃圾回收期清理
 120         // 原来首结点的后继结点设为首结点
 121         first = next;
 122         // 如果原来首结点的后继结点为空,则尾结点设为null
 123         // 否则,原来首结点的后继结点的前驱结点设为null
 124         if (next == null)
 125             last = null;
 126         else
 127             next.prev = null;
 128         size--;
 129         modCount++;
 130         // 返回原来首结点存储的元素
 131         return element;
 132     }
 133 
 134     /**
 135      * 删除尾结点,返回存储的元素,内部使用
 136      */
 137     private E unlinkLast(Node<E> l) {
 138         // 获取尾结点存储的元素
 139         final E element = l.item;
 140         // 获取尾结点的前驱结点
 141         final Node<E> prev = l.prev;
 142         // 删除尾结点
 143         l.item = null;
 144         l.prev = null; // help GC
 145         // 原来尾结点的前驱结点设为尾结点
 146         last = prev;
 147         // 如果原来尾结点的前驱结点为空,则首结点设为null
 148         // 否则,原来尾结点的前驱结点的后继结点设为null
 149         if (prev == null)
 150             first = null;
 151         else
 152             prev.next = null;
 153         size--;
 154         modCount++;
 155         // 返回原来尾结点存储的元素
 156         return element;
 157     }
 158 
 159     /**
 160      * 删除指定非空结点,返回存储的元素
 161      */
 162     E unlink(Node<E> x) {
 163         // 获取指定非空结点存储的元素
 164         final E element = x.item;
 165         // 获取指定非空结点的后继结点
 166         final Node<E> next = x.next;
 167         // 获取指定非空结点的前驱结点
 168         final Node<E> prev = x.prev;
 169 
 170         /**
 171          * 如果指定非空结点的前驱结点为空,则指定非空结点的后继结点设为首结点
 172          * 否则,指定非空结点的后继结点设为指定非空结点的前驱结点的后继结点,
 173          * 指定非空结点的前驱结点设为null
 174          */
 175         if (prev == null) {
 176             first = next;
 177         } else {
 178             prev.next = next;
 179             x.prev = null;
 180         }
 181 
 182         /**
 183          * 如果指定非空结点的后继结点为空,则指定非空结点的前驱结点设为尾结点
 184          * 否则,指定非空结点的前驱结点设为指定非空结点的后继结点的前驱结点,
 185          * 指定非空结点的后继结点设为null
 186          */
 187         if (next == null) {
 188             last = prev;
 189         } else {
 190             next.prev = prev;
 191             x.next = null;
 192         }
 193 
 194         // 指定非空结点存储的元素设为null
 195         x.item = null;
 196         size--;
 197         modCount++;
 198         // 返回指定非空结点存储的元素
 199         return element;
 200     }
 201 
 202     /**
 203      * 获取首结点存储的元素
 204      *
 205      * @return 首结点存储的元素
 206      * @throws NoSuchElementException 如果链表为空
 207      */
 208     public E getFirst() {
 209         // 获取首结点引用
 210         final Node<E> f = first;
 211         // 如果首结点为空,则抛出无该元素异常
 212         if (f == null)
 213             throw new NoSuchElementException();
 214         // 返回首结点存储的元素
 215         return f.item;
 216     }
 217 
 218     /**
 219      * 获取尾结点存储的元素
 220      *
 221      * @return 尾结点存储的元素
 222      * @throws NoSuchElementException 如果链表为空
 223      */
 224     public E getLast() {
 225         // 获取尾结点引用
 226         final Node<E> l = last;
 227         // 如果尾结点为空,则抛出无该元素异常
 228         if (l == null)
 229             throw new NoSuchElementException();
 230         // 返回尾结点存储的元素
 231         return l.item;
 232     }
 233 
 234     /**
 235      * 删除首结点,返回存储的元素
 236      *
 237      * @return 首结点存储的元素
 238      * @throws NoSuchElementException 如果链表为空
 239      */
 240     public E removeFirst() {
 241         // 获取首结点引用
 242         final Node<E> f = first;
 243         // 如果首结点为空,则抛出无该元素异常
 244         if (f == null)
 245             throw new NoSuchElementException();
 246         // 删除首结点,返回存储的元素
 247         return unlinkFirst(f);
 248     }
 249 
 250     /**
 251      * 删除尾结点,返回存储的元素
 252      *
 253      * @return 尾结点存储的元素
 254      * @throws NoSuchElementException 如果链表为空
 255      */
 256     public E removeLast() {
 257         // 获取尾结点引用
 258         final Node<E> l = last;
 259         // 如果尾结点为空,则抛出无该元素异常
 260         if (l == null)
 261             throw new NoSuchElementException();
 262         // 删除尾结点,返回存储的元素
 263         return unlinkLast(l);
 264     }
 265 
 266     /**
 267      * 头部插入指定元素
 268      *
 269      * @param e 要添加的元素
 270      */
 271     public void addFirst(E e) {
 272         // 通过头插法来插入指定元素
 273         linkFirst(e);
 274     }
 275 
 276     /**
 277      * 尾部插入指定元素,该方法等价于add()
 278      *
 279      * @param e the element to add
 280      */
 281     public void addLast(E e) {
 282         linkLast(e);
 283     }
 284 
 285     /**
 286      * 判断是否包含指定元素
 287      *
 288      * @param o 判断链表是否包含的元素
 289      * @return {@code true} 如果链表包含指定的元素
 290      */
 291     public boolean contains(Object o) {
 292         //返回指定元素的索引位置,不存在就返回-1,然后比较返回bool值
 293         return indexOf(o) != -1;
 294     }
 295 
 296     /**
 297      * 获取元素数量
 298      *
 299      * @return 元素数量
 300      */
 301     public int size() {
 302         return size;
 303     }
 304 
 305     /**
 306      * 插入指定元素,返回操作结果,默认添加到末尾作为最后一个元素
 307      *
 308      * @param e 要添加到此链表中的元素
 309      * @return {@code true} (as specified by {@link Collection#add})
 310      */
 311     public boolean add(E e) {
 312         // 通过尾插法来插入指定元素
 313         linkLast(e);
 314         return true;
 315     }
 316 
 317     /**
 318      * 删除指定元素,默认从first节点开始,删除第一次出现的那个元素
 319      *
 320      * @param o 要从该列表中删除的元素(如果存在)
 321      * @return {@code true} 如果这个列表包含指定的元素
 322      */
 323     public boolean remove(Object o) {
 324         //会根据是否为null分开处理。若值不是null,会用到对象的equals()方法
 325         if (o == null) {
 326             // 遍历链表,查找到指定元素后删除该结点,返回true
 327             for (Node<E> x = first; x != null; x = x.next) {
 328                 if (x.item == null) {
 329                     unlink(x);
 330                     return true;
 331                 }
 332             }
 333         } else {
 334             for (Node<E> x = first; x != null; x = x.next) {
 335                 if (o.equals(x.item)) {
 336                     unlink(x);
 337                     return true;
 338                 }
 339             }
 340         }
 341         // 查找失败
 342         return false;
 343     }
 344 
 345     /**
 346      * 将集合插入到链表尾部,即开始索引位置为size
 347      *
 348      * @param c 包含要添加到此链表中的元素的集合
 349      * @return {@code true} 如果该链表因添加而改变
 350      * @throws NullPointerException 如果指定的集合是空的
 351      */
 352     public boolean addAll(Collection<? extends E> c) {
 353         return addAll(size, c);
 354     }
 355 
 356     /**
 357      * 将集合从指定位置开始插入
 358      *
 359      * @param index 在哪个索引处前插入指定集合中的第一个元素
 360      * @param c     包含要添加到此链表中的元素的集合
 361      * @return {@code true} 如果该链表因添加而改变
 362      * @throws IndexOutOfBoundsException {@inheritDoc}
 363      * @throws NullPointerException      如果指定的集合是空的
 364      */
 365     public boolean addAll(int index, Collection<? extends E> c) {
 366         //检查索引是否正确(0<=index<=size)
 367         checkPositionIndex(index);
 368         //得到元素数组
 369         Object[] a = c.toArray();
 370         //得到元素个数
 371         int numNew = a.length;
 372         //若没有元素要添加,直接返回false
 373         if (numNew == 0)
 374             return false;
 375         //succ指向当前需要插入节点的位置,pred指向其前一个节点
 376         Node<E> pred, succ;
 377         //如果是在末尾开始添加,当前节点后一个节点初始化为null,前一个节点为尾节点
 378         if (index == size) {
 379             succ = null;
 380             pred = last;
 381         } else {    //如果不是从末尾开始添加,当前位置的节点为指定位置的节点,前一个节点为要添加的节点的前一个节点
 382             succ = node(index);
 383             pred = succ.prev;
 384         }
 385         //遍历数组并添加到列表中
 386         for (Object o : a) {
 387             @SuppressWarnings("unchecked") E e = (E) o;
 388             //将元素值e,前继节点pred“封装”为一个新节点newNode
 389             Node<E> newNode = new Node<>(pred, e, null);
 390             //如果原链表为null,则新插入的节点作为链表首节点
 391             if (pred == null)
 392                 first = newNode;
 393             else
 394                 pred.next = newNode;    //如果存在前节点,前节点会向后指向新加的节点
 395             pred = newNode; //pred指针向后移动,指向下一个需插入节点位置的前一个节点
 396         }
 397         //如果是从最后开始添加的,则最后添加的节点成为尾节点
 398         if (succ == null) {
 399             last = pred;
 400         } else {
 401             pred.next = succ;   //如果不是从最后开始添加的,则最后添加的节点向后指向之前得到的后续第一个节点
 402             succ.prev = pred;   //当前,后续的第一个节点也应改为向前指向最后一个添加的节点
 403         }
 404 
 405         size += numNew;
 406         modCount++;
 407         return true;
 408     }
 409 
 410     /**
 411      * 删除所有元素
 412      */
 413     public void clear() {
 414         //遍历链表,删除所有结点,方便gc回收垃圾
 415         for (Node<E> x = first; x != null; ) {
 416             Node<E> next = x.next;
 417             x.item = null;
 418             x.next = null;
 419             x.prev = null;
 420             x = next;
 421         }
 422         // 首尾结点置空
 423         first = last = null;
 424         // 元素数量置0
 425         size = 0;
 426         modCount++;
 427     }
 428 
 429 
 430     // 位置访问操作
 431 
 432     /**
 433      * 获取指定位置的元素
 434      *
 435      * @param index 要返回的元素的索引
 436      * @return 该链表中指定位置的元素
 437      * @throws IndexOutOfBoundsException {@inheritDoc}
 438      */
 439     public E get(int index) {
 440         // 判断指定位置是否合法
 441         checkElementIndex(index);
 442         // 返回指定位置的元素
 443         return node(index).item;
 444     }
 445 
 446     /**
 447      * 修改指定位置的元素,返回之前元素
 448      *
 449      * @param index   要替换的元素的索引
 450      * @param element 要存储在指定位置的元素
 451      * @return 之前在指定位置的元素
 452      * @throws IndexOutOfBoundsException {@inheritDoc}
 453      */
 454     public E set(int index, E element) {
 455         // 判断指定位置是否合法
 456         checkElementIndex(index);
 457         // 获取指定位置的结点
 458         Node<E> x = node(index);
 459         // 获取该结点存储的元素
 460         E oldVal = x.item;
 461         // 修改该结点存储的元素
 462         x.item = element;
 463         // 返回该结点存储的之前的元素
 464         return oldVal;
 465     }
 466 
 467     /**
 468      * 在指定位置前插入指定元素
 469      *
 470      * @param index   指定元素将被插入的索引
 471      * @param element 要插入的元素
 472      * @throws IndexOutOfBoundsException {@inheritDoc}
 473      */
 474     public void add(int index, E element) {
 475         // 判断指定位置是否合法
 476         checkPositionIndex(index);
 477         // 如果指定位置在尾部,则通过尾插法来插入指定元素
 478         if (index == size)
 479             linkLast(element);
 480         else        //如果指定位置不是尾部,则添加到指定位置前
 481             linkBefore(element, node(index));
 482     }
 483 
 484     /**
 485      * 删除指定位置的元素,返回之前元素
 486      *
 487      * @param index 要删除的元素的索引
 488      * @return 之前在指定位置的元素
 489      * @throws IndexOutOfBoundsException {@inheritDoc}
 490      */
 491     public E remove(int index) {
 492         // 判断指定位置是否合法
 493         checkElementIndex(index);
 494         // 删除指定位置的结点,返回之前元素
 495         return unlink(node(index));
 496     }
 497 
 498     /**
 499      * 判断指定位置是否合法
 500      */
 501     private boolean isElementIndex(int index) {
 502         return index >= 0 && index < size;
 503     }
 504 
 505     /**
 506      * 判断迭代器遍历时或插入元素时指定位置是否合法
 507      */
 508     private boolean isPositionIndex(int index) {
 509         return index >= 0 && index <= size;
 510     }
 511 
 512     /**
 513      * 获取越界异常信息
 514      */
 515     private String outOfBoundsMsg(int index) {
 516         return "Index: " + index + ", Size: " + size;
 517     }
 518 
 519     /**
 520      * 判断指定位置是否合法
 521      *
 522      * @param index
 523      */
 524     private void checkElementIndex(int index) {
 525         if (!isElementIndex(index))
 526             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 527     }
 528 
 529     /**
 530      * 判断指定位置是否合法
 531      *
 532      * @param index
 533      */
 534     private void checkPositionIndex(int index) {
 535         if (!isPositionIndex(index))
 536             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 537     }
 538 
 539     /**
 540      * 获取指定下标的结点,index从0开始
 541      */
 542     Node<E> node(int index) {
 543         // 如果指定下标<一半元素数量,则从首结点开始遍历
 544         // 否则,从尾结点开始遍历
 545         if (index < (size >> 1)) {
 546             Node<E> x = first;
 547             for (int i = 0; i < index; i++)
 548                 x = x.next;
 549             return x;
 550         } else {
 551             Node<E> x = last;
 552             for (int i = size - 1; i > index; i--)
 553                 x = x.prev;
 554             return x;
 555         }
 556     }
 557 
 558     // 查询操作
 559 
 560     /**
 561      * 获取顺序下首次出现指定元素的位置
 562      * 如果返回结果是-1,则表示不存在该元素
 563      *
 564      * @param o 要查找的元素
 565      * @return the index of the first occurrence of the specified element in
 566      * this list, or -1 if this list does not contain the element
 567      */
 568     public int indexOf(Object o) {
 569         int index = 0;
 570         if (o == null) {
 571             // 遍历链表,顺序查找指定元素
 572             for (Node<E> x = first; x != null; x = x.next) {
 573                 if (x.item == null)
 574                     return index;
 575                 index++;
 576             }
 577         } else {
 578             for (Node<E> x = first; x != null; x = x.next) {
 579                 if (o.equals(x.item))
 580                     return index;
 581                 index++;
 582             }
 583         }
 584         return -1;
 585     }
 586 
 587     /**
 588      * 获取逆序下首次出现指定元素的位置
 589      * 如果返回结果是-1,则表示不存在该元素
 590      *
 591      * @param o 要查找的元素
 592      * @return the index of the last occurrence of the specified element in
 593      * this list, or -1 if this list does not contain the element
 594      */
 595     public int lastIndexOf(Object o) {
 596         int index = size;
 597         if (o == null) {
 598             // 遍历链表,逆序查找指定元素
 599             for (Node<E> x = last; x != null; x = x.prev) {
 600                 index--;
 601                 if (x.item == null)
 602                     return index;
 603             }
 604         } else {
 605             for (Node<E> x = last; x != null; x = x.prev) {
 606                 index--;
 607                 if (o.equals(x.item))
 608                     return index;
 609             }
 610         }
 611         return -1;
 612     }
 613 
 614     // 队列操作
 615 
 616     /**
 617      * 出队(从前端),获得第一个元素,不存在会返回null,不会删除元素(节点)
 618      * 获取首元素
 619      *
 620      * @return the head of this list, or {@code null} 如果链表为空
 621      * @since 1.5
 622      */
 623     public E peek() {
 624         final Node<E> f = first;
 625         // 如果首结点为空,则返回null
 626         // 否则,返回首结点存储的元素
 627         return (f == null) ? null : f.item;
 628     }
 629 
 630     /**
 631      * 出队(从前端),不删除元素,若为null会抛出异常而不是返回null
 632      * 获取首元素
 633      *
 634      * @return the head of this list
 635      * @throws NoSuchElementException 如果链表为空
 636      * @since 1.5
 637      */
 638     public E element() {
 639         // 返回首结点存储的元素
 640         return getFirst();
 641     }
 642 
 643     /**
 644      * 出队(从前端),如果不存在会返回null,存在的话会返回值并移除这个元素(节点)
 645      * 获取并删除首元素
 646      *
 647      * @return the head of this list, or {@code null} 如果链表为空
 648      * @since 1.5
 649      */
 650     public E poll() {
 651         // 获取首结点引用
 652         final Node<E> f = first;
 653         // 如果首结点为空,则返回null
 654         // 否则,删除首结点,返回首结点存储的元素
 655         return (f == null) ? null : unlinkFirst(f);
 656     }
 657 
 658     /**
 659      * 出队(从前端),如果不存在会抛出异常而不是返回null,存在的话会返回值并移除这个元素(节点)
 660      * 获取并删除首元素
 661      *
 662      * @return the head of this list
 663      * @throws NoSuchElementException 如果链表为空
 664      * @since 1.5
 665      */
 666     public E remove() {
 667         // 删除首结点,返回首结点存储的元素
 668         return removeFirst();
 669     }
 670 
 671     /**
 672      * 入队(从后端),始终返回true
 673      *
 674      * @param e the element to add
 675      * @return {@code true} (as specified by {@link Queue#offer})
 676      * @since 1.5
 677      */
 678     public boolean offer(E e) {
 679         // 通过尾插法插入指定元素,返回操作结果
 680         return add(e);
 681     }
 682 
 683     // 双端队列操作
 684 
 685     /**
 686      * 入队(从前端),始终返回true
 687      *
 688      * @param e 要插入的元素
 689      * @return {@code true} (as specified by {@link Deque#offerFirst})
 690      * @since 1.6
 691      */
 692     public boolean offerFirst(E e) {
 693         //  通过尾插法来插入指定元素
 694         addFirst(e);
 695         return true;
 696     }
 697 
 698     /**
 699      * 入队(从后端),始终返回true
 700      *
 701      * @param e 要插入的元素
 702      * @return {@code true} (as specified by {@link Deque#offerLast})
 703      * @since 1.6
 704      */
 705     public boolean offerLast(E e) {
 706         // 通过尾插法来插入指定元素
 707         addLast(e);
 708         return true;
 709     }
 710 
 711     /**
 712      * 出队(从后端),获得最后一个元素,不存在会返回null,不会删除元素(节点)
 713      *
 714      * @return the first element of this list, or {@code null}
 715      * 如果链表为空
 716      * @since 1.6
 717      */
 718     public E peekFirst() {
 719         // 获取首结点引用
 720         final Node<E> f = first;
 721         // 如果首结点为空,则返回null
 722         // 否则,返回首结点存储的元素
 723         return (f == null) ? null : f.item;
 724     }
 725 
 726     /**
 727      * 出队(从后端),获得最后一个元素,不存在会返回null,不会删除元素(节点)
 728      *
 729      * @return the last element of this list, or {@code null}
 730      * 如果链表为空
 731      * @since 1.6
 732      */
 733     public E peekLast() {
 734         // 获取尾结点引用
 735         final Node<E> l = last;
 736         // 如果尾结点为空,则返回null
 737         // 否则,返回尾结点存储的元素
 738         return (l == null) ? null : l.item;
 739     }
 740 
 741     /**
 742      * 出队(从前端),获得第一个元素,不存在会返回null,会删除元素(节点)
 743      *
 744      * @return the first element of this list, or {@code null} if
 745      * this list is empty
 746      * @since 1.6
 747      */
 748     public E pollFirst() {
 749         // 获取首结点引用
 750         final Node<E> f = first;
 751         // 如果首结点为空,则返回null
 752         // 否则,删除首结点,返回首结点存储的元素
 753         return (f == null) ? null : unlinkFirst(f);
 754     }
 755 
 756     /**
 757      * 出队(从后端),获得最后一个元素,不存在会返回null,会删除元素(节点)
 758      *
 759      * @return the last element of this list, or {@code null} if
 760      * this list is empty
 761      * @since 1.6
 762      */
 763     public E pollLast() {
 764         // 获取尾结点引用
 765         final Node<E> l = last;
 766         // 如果尾结点为空,则返回null
 767         // 否则,删除尾结点,返回尾结点存储的元素
 768         return (l == null) ? null : unlinkLast(l);
 769     }
 770 
 771     /**
 772      * 入栈,从前面添加
 773      *
 774      * @param e the element to push
 775      * @since 1.6
 776      */
 777     public void push(E e) {
 778         // 通过头插法来插入指定元素
 779         addFirst(e);
 780     }
 781 
 782     /**
 783      * 出栈,返回栈顶元素,从前面移除(会删除)
 784      *
 785      * @return the element at the front of this list (which is the top
 786      * of the stack represented by this list)
 787      * @throws NoSuchElementException 如果链表为空
 788      * @since 1.6
 789      */
 790     public E pop() {
 791         // 删除首结点,返回首结点存储的元素
 792         return removeFirst();
 793     }
 794 
 795     /**
 796      * 删除顺序下首次出现的指定元素,返回操作结果
 797      *
 798      * @param o 要从该列表中删除的元素(如果存在)
 799      * @return {@code true} 如果链表包含指定的元素
 800      * @since 1.6
 801      */
 802     public boolean removeFirstOccurrence(Object o) {
 803         // 删除顺序下首次出现的指定元素对应的结点,返回操作结果
 804         return remove(o);
 805     }
 806 
 807     /**
 808      * 删除逆序下首次出现的指定元素,返回操作结果
 809      *
 810      * @param o 要从该列表中删除的元素(如果存在)
 811      * @return {@code true} 如果链表包含指定的元素
 812      * @since 1.6
 813      */
 814     public boolean removeLastOccurrence(Object o) {
 815         //由于LinkedList中允许存放null,因此下面通过两种情况来分别处理
 816         if (o == null) {
 817             // 遍历链表,从尾结点开始查找指定元素
 818             // 如果查找成功,删除该结点,返回true
 819             for (Node<E> x = last; x != null; x = x.prev) {
 820                 if (x.item == null) {
 821                     unlink(x);
 822                     return true;
 823                 }
 824             }
 825         } else {
 826             for (Node<E> x = last; x != null; x = x.prev) {
 827                 if (o.equals(x.item)) {
 828                     unlink(x);
 829                     return true;
 830                 }
 831             }
 832         }
 833         // 查找失败
 834         return false;
 835     }
 836 
 837     /**
 838      * Returns a list-iterator of the elements in this list (in proper
 839      * sequence), starting at the specified position in the list.
 840      * Obeys the general contract of {@code List.listIterator(int)}.<p>
 841      * <p>
 842      * The list-iterator is <i>fail-fast</i>: if the list is structurally
 843      * modified at any time after the Iterator is created, in any way except
 844      * through the list-iterator's own {@code remove} or {@code add}
 845      * methods, the list-iterator will throw a
 846      * {@code ConcurrentModificationException}.  Thus, in the face of
 847      * concurrent modification, the iterator fails quickly and cleanly, rather
 848      * than risking arbitrary, non-deterministic behavior at an undetermined
 849      * time in the future.
 850      *
 851      * @param index index of the first element to be returned from the
 852      *              list-iterator (by a call to {@code next})
 853      * @return a ListIterator of the elements in this list (in proper
 854      * sequence), starting at the specified position in the list
 855      * @throws IndexOutOfBoundsException {@inheritDoc}
 856      * @see List#listIterator(int)
 857      */
 858     public ListIterator<E> listIterator(int index) {
 859         checkPositionIndex(index);
 860         return new ListItr(index);
 861     }
 862 
 863     private class ListItr implements ListIterator<E> {
 864         private Node<E> lastReturned;
 865         private Node<E> next;
 866         private int nextIndex;
 867         private int expectedModCount = modCount;
 868 
 869         ListItr(int index) {
 870             // assert isPositionIndex(index);
 871             next = (index == size) ? null : node(index);
 872             nextIndex = index;
 873         }
 874 
 875         public boolean hasNext() {
 876             return nextIndex < size;
 877         }
 878 
 879         public E next() {
 880             checkForComodification();
 881             if (!hasNext())
 882                 throw new NoSuchElementException();
 883 
 884             lastReturned = next;
 885             next = next.next;
 886             nextIndex++;
 887             return lastReturned.item;
 888         }
 889 
 890         public boolean hasPrevious() {
 891             return nextIndex > 0;
 892         }
 893 
 894         public E previous() {
 895             checkForComodification();
 896             if (!hasPrevious())
 897                 throw new NoSuchElementException();
 898 
 899             lastReturned = next = (next == null) ? last : next.prev;
 900             nextIndex--;
 901             return lastReturned.item;
 902         }
 903 
 904         public int nextIndex() {
 905             return nextIndex;
 906         }
 907 
 908         public int previousIndex() {
 909             return nextIndex - 1;
 910         }
 911 
 912         public void remove() {
 913             checkForComodification();
 914             if (lastReturned == null)
 915                 throw new IllegalStateException();
 916 
 917             Node<E> lastNext = lastReturned.next;
 918             unlink(lastReturned);
 919             if (next == lastReturned)
 920                 next = lastNext;
 921             else
 922                 nextIndex--;
 923             lastReturned = null;
 924             expectedModCount++;
 925         }
 926 
 927         public void set(E e) {
 928             if (lastReturned == null)
 929                 throw new IllegalStateException();
 930             checkForComodification();
 931             lastReturned.item = e;
 932         }
 933 
 934         public void add(E e) {
 935             checkForComodification();
 936             lastReturned = null;
 937             if (next == null)
 938                 linkLast(e);
 939             else
 940                 linkBefore(e, next);
 941             nextIndex++;
 942             expectedModCount++;
 943         }
 944 
 945         public void forEachRemaining(Consumer<? super E> action) {
 946             Objects.requireNonNull(action);
 947             while (modCount == expectedModCount && nextIndex < size) {
 948                 action.accept(next.item);
 949                 lastReturned = next;
 950                 next = next.next;
 951                 nextIndex++;
 952             }
 953             checkForComodification();
 954         }
 955 
 956         final void checkForComodification() {
 957             if (modCount != expectedModCount)
 958                 throw new ConcurrentModificationException();
 959         }
 960     }
 961 
 962     /**
 963      * 节点的数据结构,包含前后节点的引用和当前节点
 964      *
 965      * @param <E>
 966      */
 967     private static class Node<E> {
 968         // 存储的元素
 969         E item;
 970         // 后继结点
 971         Node<E> next;
 972         // 前驱结点
 973         Node<E> prev;
 974 
 975         // 前驱结点、存储的元素和后继结点作为参数的构造方法
 976         Node(Node<E> prev, E element, Node<E> next) {
 977             this.item = element;
 978             this.next = next;
 979             this.prev = prev;
 980         }
 981     }
 982 
 983     /**
 984      * 返回迭代器
 985      *
 986      * @since 1.6
 987      */
 988     public Iterator<E> descendingIterator() {
 989         return new DescendingIterator();
 990     }
 991 
 992     /**
 993      * 因为采用链表实现,所以迭代器很简单
 994      */
 995     private class DescendingIterator implements Iterator<E> {
 996         private final ListItr itr = new ListItr(size());
 997 
 998         public boolean hasNext() {
 999             return itr.hasPrevious();
1000         }
1001 
1002         public E next() {
1003             return itr.previous();
1004         }
1005 
1006         public void remove() {
1007             itr.remove();
1008         }
1009     }
1010 
1011     /**
1012      * 父类克隆方法
1013      */
1014     @SuppressWarnings("unchecked")
1015     private LinkedList<E> superClone() {
1016         try {
1017             return (LinkedList<E>) super.clone();
1018         } catch (CloneNotSupportedException e) {
1019             throw new InternalError(e);
1020         }
1021     }
1022 
1023     /**
1024      * 克隆,浅拷贝
1025      *
1026      * @return a shallow copy of this {@code LinkedList} instance
1027      */
1028     public Object clone() {
1029         LinkedList<E> clone = superClone();
1030 
1031         // 链表初始化
1032         clone.first = clone.last = null;
1033         clone.size = 0;
1034         clone.modCount = 0;
1035 
1036         // 插入结点
1037         for (Node<E> x = first; x != null; x = x.next)
1038             clone.add(x.item);
1039         // 返回克隆后的对象引用
1040         return clone;
1041     }
1042 
1043     /**
1044      * Returns an array containing all of the elements in this list
1045      * in proper sequence (from first to last element).
1046      * <p>
1047      * <p>The returned array will be "safe" in that no references to it are
1048      * maintained by this list.  (In other words, this method must allocate
1049      * a new array).  The caller is thus free to modify the returned array.
1050      * <p>
1051      * <p>This method acts as bridge between array-based and collection-based
1052      * APIs.
1053      *
1054      * @return an array containing all of the elements in this list
1055      * in proper sequence
1056      */
1057     public Object[] toArray() {
1058         Object[] result = new Object[size];
1059         int i = 0;
1060         for (Node<E> x = first; x != null; x = x.next)
1061             result[i++] = x.item;
1062         return result;
1063     }
1064 
1065     /**
1066      * Returns an array containing all of the elements in this list in
1067      * proper sequence (from first to last element); the runtime type of
1068      * the returned array is that of the specified array.  If the list fits
1069      * in the specified array, it is returned therein.  Otherwise, a new
1070      * array is allocated with the runtime type of the specified array and
1071      * the size of this list.
1072      * <p>
1073      * <p>If the list fits in the specified array with room to spare (i.e.,
1074      * the array has more elements than the list), the element in the array
1075      * immediately following the end of the list is set to {@code null}.
1076      * (This is useful in determining the length of the list <i>only</i> if
1077      * the caller knows that the list does not contain any null elements.)
1078      * <p>
1079      * <p>Like the {@link #toArray()} method, this method acts as bridge between
1080      * array-based and collection-based APIs.  Further, this method allows
1081      * precise control over the runtime type of the output array, and may,
1082      * under certain circumstances, be used to save allocation costs.
1083      * <p>
1084      * <p>Suppose {@code x} is a list known to contain only strings.
1085      * The following code can be used to dump the list into a newly
1086      * allocated array of {@code String}:
1087      * <p>
1088      * <pre>
1089      *     String[] y = x.toArray(new String[0]);</pre>
1090      * <p>
1091      * Note that {@code toArray(new Object[0])} is identical in function to
1092      * {@code toArray()}.
1093      *
1094      * @param a the array into which the elements of the list are to
1095      *          be stored, if it is big enough; otherwise, a new array of the
1096      *          same runtime type is allocated for this purpose.
1097      * @return an array containing the elements of the list
1098      * @throws ArrayStoreException  if the runtime type of the specified array
1099      *                              is not a supertype of the runtime type of every element in
1100      *                              this list
1101      * @throws NullPointerException if the specified array is null
1102      */
1103     @SuppressWarnings("unchecked")
1104     public <T> T[] toArray(T[] a) {
1105         if (a.length < size)
1106             a = (T[]) java.lang.reflect.Array.newInstance(
1107                     a.getClass().getComponentType(), size);
1108         int i = 0;
1109         Object[] result = a;
1110         for (Node<E> x = first; x != null; x = x.next)
1111             result[i++] = x.item;
1112 
1113         if (a.length > size)
1114             a[size] = null;
1115 
1116         return a;
1117     }
1118 
1119     private static final long serialVersionUID = 876323262645176354L;
1120 
1121     /**
1122      * 序列化
1123      */
1124     private void writeObject(java.io.ObjectOutputStream s)
1125             throws java.io.IOException {
1126         // 默认序列化
1127         s.defaultWriteObject();
1128 
1129         // 写入元素数量
1130         s.writeInt(size);
1131 
1132         // 遍历链表,写入所有元素
1133         for (Node<E> x = first; x != null; x = x.next)
1134             s.writeObject(x.item);
1135     }
1136 
1137     /**
1138      * 反序列化
1139      */
1140     @SuppressWarnings("unchecked")
1141     private void readObject(java.io.ObjectInputStream s)
1142             throws java.io.IOException, ClassNotFoundException {
1143         // 默认反序列化
1144         s.defaultReadObject();
1145 
1146         // 读取元素数量
1147         int size = s.readInt();
1148 
1149         // 遍历链表,读取所有元素并尾部插入
1150         for (int i = 0; i < size; i++)
1151             linkLast((E) s.readObject());
1152     }
1153 
1154     /**
1155      * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
1156      * and <em>fail-fast</em> {@link Spliterator} over the elements in this
1157      * list.
1158      * <p>
1159      * <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and
1160      * {@link Spliterator#ORDERED}.  Overriding implementations should document
1161      * the reporting of additional characteristic values.
1162      *
1163      * @return a {@code Spliterator} over the elements in this list
1164      * @implNote The {@code Spliterator} additionally reports {@link Spliterator#SUBSIZED}
1165      * and implements {@code trySplit} to permit limited parallelism..
1166      * @since 1.8
1167      */
1168     @Override
1169     public Spliterator<E> spliterator() {
1170         return new LLSpliterator<E>(this, -1, 0);
1171     }
1172 
1173     /**
1174      * A customized variant of Spliterators.IteratorSpliterator
1175      */
1176     static final class LLSpliterator<E> implements Spliterator<E> {
1177         static final int BATCH_UNIT = 1 << 10;  // batch array size increment
1178         static final int MAX_BATCH = 1 << 25;  // max batch array size;
1179         final LinkedList<E> list; // null OK unless traversed
1180         Node<E> current;      // current node; null until initialized
1181         int est;              // size estimate; -1 until first needed
1182         int expectedModCount; // initialized when est set
1183         int batch;            // batch size for splits
1184 
1185         LLSpliterator(LinkedList<E> list, int est, int expectedModCount) {
1186             this.list = list;
1187             this.est = est;
1188             this.expectedModCount = expectedModCount;
1189         }
1190 
1191         final int getEst() {
1192             int s; // force initialization
1193             final LinkedList<E> lst;
1194             if ((s = est) < 0) {
1195                 if ((lst = list) == null)
1196                     s = est = 0;
1197                 else {
1198                     expectedModCount = lst.modCount;
1199                     current = lst.first;
1200                     s = est = lst.size;
1201                 }
1202             }
1203             return s;
1204         }
1205 
1206         public long estimateSize() {
1207             return (long) getEst();
1208         }
1209 
1210         public Spliterator<E> trySplit() {
1211             Node<E> p;
1212             int s = getEst();
1213             if (s > 1 && (p = current) != null) {
1214                 int n = batch + BATCH_UNIT;
1215                 if (n > s)
1216                     n = s;
1217                 if (n > MAX_BATCH)
1218                     n = MAX_BATCH;
1219                 Object[] a = new Object[n];
1220                 int j = 0;
1221                 do {
1222                     a[j++] = p.item;
1223                 } while ((p = p.next) != null && j < n);
1224                 current = p;
1225                 batch = j;
1226                 est = s - j;
1227                 return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
1228             }
1229             return null;
1230         }
1231 
1232         public void forEachRemaining(Consumer<? super E> action) {
1233             Node<E> p;
1234             int n;
1235             if (action == null) throw new NullPointerException();
1236             if ((n = getEst()) > 0 && (p = current) != null) {
1237                 current = null;
1238                 est = 0;
1239                 do {
1240                     E e = p.item;
1241                     p = p.next;
1242                     action.accept(e);
1243                 } while (p != null && --n > 0);
1244             }
1245             if (list.modCount != expectedModCount)
1246                 throw new ConcurrentModificationException();
1247         }
1248 
1249         public boolean tryAdvance(Consumer<? super E> action) {
1250             Node<E> p;
1251             if (action == null) throw new NullPointerException();
1252             if (getEst() > 0 && (p = current) != null) {
1253                 --est;
1254                 E e = p.item;
1255                 current = p.next;
1256                 action.accept(e);
1257                 if (list.modCount != expectedModCount)
1258                     throw new ConcurrentModificationException();
1259                 return true;
1260             }
1261             return false;
1262         }
1263 
1264         public int characteristics() {
1265             return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
1266         }
1267     }
1268 
1269 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏weixuqin 的专栏

数据结构学习笔记(线性表)

31850
来自专栏老马说编程

(43) 剖析TreeMap / 计算机程序的思维逻辑

40节介绍了HashMap,我们提到,HashMap有一个重要局限,键值对之间没有特定的顺序,我们还提到,Map接口有另一个重要的实现类TreeMap,在Tre...

22380
来自专栏10km的专栏

guava:java:java.util.Map和java.util.Set的Key类型转换

昨天写了一博客《java:java.util.Map和java.util.Set的Key类型转换》,主要是想实现以java.util.MapKey类型转换,今天...

23980
来自专栏向治洪

数据结构之线性表

基本概念 线性表(List):由零个或多个数据元素组成的有限序列。 特征: 1.线性表是一个序列。 2.0个元素构成的线性表是空表。 3.线性表中的第一个元素无...

21690
来自专栏恰童鞋骚年

数据结构基础温故-4.树与二叉树(下)

上面两篇我们了解了树的基本概念以及二叉树的遍历算法,还对二叉查找树进行了模拟实现。数学表达式求值是程序设计语言编译中的一个基本问题,表达式求值是栈应用的一个典型...

11220
来自专栏java小白

LinkedList源码详解

14220
来自专栏java一日一条

Java 容器&泛型(1):认识容器

容器是Java语言学习中重要的一部分。泥瓦匠我的感觉是刚开始挺难学的,但等你熟悉它,接触多了,也就“顺理成章”地知道了。Java的容器类主要由两个接口派生而出:...

13020
来自专栏数据结构与算法

2879 堆的判断

2879 堆的判断 时间限制: 1 s 空间限制: 32000 KB 题目等级 : 黄金 Gold 题目描述 Description 堆是一种常用...

32780
来自专栏LeetCode

LeetCode 46 & 47. Permutations I&II

Given a collection of distinct integers, return all possible permutations.

29600
来自专栏架构之路

Combination Sum II 组合数求和之2-Leetcode

原题: Given a collection of candidate numbers (C) and a target number (T), find al...

31550

扫码关注云+社区

领取腾讯云代金券