JDK1.8 LinkedList源码解析

继ArrayList之后，记录一下阅读LinkedList源码的笔记。

还是有一些不太懂的地方，在代码中有标注，欢迎各位不吝赐教，感谢！

package java.util;import java.util.function.Consumer;public class LinkedListextends AbstractSequentialListimplements List, Deque, Cloneable, java.io.Serializable
{// transient不被持久化transient int size = 0;// 首节点transient Node first;// 尾节点transient Node last;/*** 空构造函数*/public LinkedList() {}/*** 根据Collection构造* @param  c Collection* @throws NullPointerException 当c==null时*/public LinkedList(Collection c) {this();addAll(c);}/*** 将e连接到第一个元素*/private void linkFirst(E e) {// 暂存首节点final Node f = first;// 创建一个新节点，该节点的前一个是e，后一个是ffinal Node newNode = new Node<>(null, e, f);// 新的首节点first = newNode;// f==null即队列之前没有元素if (f == null)// 最后一个节点即首节点last = newNode;else// 旧首节点的前一个为新节点f.prev = newNode;size++;modCount++;}/*** 将e连接到最后一个元素* 很多内容可以对比着LinkFirst看*/void linkLast(E e) {final Node l = last;final Node newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}/*** 将e插到非空节点succ前* 很多内容可以对比着LinkFirst看*/void linkBefore(E e, Node succ) {// assert succ != null;final Node pred = succ.prev;final Node newNode = new Node<>(pred, e, succ);succ.prev = newNode;if (pred == null)first = newNode;elsepred.next = newNode;size++;modCount++;}/*** 删除非空头节点*/private E unlinkFirst(Node f) {// assert f == first && f != null;final E element = f.item;final Node next = f.next;f.item = null;f.next = null; // help GC// 头节点后移first = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;}/*** 删除最后一个非空节点*/private E unlinkLast(Node l) {// assert l == last && l != null;final E element = l.item;final Node prev = l.prev;l.item = null;l.prev = null; // help GC// 尾节点last = prev;if (prev == null)first = null;elseprev.next = null;size--;modCount++;return element;}/*** 删除非空节点x*/E unlink(Node x) {// assert x != null;final E element = x.item;final Node next = x.next;final Node prev = x.prev;// x没有前驱节点if (prev == null) {// 头节点设为x的下一个节点first = next;} else {// x有前驱// 前驱节点的nect连接到x的nectprev.next = next;// x的prev置空x.prev = null;}// 实现没有节点的next连着x,x的prev也不连着任何节点// 逻辑同上if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}// 实现没有节点的prev连着x,x的next也不连着任何节点x.item = null;size--;modCount++;return element;}/*** 返回列表的第一个元素** @return* @throws NoSuchElementException 当列表为空时*/public E getFirst() {final Node f = first;if (f == null)throw new NoSuchElementException();return f.item;}/*** 返回列表的最后一个元素** @return* @throws NoSuchElementException 当列表为空时*/public E getLast() {final Node l = last;if (l == null)throw new NoSuchElementException();return l.item;}/*** 移除并返回列表第一个元素** @return* @throws NoSuchElementException*/public E removeFirst() {final Node f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);}/*** 移除并返回最后一个元素** @return* @throws NoSuchElementException*/public E removeLast() {final Node l = last;if (l == null)throw new NoSuchElementException();return unlinkLast(l);}/*** 将指定元素加到队首** @param e 待添加元素*/public void addFirst(E e) {linkFirst(e);}/*** 将指定元素加到队尾** @param e*/public void addLast(E e) {linkLast(e);}/*** 判断队列是否包含某元素** @param o* @return {@code true}*/public boolean contains(Object o) {return indexOf(o) != -1;}/*** 获取队列长度** @return*/public int size() {return size;}/*** 指定元素加到队尾** @param e* @return*/public boolean add(E e)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！