转载

基于jdk12的LinkedList源码阅读分析

LinkedList是Java集合框架中一个重要的实现,底层采用双向链表结构。和ArrayList一样,其也支持null值和重复值。它基于双向链表实现,就不用扩容了,可这也就是说,在维护结点的时候需要额外的空间存储前驱和后继的引用。在链表头部和尾部插入效率比较高,但是在指定位置插入就不太行了,原因是定位需要O(N)的时间复杂度,这也就是说查找的效率也不太行。最后,他是非线程安全集合类。

二、源码阅读部分

1.声明部分:

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
复制代码

可以看出它继承了AbstractSequentialList,查看AbstractSequentialList的源码,发现里面实现了增删查,很多都是基于iterator实现的。不用LinkedList自己重新实现了其中的一套方法,此外说一点,一般建议声明明队列的时候: Queue<T> queue = new LinkedList<>(); 而且建议用LinkedList实现Stack。因为原生的 Stack<T> stack = new Stack<>(); 有很多问题。

2.get方法:

public E get(int index) {
    //检查index是否合理
    checkElementIndex(index);
    return node(index).item;
}
Node<E> node(int index) {
    // assert isElementIndex(index);
    // 如果index是小于size的二分之一,这设计的很巧妙
    if (index < (size >> 1)) {
    	//则从前面从前往后开始找
    	Node<E> x = first;
    	for (int i = 0; i < index; i++)
    		x = x.next;
    	return x;
    } else {
    	//否则从后往前找
    	Node<E> x = last;
    	for (int i = size - 1; i > index; i--)
    		x = x.prev;
    	return x;
    }
}
复制代码

3.add方法:

//单参,在链表尾部插入元素
public boolean add(E e) {
    linkLast(e);
    return true;
}
//双参,在指定位置加入元素
public void add(int index, E element) {
    //老规矩先检查
    checkPositionIndex(index);
    //如果index就是size,就直接在末尾加
    if (index == size)
    	linkLast(element);
    //否则在指定位置之前插
    else
    	linkBefore(element, node(index));
}
/**
 * Links e as last element.
 * 将e插入最后一位
 */
void linkLast(E e) {
    final Node<E> l = last;
    //初始化新结点,指明前驱为l,后继为null
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    //如果链表为空,就直接插第一个
    if (l == null)
    	first = newNode;
    //前面把last给l了,则直接把新插入的元素插到l的后面
    else
    	l.next = newNode;
    //改变了原有数据结构,操作数加一
    size++;
    modCount++;
}

/**
 * Inserts element e before non-null Node succ.
 * 在非空结点之前插入e
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    //前提就是当前结点不空
    final Node<E> pred = succ.prev;
    //初始化新结点,指明前驱为pred,后继为当前结点succ
    final Node<E> newNode = new Node<>(pred, e, succ);
    //让succ的前驱指向新结点
    succ.prev = newNode;
    //如果pred为空,表明当前元素是第一个元素,或者当前链表为空
    if (pred == null)
    	first = newNode;
    //否则,succ的前驱的后继变成了新加入的结点
    else
    	pred.next = newNode;
    //改变了原有数据结构,操作数加一
    size++;
    modCount++;
}
复制代码

按照索引插入的过程大概就是:

  1. 创建新结点,并指明新结点的前驱和后继
  2. 将succ的前驱引用指向新结点
  3. 如果succ的前驱不空,则将succ的前驱的后继指向新结点

4.remove方法:

public boolean remove(Object o) {
    //前面说过,LinkedList里面是可以塞空的,所以这就先在里面找null,从前往后,只要找到第一个就删
    if (o == null) {
    	for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
            	unlink(x);
            	return true;
            }
    	}
    } else {
    	//否则就是找元素,找到就删
    	for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
            	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;
    
    //prev为null表示x第一个元素,直接让first指向x的后继就行
    if (prev == null) {
    	first = next;
    } else {
    	//否则就是x前驱的后继直接赋给x的后继,并让x的前驱引用为null,即释放x与前驱的连接
    	prev.next = next;
    	x.prev = null;
    }
    //next为null表示x为最后一个元素,直接让last指向x的前驱就行
    if (next == null) {
    	last = prev;
    } else {
    	//否则就是x后继的前驱直接赋给x的前驱,并让x的后继引用为null,即释放x与后继的连接
    	next.prev = prev;
    	x.next = null;
    }
    //清除x的数据,方便GC回收
    x.item = null;
    //改变数据结构
    size--;
    modCount++;
    return element;
}
复制代码

删除的时候断开连接的步骤小结(假设x既不是头也不是尾):

  1. 将待删除结点x的前驱的后继指向x的后继
  2. 将x的前驱引用置空,断开x与前驱的连接
  3. 将待删除结点x的后继的前驱指向x的前驱
  4. 将x的后继引用置空,断开x与后继的连接

三、写在最后

最后在讲一下基于LinkedList实现的Queue里面的一些常用方法,方便后续学习:

查看Queue接口,里面有这些方法:

在队尾增加元素: boolean add(E e);

在队尾增加元素: boolean offer(E e); //这个元素内部就是调用add方法,不再赘述

删除元素:

E remove();
//这个是Queue特有的remove
public E remove() {
    return removeFirst();
}
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
    	throw new NoSuchElementException();
    return unlinkFirst(f);
}
复制代码

出队并取得之: E poll();

//出队并且取得队首操作,不赘述了。
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
复制代码

取得队首元素: E element();

取得队首元素: E peek();

public E peek() {
    //和上面的区别就是这个peek可以在队空的情况下返回null,上面element()则直接报异常
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
复制代码
原文  https://juejin.im/post/5ebf47835188255b0166af26
正文到此结束
Loading...