LinkedList简介
(1)基于双向循环链表的结构，实现了Deque接口，可以用作堆栈、队列或双端队列使用； (2)实现为非同步的，即在多线程下是不安全的，单线程安全； (3)实现了Cloneable、Serializable，可以克隆与被序列化；JDK1.7-LinkedList源码详细分析
1 package java.util; 2 /** 3 * JDK1.7 4 * @author foolishbird_lmy 5 * 为了便于观察分析，我调整了一些方法的位置，相应的私有方法我都调整到了该方法的调用者下面，便于比较分析； 6 */ 7 8 public class LinkedList9 extends AbstractSequentialList 10 implements List , Deque , Cloneable, java.io.Serializable 11 { 12 //transient关键字的基本功能是，在实现了序列化的类中使用表示此变量不被序列化 13 14 transient int size = 0;//列表的长度 15 16 transient Node first;//定义一个节点指针引用，指向第一个节点，即头指针 17 18 transient Node last;//定义一个节点指针引用，指向最后一个节点，即尾指针 19 20 //空的构造函数 21 public LinkedList() { 22 } 23 24 //构造一个包含指定 collection 中的元素的列表，这些元素按其 collection 的迭代器返回的顺序排列 25 public LinkedList(Collection c) { 26 this(); 27 addAll(c);//将collection元素添加进列表 28 } 29 30 //在指定节点succ前面插入值为e的节点 31 void linkBefore(E e, Node succ) { 32 // assert succ != null; 33 final Node pred = succ.prev;//创建新的临时节点pred，指向succ的前驱节点 34 /*构造一个新的值为e的节点newNode，节点的前驱为pred，后驱next指向succ*/ 35 final Node newNode = new Node<>(pred, e, succ); 36 succ.prev = newNode; 37 if (pred == null)//如果要插入的点的前驱为空，即插在链表的头部 38 first = newNode; 39 else 40 pred.next = newNode; 41 size++; 42 modCount++; 43 } 44 45 //移除链表中的指定节点x，前提是x不为null，并返回节点的值 46 E unlink(Node x) { 47 // assert x != null; 48 final E element = x.item; 49 final Node next = x.next; 50 final Node prev = x.prev; 51 52 //判断x节点是否为头结点，如果是头结点，则前驱为null，否则将前驱的后继指向x的后继，即删除节点x操作 53 if (prev == null) { 54 first = next; 55 } else { 56 prev.next = next; 57 x.prev = null; 58 } 59 //判断x节点是否为尾结点，如果是尾结点，则后继为null，否则将x的前驱指向x后继的前驱，即连接起来 60 if (next == null) { 61 last = prev; 62 } else { 63 next.prev = prev; 64 x.next = null; 65 } 66 67 x.item = null; 68 size--; 69 modCount++; 70 return element; 71 } 72 73 //返回链表中的第一个节点的值 74 public E getFirst() { 75 final Node f = first; 76 if (f == null) 77 throw new NoSuchElementException(); 78 return f.item; 79 } 80 81 //返回链表中的最后一个节点的值 82 public E getLast() { 83 final Node l = last; 84 if (l == null) 85 throw new NoSuchElementException(); 86 return l.item; 87 } 88 89 /*移除第一个节点，并返回节点值*/ 90 public E removeFirst() { 91 final Node f = first; 92 if (f == null) 93 throw new NoSuchElementException(); 94 return unlinkFirst(f); 95 } 96 private E unlinkFirst(Node f) { 97 // f必须为头结点且不能为null 98 final E element = f.item;//保存节点的值 99 final Node next = f.next;//创建一个新的节点指向头结点的后继，即第二个节点100 f.item = null;101 f.next = null; // 然后设置为null，便于GC回收102 first = next;//更新把头指针指向第二个节点，现在已经是头结点，头指针是一直指向头结点的；103 if (next == null)//若链表只有一个节点，如果删除，则first=next=last=null104 last = null;105 else//删除头结点后，将原来的第二节点的前驱设置为null106 next.prev = null;107 size--;108 modCount++;109 return element;110 }111 112 /*移除最后一个节点，并返回节点值*/113 public E removeLast() {114 final Node l = last;115 if (l == null)116 throw new NoSuchElementException();117 return unlinkLast(l);118 }119 private E unlinkLast(Node l) {120 // l必须为尾结点且不能为null121 final E element = l.item;//保存节点的值122 final Node prev = l.prev;//创建一个新的节点指向尾结点的前驱，即倒数第二个节点123 l.item = null;124 l.prev = null; //然后设置为null，便于GC回收125 last = prev;//更新尾部指针，现在的尾节点为原来的倒数第二个节点，即prev指向的节点126 if (prev == null)//如果链表中只有一个节点，则删除后链表为空，first与last都指向null127 first = null;128 else//否则删除尾结点后，将原来的倒数第二节点的后继设置为null，因为已经是尾部节点了129 prev.next = null;130 size--;131 modCount++;132 return element;133 }134 135 //添加一个元素到链表的头*/136 public void addFirst(E e) {137 linkFirst(e);138 }139 /*添加一个元素到链表的头*/140 private void linkFirst(E e) {141 final Node f = first;142 //构造一个新的带值的节点newNode，节点的前驱为空，next指向f，即之前的头结点143 final Node newNode = new Node<>(null, e, f);144 first = newNode;//更新头结点的引用145 if (f == null)//若列表为空，则尾指针头指针都指向这个新添加的节点146 last = newNode;147 else148 f.prev = newNode;//否则将原来头结点的变为第二节点，头结点的后驱指向它149 size++;//更新长度150 modCount++;//链表修改的次数，在AbtractList中定义，主要是为了读取数据同步线程安全151 }152 153 //添加一个元素到链表的尾部154 public void addLast(E e) {155 linkLast(e);156 }157 //添加一个元素到链表的尾部，与上面的情况相反158 //这里注意一下源码，这个方法并没有与上面类似设置为private，经测试应该是忽略写掉了，外部是不能调用的；159 void linkLast(E e) {160 final Node l = last;161 final Node newNode = new Node<>(l, e, null);162 last = newNode;163 if (l == null)164 first = newNode;165 else166 l.next = newNode;167 size++;168 modCount++;169 }170 171 //判断是否包含某个指定元素172 public boolean contains(Object o) {173 return indexOf(o) != -1;//未找到返回-1，这里即返回false174 }175 176 //链表的长度177 public int size() {178 return size;179 }180 181 //将指定元素添加到此列表的结尾182 public boolean add(E e) {183 linkLast(e);//注意这里是可以添加null元素的，即无论你往尾部添加什么类型元素都会返回true184 return true;185 }186 187 //移除链表中首次出现的指定元素节点188 public boolean remove(Object o) {189 //注意null元素与普通元素是分开处理的190 if (o == null) {191 for (Node x = first; x != null; x = x.next) {192 if (x.item == null) { //比较地址193 unlink(x);//移除指定元素194 /*看到这里，我发现另一个问题，这里有必要说一下，就是空的元素与空值的元素195 例如：我们添加一个null的节点，意思是节点的值为null，但是并不代表这个节点是空，这个节点一样具有节点的性质有前驱有196 后继，只是一个特殊的节点而已，一样可以查找可以删除，与普通节点处理类似；197 但是一个空节点，只有你把它的前驱后继都设置为null之后，GC才会回收它，这才是一个空节点198 所以，unlink(x)方法在判断参数是否为空时，是判断是否这个节点为空节点，而不是null值节点*/199 return true;200 }201 }202 } else {203 for (Node x = first; x != null; x = x.next) {204 if (o.equals(x.item)) { //比较内容205 unlink(x);206 return true;207 }208 }209 }210 return false;211 }212 213 //将collection元素添加进列表尾部214 public boolean addAll(Collection c) {215 return addAll(size, c);216 }217 218 //将collection元素添加进列表的指定位置index处219 public boolean addAll(int index, Collection c) {220 checkPositionIndex(index);221 222 Object[] a = c.toArray();223 int numNew = a.length;224 if (numNew == 0)225 return false;226 227 Node pred, succ;228 if (index == size) { //插入到尾部229 succ = null;230 pred = last;231 } else { //创建两个节点指针，一个指向要插入的节点位置，一个指向此节点的前驱节点232 succ = node(index);233 pred = succ.prev;234 }235 236 //循环创建节点，并插入到链表中237 for (Object o : a) {238 @SuppressWarnings("unchecked") E e = (E) o;239 Node newNode = new Node<>(pred, e, null);240 if (pred == null)//刚好是从头结点开始插入241 first = newNode;242 else//插入节点的位置为pred的后继节点243 pred.next = newNode;244 pred = newNode;//每次将pred指向插入的新节点245 }246 247 if (succ == null) { //刚好从尾部插入248 last = pred;//更新尾部指针，因为pred每次都指向新插入的节点，所以最后pred是指向尾部249 } else { //将插入的链表连接起来250 pred.next = succ;251 succ.prev = pred;252 }253 254 size += numNew;255 modCount++;256 return true;257 }258 259 //清除链表中的所有元素260 public void clear() {261 for (Node x = first; x != null; ) {262 Node next = x.next;263 x.item = null;264 x.next = null;265 x.prev = null;266 x = next;267 }268 first = last = null;//最后将指针清空269 size = 0;270 modCount++;271 }272 273 //返回链表中的指定位置元素的值274 public E get(int index) {275 checkElementIndex(index);//检查范围越界276 return node(index).item;277 }278 279 /*给链表中指定位置设置新的值*/280 public E set(int index, E element) {281 checkElementIndex(index);282 Node x = node(index);283 E oldVal = x.item;284 x.item = element;285 return oldVal;//并返回节点的旧值286 }287 288 /*在链表指定位置插入新的节点*/289 public void add(int index, E element) {290 checkPositionIndex(index);291 292 if (index == size)293 linkLast(element);294 else295 linkBefore(element, node(index));296 }297 298 //移除指定位置元素299 public E remove(int index) {300 checkElementIndex(index);301 return unlink(node(index));302 }303 304 //判断下标是否越界，用于遍历链表305 private boolean isElementIndex(int index) {306 return index >= 0 && index < size;307 }308 309 //判断下标是否越界，用于插入、删除，与上面区别在于可以在链表尾部插入删除310 private boolean isPositionIndex(int index) {311 return index >= 0 && index <= size;312 }313 314 //主要用于异常提示信息315 private String outOfBoundsMsg(int index) {316 return "Index: "+index+", Size: "+size;317 }318 319 private void checkElementIndex(int index) {320 if (!isElementIndex(index))321 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));322 }323 324 private void checkPositionIndex(int index) {325 if (!isPositionIndex(index))326 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));327 }328 329 /*这个有点意思，功能是返回指定位置的节点*/330 Node node(int index) {331 /*为了提高查找效率，充分利用双向链表的特性，查找的时候特地设计成为分为两部分，332 一部分是前半部分，小于size/2，从前开始往后遍历；*/333 if (index < (size >> 1)) {334 Node x = first;335 for (int i = 0; i < index; i++)336 x = x.next;337 return x;338 } else {339 //另一部分是后半部分，从后开始往前遍历340 Node x = last;341 for (int i = size - 1; i > index; i--)342 x = x.prev;343 return x;344 }345 }346 347 // Search Operations348 349 //从前开始往后遍历，查找指定元素的索引值，返回第一次出现的下标位置350 public int indexOf(Object o) {351 int index = 0;352 //也是分为两个部分查找，一个是null值节点，一个是普通节点353 if (o == null) {354 for (Node x = first; x != null; x = x.next) {355 if (x.item == null)356 return index;357 index++;358 }359 } else {360 for (Node x = first; x != null; x = x.next) {361 if (o.equals(x.item))362 return index;363 index++;364 }365 }366 return -1;//没有查找到返回-1367 }368 369 //从后开始往前遍历，查找指定元素的索引值，返回第一次出现的下标位置370 public int lastIndexOf(Object o) {371 int index = size;372 if (o == null) {373 for (Node x = last; x != null; x = x.prev) {374 index--;375 if (x.item == null)376 return index;377 }378 } else {379 for (Node x = last; x != null; x = x.prev) {380 index--;381 if (o.equals(x.item))382 return index;383 }384 }385 return -1;386 }387 388 // 队列操作，LinkedList可以当作双向队列操作389 390 //返回列表中第一个元素，没有删除391 public E peek() {392 final Node f = first;393 return (f == null) ? null : f.item;394 }395 396 /*获取列表中第一个元素，这个方法与上面的唯一区别是当链表为空时，此方法会抛出NoSuchElementException 异常，397 而peek()方法会返回null*/398 public E element() {399 return getFirst();400 }401 402 //返回列表中第一个元素，并且删除操作403 public E poll() {404 final Node f = first;405 return (f == null) ? null : unlinkFirst(f);406 }407 408 //返回列表中第一个元素，并且删除操作，与上面方法类似，当链表为空时会抛出异常，poll方法会返回null409 public E remove() {410 return removeFirst();411 }412 413 //在链表的尾部添加指定节点414 public boolean offer(E e) {415 return add(e);416 }417 418 //在链表的头添加指定节点419 public boolean offerFirst(E e) {420 addFirst(e);421 return true;422 }423 //在链表的尾部添加指定节点，这个方法我仔细对比了以下与offer的内部调用，发现都是用的linkLast添加到尾部424 //所以实质上没有什么区别，这个是1.6版本方法，上面是1.5的425 public boolean offerLast(E e) {426 addLast(e);427 return true;428 }429 430 //获取列表中第一个元素，如果链表为null，则返回null，与getFirst方法区别是会抛出异常431 public E peekFirst() {432 final Node f = first;433 return (f == null) ? null : f.item;434 }435 436 //获取列表中最后一个元素，如果链表为null，则返回null，与getLast方法区别是会抛出异常437 public E peekLast() {438 final Node l = last;439 return (l == null) ? null : l.item;440 }441 442 //获取并且删除链表中第一个元素443 public E pollFirst() {444 final Node f = first;445 return (f == null) ? null : unlinkFirst(f);446 }447 448 //获取并且删除链表中最后一个元素449 public E pollLast() {450 final Node l = last;451 return (l == null) ? null : unlinkLast(l);452 }453 454 /*下面的方法是执行堆栈操作*/455 //将元素推入此列表所表示的堆栈，即链表的开头，从表头开始添加元素456 public void push(E e) {457 addFirst(e);458 }459 460 //从堆栈中弹出元素，即从链表的开头开始取出元素，删除链表中的元素并返回461 public E pop() {462 return removeFirst();463 }464 465 //从此列表中移除第一次出现的指定元素(从头开始遍历),如果列表不包含该元素，则不作更改。466 public boolean removeFirstOccurrence(Object o) {467 return remove(o);468 }469 470 //从此列表中移除第一次出现的指定元素(从尾开始遍历),如果列表不包含该元素，则不作更改。471 public boolean removeLastOccurrence(Object o) {472 if (o == null) {473 for (Node x = last; x != null; x = x.prev) {474 if (x.item == null) {475 unlink(x);//删除操作476 return true;477 }478 }479 } else {480 for (Node x = last; x != null; x = x.prev) {481 if (o.equals(x.item)) {482 unlink(x);//删除操作483 return true;484 }485 }486 }487 return false;488 }489 490 491 public ListIterator listIterator(int index) {492 checkPositionIndex(index);493 return new ListItr(index);494 }495 496 //内部类ListItr，List迭代器497 private class ListItr implements ListIterator {498 private Node lastReturned = null;//上一次迭代返回的节点499 private Node next;//下一个节点500 private int nextIndex;//下一个节点的下标索引值501 //期望的计数值502 private int expectedModCount = modCount;503 //构造函数，从index索引位置开始往后迭代元素504 ListItr(int index) {505 /*三目运算符，如果index == size为true，则next=null，否则next=node(index)*/506 507 next = (index == size) ? null : node(index);508 nextIndex = index;509 }510 //迭代时链表中是否为空，还有后继节点511 public boolean hasNext() {512 return nextIndex < size;513 }514 //从前开始往后遍历，迭代取出节点元素515 public E next() {516 checkForComodification();517 if (!hasNext())518 throw new NoSuchElementException();519 520 lastReturned = next;//每次记录返回的节点521 next = next.next;522 nextIndex++;523 return lastReturned.item;524 }525 //用于从后往前迭代526 public boolean hasPrevious() {527 return nextIndex > 0;528 }529 //返回前驱节点530 public E previous() {531 checkForComodification();532 if (!hasPrevious())533 throw new NoSuchElementException();534 535 lastReturned = next = (next == null) ? last : next.prev;536 nextIndex--;537 return lastReturned.item;538 }539 //返回下一个节点的下标索引值540 public int nextIndex() {541 return nextIndex;542 }543 //返回上一个节点的下标索引值544 public int previousIndex() {545 return nextIndex - 1;546 }547 //删除链表中的当前节点548 public void remove() {549 checkForComodification();550 if (lastReturned == null)551 throw new IllegalStateException();552 553 Node lastNext = lastReturned.next;554 unlink(lastReturned);555 if (next == lastReturned)556 next = lastNext;557 else558 nextIndex--;559 lastReturned = null;560 expectedModCount++;561 }562 //设置当前节点值为e563 public void set(E e) {564 if (lastReturned == null)565 throw new IllegalStateException();566 checkForComodification();567 lastReturned.item = e;568 }569 //将e节点添加到当前节点的前面570 public void add(E e) {571 checkForComodification();572 lastReturned = null;573 if (next == null)574 linkLast(e);575 else576 linkBefore(e, next);577 nextIndex++;578 expectedModCount++;579 }580 581 final void checkForComodification() {582 if (modCount != expectedModCount)583 throw new ConcurrentModificationException();584 }585 }586 //链表中节点的构造587 private static class Node {588 E item;//节点的值589 Node next;//节点的后继590 Node prev;//节点的前驱591 592 Node(Node prev, E element, Node next) {593 this.item = element;594 this.next = next;595 this.prev = prev;596 }597 }598 599 /**600 * 单例设计模式，获取DescendingIterator的一个实例601 */602 public Iterator descendingIterator() {603 return new DescendingIterator();604 }605 606 /**607 * 反向迭代器，用于从后往前迭代608 */609 private class DescendingIterator implements Iterator {610 private final ListItr itr = new ListItr(size());611 public boolean hasNext() {612 return itr.hasPrevious();//是否有前驱节点，其实是判断是否到了链表头613 }614 public E next() { //获取下一个节点，即获取前驱节点615 return itr.previous();616 }617 public void remove() { //删除当前节点618 itr.remove();619 }620 }621 622 @SuppressWarnings("unchecked")623 private LinkedList superClone() {624 try {625 return (LinkedList ) super.clone();626 } catch (CloneNotSupportedException e) {627 throw new InternalError();628 }629 }630 631 //克隆一个链表，执行的是浅克隆，并没有元素的真实复制，只是把创建一个引用指向已经存在的元素节点；632 public Object clone() {633 LinkedList clone = superClone();634 635 // Put clone into "virgin" state636 clone.first = clone.last = null;637 clone.size = 0;638 clone.modCount = 0;639 640 // Initialize clone with our elements641 for (Node x = first; x != null; x = x.next)642 clone.add(x.item);643 644 return clone;645 }646 647 //返回以适当顺序（从第一个元素到最后一个元素）包含此列表中所有元素的数组。 648 public Object[] toArray() {649 Object[] result = new Object[size];650 int i = 0;651 for (Node x = first; x != null; x = x.next)652 result[i++] = x.item;653 return result;654 }655 656 657 /*返回以适当顺序（从第一个元素到最后一个元素）包含此列表中所有元素的数组；返回数组的运行时类型为指定数组的类型。658 如果指定数组能容纳列表，则在其中返回该列表。否则，分配具有指定数组的运行时类型和此列表大小的新数组。 659 如果指定数组能容纳列表，并有剩余空间（即数组比列表元素多），则紧跟在列表末尾的数组元素会被设置为 null660 */661 public T[] toArray(T[] a) {662 if (a.length < size)//如果指定的数组长度不够，则通过反射技术创建一个相同类型的以实际链表长度size的数组663 a = (T[])java.lang.reflect.Array.newInstance(664 a.getClass().getComponentType(), size);665 int i = 0;666 Object[] result = a;667 //遍历链表，将链表的值放进数组之中668 for (Node x = first; x != null; x = x.next)669 result[i++] = x.item;670 671 if (a.length > size)672 a[size] = null;//如果数组的长度本来就大于链表的长度，则后续的数组元素值为null673 674 return a;675 }676 677 private static final long serialVersionUID = 876323262645176354L;678 //序列化写入函数，将链表中的元素都写入到输入流中679 private void writeObject(java.io.ObjectOutputStream s)680 throws java.io.IOException {681 // Write out any hidden serialization magic682 s.defaultWriteObject();683 684 // 写入容量685 s.writeInt(size);686 687 // 写入所有的节点值688 for (Node x = first; x != null; x = x.next)689 s.writeObject(x.item);690 }691 692 693 //序列化读取函数，将链表中的元素从输入流中读取出来694 private void readObject(java.io.ObjectInputStream s)695 throws java.io.IOException, ClassNotFoundException {696 // Read in any hidden serialization magic697 s.defaultReadObject();698 699 // Read in size700 int size = s.readInt();701 702 // 读取所有的元素，并且从尾部添加到链表中703 for (int i = 0; i < size; i++)704 linkLast((E)s.readObject());705 }706 }
总结一下：
1、通过以前版本的JDK源码比较，1.7版本的LinkedList实现双向循环链表时，没有了头节点这个概念，即头结点就是第一个节点也会存放元素，但是添加了一个last指针指向最后一个节点，这有可以很方便的直接取出最后的节点，也能直接从后往前进行迭代。
2、构造函数两个，一个无参数，构造的是一个空的链表，一个是以指定容器列表中的元素为参数构造链表，即从后插入链表，没有头节点这个概念。
3、与ArrayList一样，集合中允许null值元素，但是在查找、删除null值元素的操作是与普通元素分开处理。主要是比较的方式不同，null值比较是用==，例如x.item == null，普通元素比较直接比较值例如o.equals(x.item)。
4、LinkedList是链表结构，理论上容量是与内存挂钩，不存在容量不足问题，只要内存足够大。
5、仔细看源码中329行，按下标索引查找节点方法很有意思，它为了提高查找的效率，充分利用双向链表的特性，查找的时候特地设计成为分为两部分，一部分是前半部分，小于size/2，从前开始往后遍历，另外一部分从后往前遍历，充分利用指向链表前后两端的指针，将查找范围从开始就缩小到了原来的一半，不过还是属于遍历列表，效率很慢。。
6、基本的链表特性，查找要遍历链表效率低，但是删除添加元素只需要移动指针效率较高。
7、LinkedList虽然是一个链表，但是是双向循环链表结构，可以当前队列、栈同时使用，功能还是比较强大的。