前言 主要是模拟Java中的LinkList的实现。
LinkedList概述 LinkedList是一种双向链表。
根据双向链表的特点，会有头节点和尾节点，并且节点之间是通过前驱指针和后继指针来维护关系的，而不是像数组那样通过位置下标来维护节点间关系的。所以既可以从头到尾遍历，又可以从尾到头遍历。
双向链表是包含两个指针的，pre指向前一个节点，next指向后一个节点，但是第一个节点head的pre指向null，最后一个节点的tail的next指向null。
LinkedList是一个继承于AbstractSequentialList，并实现了List接口和Deque接口的双端链表。
LinkedList底层的链表结构使它支持高效的插入和删除操作，另外它实现了Deque接口，使得LinkedList类也具有队列的特性(addFirst(),removeLast()…)，它可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
1 2 3 4 5 public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ ... }
LinkedList不是线程安全的，如果想使LinkedList变成线程安全的，可以调用静态类Collections类中的synchronizedList方法。
和ArrayList一样，类中的iterator()方法和listIterator()方法返回的iterators迭代器是fail-fast 的：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件，底层由modCount实现。
AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些骨干性函数。降低了List接口的复杂度。这些接口都是随机访问List的，LinkedList是双向链表（链表数据结构本身不具备随机访问的特性）；既然它继承于AbstractSequentialList，就相当于已经实现了“get(int index)这些接口”。
此外，我们若需要通过AbstractSequentialList自己实现一个列表，只需要扩展此类，并提供 listIterator() 和 size() 方法的实现即可。若要实现不可修改的列表，则需要实现列表迭代器的 hasNext、next、hasPrevious、previous 和 index 方法即可。
模拟LinkedList Queue 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 /** * @ClassName Queue * @Description 队列 * @Author HuangCanCan * @Date 2019/10/10 17:46 * @Version 1.0 **/ public interface Queue { /** * 将指定的元素值e插入此列表末尾 * * @param e * @return */ boolean offer(Object e); /** * 获取并移除此队列的头，如果此队列为空，则抛出NoSuchElementException异 * * @return */ Object remove(); /** * 获取并移除此队列的头，如果此队列为空，则返回 null * * @return */ Object poll(); /** * 获取但不移除此队列的头；如果此队列为空，则抛出NoSuchElementException异常 * * @return */ Object element(); /** * 获取但不移除此队列的头；如果此队列为空，则返回 null * * @return */ Object peek(); }
Deque 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 /** * @ClassName Deque * @Description 双端队列 * @Author HuangCanCan * @Date 2019/10/10 18:23 * @Version 1.0 **/ public interface Deque extends Queue { /** * 将指定的元素插入此双端队列的开头 * * @param e * @return */ boolean offerFirst(Object e); /** * 将指定的元素插入此双端队列的末尾 * * @param e * @return */ boolean offerLast(Object e); /** * 获取，但不移除此双端队列的第一个元素；如果此双端队列为空，则返回 null * * @return */ Object peekFirst(); /** * 获取，但不移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null * * @return */ Object peekLast(); /** * 获取并移除此双端队列的第一个元素；如果此双端队列为空，则返回 null * * @return */ Object pollFirst(); /** * 获取并移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null * * @return */ Object pollLast(); /** * 将一个元素推入此双端队列所表示的堆栈（换句话说，此双端队列的头部） * * @param e */ void push(Object e); /** * 从此双端队列所表示的堆栈中弹出一个元素（换句话说，移除并返回此双端队列的头部） */ Object pop(); /** * 从此双端队列移除第一次出现的指定元素，如果列表中不包含次元素，则没有任何改变 * * @param e * @return */ boolean removeFirstOccurrence(Object e); /** * 从此双端队列移除最后一次出现的指定元素,如果列表中不包含次元素，则没有任何改变 * * @param e * @return */ boolean removeLastOccurrence(Object e); }
LinkedList 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 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 import java.util.Collection; import java.util.Iterator; import java.util.NoSuchElementException; /** * @ClassName LinkedList * @Description 模拟LinkedList * @Author HuangCanCan * @Date 2019/10/8 17:18 * @Version 1.0 **/ public class LinkedList implements List, Iterable, Deque { /** * 指向头结点， * <p> * 不变的: (first == null && last == null) || (first.prev == null && first.data != null) */ private Node first; /** * 指向尾结点 * <p> * 不变的: (first == null && last == null) || (last.next == null && last.data != null) */ private Node last; /** * 结点个数 */ private int size; /** * 修改此列表的次数 * <p> * 用于在迭代器遍历时,用于判断在迭代过程中是否发生了修改操作,如果发生了修改,则抛出ConcurrentModificationException异常 */ private int modCount; public LinkedList() { } public LinkedList(Collection c) { this(); addAll(c); } @Override public int size() { return size; } @Override public Object get(int index) { //检查index范围 checkElementIndex(index); return getNode(index).data; } /** * 判断元素的索引是否越界 * * @param index */ private void checkElementIndex(int index) { if (index < 0 || index > size) { throw new RuntimeException("指针越界异常：" + index); } } @Override public boolean isEmpty() { return size == 0; } @Override public boolean contains(Object e) { // 判断列表中是否包含有元素值e，返回true当列表中至少存在一个元素值e return indexOf(e) >= 0; } /** * 正向查找，返回LinkedList中元素值Object data <strong>第一次</strong> 出现的位置，如果元素不存在，则返回-1 * * @param data * @return */ @Override public int indexOf(Object data) { //返回第一次出现的指定元素的索引 int index = 0; if (data == null) { for (Node x = first; x != null; x = x.next) { if (x.data == null) { return index; } index++; } } else { for (Node x = first; x != null; x = x.next) { if (data.equals(x.data)) { return index; } index++; } } return -1; } /** * 逆向查找，返回LinkedList中元素值Object e <strong>最后一次</strong>出现的位置，如果元素不存在，则返回-1 * * @param e * @return */ public int lastIndexOf(Object e) { int index = size; if (e == null) { for (Node x = last; x != null; x = x.pre) { index--; if (x.data == null) { return index; } } } else { for (Node x = last; x != null; x = x.pre) { index--; if (e.equals(x.data)) { return index; } } } return -1; } @Override public void add(int index, Object data) { //检查index范围 checkElementIndex(index); /* 判断此索引是否等于节点的个数，如果相等那就在尾部插入元素，否则在中间插入元素 */ if (index == size) { //尾插入 linkLast(data); } else { //中间插入 //获取指定索引位置的节点 Node node = getNode(index); //在指定索引位置的节点前插入新节点 linkBefore(data, node); } } /** * 在非空节点node之前插入新节点的值。中间操作 * * @param data 新节点的值 * @param node 当前节点 */ private void linkBefore(Object data, Node node) { Node pred = node.pre; // 构建一个新的节点 Node newNode = new Node(pred, data, node); //设置node的前驱节点为这个新的节点 node.pre = newNode; // 第一个节点head的pre指向null，最后一个节点的tail的next指向null //判断node是否是首节点（node.pre前驱节点为null） if (pred == null) { //表示node是首节点 //将newNode设置为首节点 first = newNode; } else { //node不是首节点,设置node的前驱节点的后续节点设置为新的节点 pred.next = newNode; } //节点个数加 1 size++; //修改此列表的次数加 1 modCount++; } /** * 将新节点的值添加到链表尾部。尾插入 * * @param data */ private void linkLast(Object data) { Node l = last; //构建一个新的节点 Node newNode = new Node(l, data, null); //将新节点作为尾节点 last = newNode; //如果原尾节点为null，即原链表为null，则链表首节点设置为newNode if (l == null) { first = newNode; } else { //否则，原尾节点的next设置为newNode l.next = newNode; } //节点个数加 1 size++; //修改此列表的次数加 1 modCount++; } /** * 在链表头部添加元素，头插入 * * @param data */ private void linkFirst(Object data) { Node f = first; // 构建一个新节点 Node newNode = new Node(null, data, f); //将新节点作为首节点 first = newNode; //如果原首节点为null，即原链表为null，则链表尾节点也设置为newNode if (f == null) { last = newNode; } else { //否则，原首节点的pre设置为newNode f.pre = newNode; } //节点个数加 1 size++; //修改此列表的次数加 1 modCount++; } /** * 返回指定索引位置的节点 * * @return */ private Node getNode(int index) { /* * *************【折半思想】************** * 当index < size/2 (size >> 1)时，从列表首节点向后查找 * 当 index >= size/2时，从列表尾节点向前查找 */ if (index < size / 2) { Node x = first; for (int i = 0; i < index; i++) { x = x.next; } return x; } else { Node x = last; for (int i = size - 1; i > index; i--) { x = x.pre; } return x; } } @Override public void add(Object data) { linkLast(data); } /** * 按照指定collection的迭代器所返回的元素顺序，将该collection中的所有元素添加到此链表的尾部。尾部插入 * <p> * 如果指定的集合添加到链表的尾部的过程中，集合被修改，则该插入过程的后果是不确定的。 * 一般这种情况发生在指定的集合为该链表的一部分，且其非空。 * * @param c */ public boolean addAll(Collection c) { return addAll(size, c); } /** * 从指定的位置开始，将指定collection中的所有元素插入到此链表中，新元素的顺序为指定collection的迭代器所返回的元素顺序 * * @param index * @param c */ public boolean addAll(int index, Collection c) { //检查index范围 checkElementIndex(index); Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) { return false; } Node pred, //指向需要插入节点的位置的前驱节点 succ;//需要插入节点的位置 if (index == size) { // 在链表表尾部插入集合元素 succ = null; pred = last; } else { // 在中间插入 // 获取指定索引位置的节点 succ = getNode(index); pred = succ.pre; } //指定collection中的所有元素依次插入到此链表中指定位置的过程 for (Object data : a) { // 构建新节点 Node newNode = new Node(pred, data, null); if (pred == null) { // 如果原链表为null，则新插入的节点作为链表首节点 first = newNode; } else { pred.next = newNode; } pred = newNode; // pred指针向后移动，指向下一个需插入节点位置的前一个节点 } //集合元素插入完成后，与原链表index位置后面的子链表链接起来 if (succ == null) { //说明之前是在列表尾部插入的集合元素 last = pred; //pred指向的是最后插入的那个节点 } else { // 否则，是在中间插入的集合元素 pred.next = succ; succ.pre = pred; } size += numNew; modCount++; return true; } /** * 在链表头部添加元素，头插入 * * @param data */ public void addFirst(Object data) { linkFirst(data); } /** * 在链表尾部添加元素，等价于add * * @param data */ public void addLast(Object data) { linkLast(data); } @Override public boolean addBefore(Object obj, Object e) { int index = indexOf(obj); if (index < 0) { return false; } add(index, e); return true; } @Override public boolean addAfter(Object obj, Object e) { int index = indexOf(obj); if (index < 0) { return false; } add(index + 1, e); return true; } @Override public Object remove(int index) { checkElementIndex(index); Node oldNode = getNode(index); // 获取指定索引处的节点，老节点 return unlink(oldNode); } /** * 删除非空节点node * * @param node 要删除的节点 * @return */ private Object unlink(Node node) { Object oldValue = node.data; Node prev = node.pre; //老节点的前驱节点 Node next = node.next; // 老节点的后续节点 // 更改老节点的前驱节点和后续节点的的关联 // prev.next = next; // next.pre = prev; /* 需要判断删除的元素是否是头节点和尾节点 */ if (prev == null) { //代表该节点是头节点 first = next; } else { // 不是头结点 prev.next = next; node.pre = null; } if (next == null) { //代表该节点是尾节点 last = prev; } else { // 不是尾结点 next.pre = prev; node.next = null; } node.data = null; // 使GC能够快速回收 size--; modCount++; return oldValue; } @Override public boolean remove(Object e) { //移除列表中首次出现的指定元素(如果存在)，LinkedList中允许存放重复的元素 /* * 第一种： */ // int index = indexOf(e);//返回元素e第一次出现的索引 // if (index < 0) { // return false; // } // remove(index); // return true; if (e == null) { for (Node x = first; x != null; x = x.next) { if (x.data == null) { unlink(x); return true; } } } else { for (Node x = first; x != null; x = x.next) { if (e.equals(x.data)) { unlink(x); return true; } } } return false; } /** * 替换指定索引位置节点的元素值，并返回旧值 * * @param index 索引 * @param element 元素的值 * @return */ private Object set(int index, Object element) { checkElementIndex(index); Node node = getNode(index); Object oldValue = node.data; node.data = element; return oldValue; } @Override public Object replace(int index, Object e) { return set(index, e); } @Override public String toString() { if (size == 0) { return "[]"; } StringBuilder builder = new StringBuilder("["); Node p = first; for (int i = 0; i < size; i++) { if (i != size - 1) { builder.append(p.data + ","); } else { builder.append(p.data); } //移动指针到下一个结点 p = p.next; } builder.append("]"); return builder.toString(); } @Override public Iterator iterator() { return new LinkedListIteraor(); } /** * 获取列表首节点元素值 */ public Object getFirst() { Node head = first; if (head == null) { throw new NoSuchElementException(); } return head.data; } /** * 获取列表尾节点元素值 */ public Object getLast() { Node tail = last; if (tail == null) { throw new NoSuchElementException(); } return tail.data; } /** * 移除首节点，并返回该节点的元素值 * * @return */ public Object removeFirst() { final Node f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } /** * 移除尾节点，并返回该节点的元素值 * * @return */ public Object removeLast() { final Node l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } /** * 删除非空的首节点f */ private Object unlinkFirst(Node f) { Object element = f.data; Node next = f.next; f.data = null; f.next = null; // help GC first = next; //将原首节点的next节点设置为首节点 if (next == null) //如果原链表只有一个节点，即原首节点，删除后，链表为null last = null; else next.pre = null; size--; modCount++; return element; } //删除非空的尾节点l private Object unlinkLast(Node l) { // assert l == last && l != null; final Object element = l.data; final Node prev = l.pre; l.data = null; l.pre = null; // help GC last = prev; //将原尾节点的prev节点设置为尾节点 if (prev == null) //如果原链表只有一个节点,则删除后，链表为null first = null; else prev.next = null; size--; modCount++; return element; } @Override public boolean offer(Object e) { // 将指定的元素值e插入此列表末尾 add(e); return true; } @Override public Object remove() { //获取并 移除 此队列的头，如果此队列为空，则抛出NoSuchElementException异 return removeFirst(); } @Override public Object poll() { //获取并 移除 此队列的头，如果此队列为空，则返回 null Node f = first; return f == null ? null : unlinkFirst(f); } @Override public Object element() { //获取但 不移除 此队列的头；如果此队列为空，则抛出NoSuchElementException异常 return getFirst(); } @Override public Object peek() { //获取但 不移除 此队列的头；如果此队列为空，则返回 null Node f = first; return f == null ? null : f.data; } @Override public boolean offerFirst(Object e) { addFirst(e); return true; } @Override public boolean offerLast(Object e) { addLast(e); return true; } @Override public Object peekFirst() { final Node f = first; return (f == null) ? null : f.data; } @Override public Object peekLast() { final Node l = last; return (l == null) ? null : l.data; } @Override public Object pollFirst() { final Node f = first; return (f == null) ? null : unlinkFirst(f); } @Override public Object pollLast() { final Node l = last; return (l == null) ? null : unlinkLast(l); } @Override public void push(Object e) { addFirst(e); } @Override public Object pop() { return removeFirst(); } @Override public boolean removeFirstOccurrence(Object e) { return remove(e); } @Override public boolean removeLastOccurrence(Object e) { if (e == null) { for (Node x = last; x != null; x = x.pre) { //逆向向前 if (x.data == null) { unlink(x); return true; } } } else { for (Node x = last; x != null; x = x.pre) { if (e.equals(x.data)) { unlink(x); return true; } } } return false; } public static class Node { /** * 要存储的数据 */ Object data; /** * 后续结点 */ Node next; /** * 前驱结点 */ Node pre; public Node(Node pre, Object data, Node next) { this.pre = pre; this.data = data; this.next = next; } } private class LinkedListIteraor implements Iterator { /** * 起始位置的后续节点 */ private Node current = first.next; /** * 记录此刻集合修改的总次数,之后会拿modCount再和此值作比较,如果不相等,说明在迭代过程中,集合发生了修改操作,则会抛出ConcurrentModification异常 */ private int expectedModCount = modCount; /** * 判断是否可以向后移动指针 */ private boolean canMove = false; @Override public boolean hasNext() { //后续节点与尾节点比较，如果不相等证明还有元素没有迭代完 return current != last; } @Override public Object next() { if (expectedModCount != modCount) { throw new java.util.ConcurrentModificationException(); } if (!hasNext()) { throw new java.util.NoSuchElementException(); } Object nextVal = current.data; current = current.next; canMove = true; return nextVal; } @Override public void remove() { if (expectedModCount != modCount) { throw new java.util.ConcurrentModificationException(); } if (!canMove) { throw new IllegalStateException(); } LinkedList.this.unlink(current.pre); canMove = false; expectedModCount++; } } }
遍历集合时进行修改或删除操作为什么会抛出ConcurrentModificationException？ 如一下代码：以上面的代码为例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 LinkedList linkedList = new LinkedList(); linkedList.add(1); linkedList.add(2); linkedList.add(3); linkedList.add(4); linkedList.add(5); linkedList.add(6); for (Object i : linkedList) { if ((Integer) i == 2) { linkedList.remove(2); } } 输出：Exception in thread "main" java.util.ConcurrentModificationException
原因：
因为增强的for循环内部使用的是iterator迭代器的方式进行遍历的,在遍历过程中,如果进行修改操作会导致exceptedModCount的值和modCount的值不相等.因此会抛出ConcurrentModificationException的异常。
正确的删除元素的方式应该是使用iterator()的方式遍历并进行删除操作,因为迭代器中的remove()方法和集合中的remove()有一点不同就是,前者删除后,会进行exceptedModCount++,因为不会抛出上面那个异常。
下面的代码不会抛出ConcurrentModificationException：
1 2 3 4 5 6 7 Iterator iterator = linkedList.iterator(); while (iterator.hasNext()) { Integer next = (Integer) iterator.next(); if (next == 2) { iterator.remove(); } }
总结 LinkedList是基于双向链表实现的，适合增删多查找少的场景。
LinkedList添加的元素，取时与添加时的顺序一致。因为向双向链表的尾部添加元素，然后按照头节点顺序遍历获取，所以一致。
LinkedList允许添加重复元素。
LinkedList不是线程安全的集合。
LinkedList允许添加null元素。
add方法插入元素是在双向链表的尾部插入。
get方法遍历双向链表，先判断下标靠近头节点还是尾节点，这样会减少多余的循环。
折半思想：当index < size/2 (size >> 1)时，从列表首节点向后查找；当 index >= size/2时，从列表尾节点向前查找
