上文阅读直达车: 【震精】LinkedList源码竟然可以这样玩!! 注意源码版本为JDK1.8
在LinkedList中remove()和removeFirst()是相同的 在LinkedList中的删除其实就是通过修改上一个节点和指向下一个节点的引用完成的,可以看下面的图片:
我们可以看到把node6的prev指向清空然后把node3的next设置成空就完成了删除的操作。看一下JDK的源码实现:
调用removeFirst,在调用removeFirst中先获取头部节点,如果头节点为空就抛异常。
调用unlinkFirst
private E unlinkFirst(Node<E> f) { final E element = f.item; //next 为头结点的下一个节点 final Node<E> next = f.next; f.item = null; // 将节点的元素以及引用都设为 null,便于垃圾回收 f.next = null; //修改头结点为第二个节点 first = next; //如果第二个节点为空(当前链表只存在第一个元素) if (next == null) //那么尾节点也置为 null last = null; else //如果第二个节点不为空,那么将第二个节点的上一个引用置为 null next.prev = null; size--; modCount++; return element; }
我们看一下removeLast,从列表中删除最后一个元素
首先看到先获取了last最后一个元素,如果为空然后就抛异常 然后调用了unlinkLast
看到unlinkLast方法中有一个 help gc ,它的主要作用就是帮助GC来做垃圾回收。
private E unlinkLast(Node<E> l) { // assert l == last && l != null; final E element = l.item; final Node<E> prev = l.prev; l.item = null; //帮助GC垃圾回收 l.prev = null; //尾节点为倒数第二个节点 last = prev; //如果倒数第二个节点为null if (prev == null) //那么将节点也置为 null first = null; else prev.next = null; //如果倒数第二个节点不为空,那么将倒数第二个节点的下一个引用置为 null size--; modCount++; return element; }
同样执行了modCount++
根据索引来删除元素
//删除此列表中指定位置的元素 public E remove(int index) { //判断索引 index >= 0 && index <= size中时抛出IndexOutOfBoundsException异常 checkElementIndex(index); return unlink(node(index)); } 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) {//如果删除节点位置的上一个节点引用为null(表示删除第一个元素) first = next;//将头结点置为第一个元素的下一个节点 } else {//如果删除节点位置的上一个节点引用不为null prev.next = next;//将删除节点的上一个节点的下一个节点引用指向删除节点的下一个节点(去掉删除节点) x.prev = null;//删除节点的上一个节点引用置为null }
if (next == null) {//如果删除节点的下一个节点引用为null(表示删除最后一个节点) last = prev;//将尾节点置为删除节点的上一个节点 } else {//不是删除尾节点 next.prev = prev;//将删除节点的下一个节点的上一个节点的引用指向删除节点的上一个节点 x.next = null;//将删除节点的下一个节点引用置为null } //删除节点内容置为null,便于垃圾回收 x.item = null; size--; modCount++; return element; }
简单粗暴直接贴代码
public E set(int index, E element) { //检查索引是否合法否则IndexOutOfBoundsException异常 checkElementIndex(index); //获取指定索引的元素 Node<E> x = node(index); E oldVal = x.item; //将指定索引的元素替换成新的元素 x.item = element; /返回指定索引位置原来的元素 return oldVal;/ }
很简单
返回第一个元素
public E getFirst() { 获取头 final Node<E> f = first; 判断是否为空 if (f == null) throw new NoSuchElementException(); 元素返回 return f.item; }
返回最后一个元素
public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; }
返回指定索引元素
public E get(int index) { checkElementIndex(index); return node(index).item; }
暂时就这么多