从源码角度解析LinkedList特性

前两天讲到了ArrayList,那么按照套路今天应该到LinkedList了。那么我们现在就开始来扒开LinkedList的外衣,看看它的内在
从名字上我们就能够知道LinkedList它的底层是通过链表来存储数据的,来看看它的源码。
从源码角度解析LinkedList特性
从源码角度解析LinkedList特性
OK,没有毛病。我们来看看Node类,它是怎么存储的
从源码角度解析LinkedList特性
从源码角度解析LinkedList特性
从上面可以看出Node保存当前节点内容,以及前后节点的引用,典型的链表结构。我们再接着往下看LinkedList是如何添加元素的。
从源码角度解析LinkedList特性

从源码角度解析LinkedList特性
从源码角度解析LinkedList特性

从源码角度解析LinkedList特性
从这我们可以看到LinkedList它是双向的,我们可以从头部加入元素也可以从尾部加入元素,也可以从头部或者尾部取数据。联想下我们是不是用LinkedList实现堆栈,队列。好吧,扯远了。回归到我们最常用的add()。
从源码角度解析LinkedList特性
从源码角度解析LinkedList特性
在执行add()方法的时候,实际是执行了linkLast()方法,看名字就知道它是将我们新增的元素插入在链表的尾部,来看看linkLast()具体操作。
从源码角度解析LinkedList特性
从源码角度解析LinkedList特性
上面代码执行过后则是将当前要插入的元素加入了链表末尾。讲到这里我们再来回顾下昨天讲的ArrayList的插入,ArrayList插入时候首先要判断空间是否足够,如果不足够,则得要去扩容。到这里我们应该明白LinkedList的插入效率是要高于ArrayList的。
我们再接着来看看LinkedList的获取元素吧get()。
从源码角度解析LinkedList特性
从源码角度解析LinkedList特性
从源码角度解析LinkedList特性
从源码角度解析LinkedList特性
上面的index < (size >> 1)这行其实就是判断我们要查找的元素的index是在链表的前半段还是后半段。如果是在前半段则就从链表头开始查找,如果在后半段则就从链表尾部开始查找,以此达到减少查找次数。到这里大家应该能够清晰明了了,ArrayList的查找性能是要高于LinkedList。
我们再来看看LinkedList的其他插入方法
从源码角度解析LinkedList特性
从源码角度解析LinkedList特性
将元素e插入在succ元素前面。