1.LinkedList的构造器

• 无参构造器

/*** Constructs an empty list.*/
public LinkedList() {
}

• 构造Collection: 只要是 Collection 下的实现类都可以被 LinkedList 构造

// ? extends E: 只要是E的子类及E类型的类都可以使用

public LinkedList(Collection<? extends E> c) {// 调用无参构造器this();// 把集合 c 中的所有元素都添加到 LinkedList 的对象中addAll(c);
}

2.添加元素

• 头插: 把元素插入到链表的开头

public void addFirst(E e) {linkFirst(e);
}// 进行头插
private void linkFirst(E e) {// f 指向了头节点final Node<E> f = first;// 把 newNode 连接起来, newNode.next = f;final Node<E> newNode = new Node<>(null, e, f);// 让first 重新指向头节点first = newNode;// 判空if (f == null)last = newNode;elsef.prev = newNode; //连接起来后面的节点// 长度自增size++;modCount++;
}

• 尾插: 把元素添加到链表的最后

public boolean add(E e) {linkLast(e);return true;
}// 真正进行尾插的地方
void linkLast(E e) {// l 指向 last, 即链表的最后一个位置final Node<E> l = last;// newNode 绑定了 prev, 即 newNode.prev = l;final Node<E> newNode = new Node<>(l, e, null);// 更新尾结点; last 为空, 则更新 newNode 为尾结点last = newNode;// l 为空, 则说明链表中一个节点都没有if (l == null)first = newNode; // 更新为头节点elsel.next = newNode; // 把 l.next 指向 newNode;size++; // 链表长度 +1modCount++;
}

• 指定位置添加元素

public void add(int index, E element) {// 判断 index 是否合理checkPositionIndex(index);// index 为链表的长度if (index == size)linkLast(element); // 尾插else// node(index) 找到要插入的位置, 然后进行插入linkBefore(element, node(index));
}// succ 为要插入的位置, e 为要插入的值
// 尾插上面代码已经体现, 还要头插和任意位置插入未体现
void linkBefore(E e, Node<E> succ) {// assert succ != null;// pred 为插入位置的前一个final Node<E> pred = succ.prev;// 绑定 newNode.prev = pred, newNode.next = succ;final Node<E> newNode = new Node<>(pred, e, succ);// 前面已经知道了 newNode 的 prev 和 next, 还差 pred.next 和 succ.prev// 这个地方是绑定 succ.prevsucc.prev = newNode;// 说明要插入的节点是头节点if (pred == null)first = newNode; // 头插else// 任意位置, 绑定 pred.nextpred.next = newNode;size++; // 链表长度 +1modCount++;
}

• 指定位置添加另一个集合中的所有元素

public boolean addAll(Collection<? extends E> c) {// 从 0 位置开始把集合 c 中的元素全部添加到 LinkedList 的对象中return addAll(size, c);
}// 具体实现细节
public boolean addAll(int index, Collection<? extends E> c) {// 检查下标是否正常checkPositionIndex(index);// 把集合 c 转化成 Object 数组Object[] a = c.toArray();// 获取数组长度int numNew = a.length;// 空数组, 直接返回, 无需构造if (numNew == 0)return false;// 定义前驱和后继节点Node<E> pred, succ;// index 的值和 size 相同, 则需要尾插(? 因为 size 代表当前 LinkedList 对象的元素个数)if (index == size) {succ = null; pred = last; // pred 指向最后一个元素} else {// succ 指向要插入位置的节点succ = node(index);// pred 指向要插入位置节点的前驱节点pred = succ.prev;}// 循环遍历数组 a// 要插入的所有值, 在 pred 的后面插入, 在 succ 的前面插入for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o; // 强制类型转化, 把 Object 转为特定类型// 进行插入, 让 newNode.prev 指向 pred, newNode.next = null;Node<E> newNode = new Node<>(pred, e, null);// 若 pred 为空, 则说明 succ 是头节点, 即说明前面是进入了 else 语句if (pred == null)first = newNode; // 更新头节点elsepred.next = newNode; // 让 pred 和 newNode 相互连接(串起来)pred = newNode; // 更新节点, 继续插入}// succ 为空, 则说明是尾插法, 即进入了 size == index 内部if (succ == null) {// last 指向最后一个元素last = pred;} else {// 连接 pred 和 succ 节点, 把链表串起来pred.next = succ;succ.prev = pred;}// 添加长度size += numNew;modCount++;return true;
}

3.删除元素

• 头删: 把链表的最后一个元素删掉

public E removeFirst() {final Node<E> f = first;// 链表中一个节点也没有if (f == null)throw new NoSuchElementException();// unlinkFirst 方法中把头节点传过去return unlinkFirst(f);
}// 进行头删
private E unlinkFirst(Node<E> f) {// assert f == first && f != null;// 获取待删除节点的值final E element = f.item;// next 指向待删除节点的下一个节点final Node<E> next = f.next;// 把头节点的值置为 nullf.item = null;// 让 f(头节点)和后面的节点断开f.next = null; // help GC// 头节点重置first = next;// 说明 f 只有一个节点的情况if (next == null)last = null;elsenext.prev = null; // 把 next 的前驱也置为空, 彻底和 f 断开连接size--;modCount++;// 返回删除头节点的值return element;
}

• 尾删: 把链表的最后一个元素删掉

public E removeLast() {final Node<E> l = last;// 一个节点都不存在if (l == null)throw new NoSuchElementException();// 把尾结点传到 unlinkLast 方法中return unlinkLast(l);
}// 进行尾删
private E unlinkLast(Node<E> l) {// assert l == last && l != null;// 获取待删除节点的值final E element = l.item;// 获取待删除节点的前一个节点final Node<E> prev = l.prev;// 把待删除节点的值域和 next 域均置为空l.item = null;l.prev = null; // help GC// 把尾结点重置到待删除节点的前一个节点last = prev;// 只有一个节点的情况, 则 prev 为空, 则需要把头节点也置为空if (prev == null)first = null;else// 删掉最后一个节点, 即和链表前面的链表断开连接prev.next = null;size--;modCount++;return element;
}

• 删除指定节点: 那个节点值和传入要删除的值相同, 则删除该节点

// 删掉节点值与 o 相等的节点
public boolean remove(Object o) {// 判空if (o == null) {// 从头开始遍历节点for (Node<E> x = first; x != null; x = x.next) {// 判断那个的节点值为 null, 则删除这个节点if (x.item == null) {// 待删除的节点传到 unlink 中unlink(x);return true;}}} else { // 给的值不为 null// 遍历链表for (Node<E> x = first; x != null; x = x.next) {// 相等则删除if (o.equals(x.item)) {// 待删除的节点传到 unlink 中unlink(x);return true;}}}// 没有找到有相同的值return false;
}// 删除节点的逻辑
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 节点// 把x节点的值置为空x.item = null;size--;modCount++;return element;
}

 

4.获取/修改元素

• 获取index处的节点值

public E get(int index) {// 判断下标是否合法checkElementIndex(index);// 获取 index 处的值后, 返回return node(index).item;
}// 查找 index 处的节点值
Node<E> node(int index) {// assert isElementIndex(index);// 判断 index 是否在 size 的 1/2 内, 这个设计的目的是提高查找效率if (index < (size >> 1)) {// 定义查询节点Node<E> x = first;// 从头节点开始进行遍历, 一直到 index 处的节点位置for (int i = 0; i < index; i++)x = x.next;// 返回 index 处的节点的位置return x;} else {// 查找的节点在后半段Node<E> x = last;// 从尾结点向前遍历for (int i = size - 1; i > index; i--)x = x.prev;// 返回 index 处的节点return x;}
}

• 修改index处节点的节点值

public E set(int index, E element) {// 判断下标是否合法checkElementIndex(index);// 获取 index 处的节点值Node<E> x = node(index);// 获取原来节点的节点值E oldVal = x.item;// 把节点的节点值进行更新x.item = element;// 返回原先的节点值return oldVal;
}

 

5.获取元素第一次/最后一次出现的位置

• 获取元素第一次出现的位置

public int indexOf(Object o) {// 计数器, 用于获取目标节点处于那个下标int index = 0;if (o == null) {// 若是 o 为空, 也需要找到 null 在链表中的那个位置, 把这个位置返回for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)return index;index++;}} else {// 不为空, 那么就判断那个节点值和当前的 o 相等, 相等则返回对应的下标for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))return index;index++;}}// 没有找到的情况return -1;
}

• 获取元素最后一次出现的位置

public int lastIndexOf(Object o) {// 计数器, 下标从链表的最后一个位置开始int index = size;if (o == null) {// 若是 o 为空, 也需要找到 null 在链表中的那个位置, 把这个位置返回// 从尾向头开始进行遍历for (Node<E> x = last; x != null; x = x.prev) {index--;if (x.item == null)return index;}} else {// 不为空, 那么就判断那个节点值和当前的 o 相等, 相等则返回对应的下标for (Node<E> x = last; x != null; x = x.prev) {index--;if (o.equals(x.item))return index;}}// 链表中不存在对应的值return -1;
}

 

6.链表长度

public int size() {return size;
}// size 是 LinkedList 中的一个计数器, 用于记录链表长度的
transient int size = 0;

 

7.清空链表

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; ) {// 记录 x 的下一个节点Node<E> next = x.next;// 把 x 节点释放x.item = null;x.next = null;x.prev = null;// 指向下一个节点x = next;}// 头节点和尾结点置为 nullfirst = last = null;// 长度置为 0size = 0;modCount++;
}