基于JDK1.8的LinkedList剖析

我们从以下几个方面介绍LinkedList

 

Node节点

add方法

remove方法

get方法

(一)Node节点

 

 1 private static class Node<E> {

 2     E item;

 3     Node<E> next;

 4     Node<E> prev;

 5 

 6     Node(Node<E> prev, E element, Node<E> next) {

 7         this.item = element;

 8         this.next = next;

 9         this.prev = prev;

10     }

11 }

 

我们可以看出每个结点的组成部分有三个，一个是item数据，一个是prev前驱节点，一个是next后驱节点。

 

那么就可以知道LinkedList就是一个双向链表，每个节点既有指向后面的链表，也有指向前面的链表。

 

 

 

(二)add方法

 

1 //最基本的add方法，其他方法都是这个方法的变体

2 public boolean add(E e) {

3     linkLast(e);

4     return true;

5 }

直接调用了linkLast方法(也就是说，add方法是默认插入到链表的尾端)，然后return 一个 true。

 

 

 1 void linkLast(E e) {

 2     //将链表的last节点给l

 3     final Node<E> l = last;

 4     final Node<E> newNode = new Node<>(l, e, null);

 5     last = newNode;

 6     //如果是第一个节点

 7     if (l == null)

 8         first = newNode;

 9     //直接加入到尾节点的后面去

10     else

11         l.next = newNode;

12     size++;

13     modCount++;

14 }

 

我们知道add方法是在队列尾部添加元素，还是很容易的。首先用变量 l 指向最后一个节点，然后创建一个节点将它的prev指向 l ，这样newnode成为最后一个节点，使用last指向它，接着使 l 的next指向newnode，这种直接添加在队列尾部的方式还是很好理解的，我们重点看看如何添加在队列的中间位置。

 

 

 1 public void add(int index, E element) {

 2     //检查插入位置是否合法

 3     checkPositionIndex(index);

 4 

 5     //如果插入到最后，直接调用linkLast方法

 6     if (index == size)

 7         linkLast(element);

 8     //否则调用linkBefore

 9     else

10         linkBefore(element, node(index));

11 }

 

直接看注释。在调用linkBefore之前，调用了node(index)确定插入的位置

 

 

 1 Node<E> node(int index) {

 2     // assert isElementIndex(index);

 3 

 4     if (index < (size >> 1)) {

 5         Node<E> x = first;

 6         for (int i = 0; i < index; i++)

 7             x = x.next;

 8         return x;

 9     } else {

10         Node<E> x = last;

11         for (int i = size - 1; i > index; i--)

12             x = x.prev;

13         return x;

14     }

15 }

 

首先判断在前半部分还是在后半部分，然后一个for循环查找。时间复杂度O(n), 没办法，链表的缺点。

 

 

 1 void linkBefore(E e, Node<E> succ) {

 2     // assert succ != null;

 3     final Node<E> pred = succ.prev;

 4     final Node<E> newNode = new Node<>(pred, e, succ);

 5     succ.prev = newNode;

 6     if (pred == null)

 7         first = newNode;

 8     else

 9         pred.next = newNode;

10     size++;

11     modCount++;

12 }

 

 (三)remove方法

 

看完了添加，删除就显得简单些，无非分为两种，从头部删除，从中间删除，从头部删除和从尾部添加一样简单，从中间删除就是把此结点的前一个结点的next指向此结点的后一个结点，并把后一个结点的prev指向此节点的前一个结点，就是跳过此结点，最终将此结点null交给GC大人解决。为了篇幅，我们不再赘述。

 

 (四)get方法

 

由于LinkedList是链表，get方法必须扫描一遍链表，效率极低，所以谨慎使用。

 

 

1  public E get(int index) {

2      //检查是否超过链表长度或者负数

3     checkElementIndex(index);

4     //node节点我前面分析过了，O(n)复杂度

5     return node(index).item;

6 }

 

从源代码中我们可以清晰的看到，所谓的get方法也就是，调用node方法遍历整个链表，只是其中稍微做了点优化，如果index的值小于size/2从头部遍历，否则从尾部遍历。可见效率一样低下，所以我们以后写程序的时候，如果遇到数据量不大但是需要经常遍历查找的时候使用ArrayList而不是LinkedList，如果数据量非常的大，但是不是很经常的查找时使用LinkedList。

软件定制，软件开发，友情提醒。