基于JDK1.8的LinkedList剖析

2018-03-02 08:29:21来源:cnblogs.com作者:wenbochang人点击

分享

之前写了一篇ArrayList,那么今天就写一篇他的姊妹篇,LinkedList。

众所周知,ArrayList底层数据是数组,可以在O(1)的时间内get到数据,但删除和插入就要O(n)时间复杂度。

所以出现了链表,链表可以在O(1)的时间内插入,并且不会浪费内存,用多少就链接多少即可。

我们从以下几个方面介绍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     else11         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     else10         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。

相关文章

    无相关信息

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台