从源码解析LinkedList集合

     上篇文章我们介绍了ArrayList类的基本的使用及其内部的一些方法的实现原理,但是这种集合类型虽然可以随机访问数据,但是如果需要删除中间的元素就需要移动一半的元素的位置,效率低下。并且它内部是用数组来实现的,数组要求连续的存储空间,当数据量大的时候就极耗内存。本篇我们介绍使用链表实现的集合LinkedList,这种类型不需要连续的存储空间,删除数据方便,但是不支持随机访问并且查找效率低下,几乎是ArrayList的对立面。我们将从以下方面介绍此类型:

  • 超接口和超类的基本方法及实现
  • 内部组成细节
  • add方法的源码解析
  • remove方法的源码解析
  • 低效的get方法
  • LinkedList的应用场景 一、了解LinkedList的超接口      我们首先看到LinkedList实现了接口Deque,而这个接口又实现了Queue接口,那我们就从Queue接口看起。
public interface Queue<E> extends Collection<E> {
    boolean add(E e);//添加元素
    boolean offer(E e);//添加元素
    E remove();//删除元素
    E poll();//删除元素
    E element();//返回头部元素
    E peek();//返回头部元素
}

          我们可以看到该接口中声明的每个操作都是由两个方法对应,那这两个方法之间有什么不同呢?调用两种方法的任意一种都是可以完成我们所需要的大部分功能,但是当处于特殊情况下,两者处理方式不一样。比如:当链表为空时,调用remove就会抛异常,而poll则是返回特殊值null,当链表满了,调用add就会抛异常,而offer就会false。(我们的LinkedList 是没有长度限制的,但是对于其他实现Queue的类可能会有长度限制,及可能会满员)。           看完了Queue我们看看看他的子接口Deque(双端队列):

public interface Deque<E> extends Queue<E> {
    void addFirst(E e);
    void addLast(E e);
    boolean offerFirst(E e);
    boolean offerLast(E e);
    E removeFirst();
    E removeLast();
    E pollFirst();
    E pollLast();
    E getFirst();
    E getLast();
    E peekFirst();
    E peekLast();
    .......
    //由于方法比较多,此处为了不增加篇幅,列举一些说明问题即可
    .......
  }

          我们可以很清晰的看到,Deque在继承Queue接口的前提下,扩展了N多方法,但是这些方法都是以XXfirst,XXlast形式的,这说明了,实现这个接口的类必须具有双端操作队列的能力。不在局限于从队头出,从队尾增加。当然,可能有些读者会有疑问,add方法和addlast方法实际上是相同的,为什么要声明addLast方法呢?没错,他们完成的功能的确一样,在LinkedList中也是这样实现的:

 public void addLast(E e) {
        linkLast(e);
    }
 public boolean add(E e) {
        linkLast(e);
        return true;
   }
   //实际上他们调用同样的方法来实现,只是返回了不同的类型
   
   //博主也不知道为何这样设计,可能是为了封装性更好吧

          所以,在LinkedList的内部方法中,有三对是具有一样功能的方法。 二、LinkedList的内部实现细节           之前我们也说过,既然实现了接口Deque 就一定是用双向链表来实现的,学过数据结构的读者就会发现这种结构灵活性很强。我们一起来看看:

/*为了节约篇幅,只截取部分代码*/
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
 transient Node<E> first;
 transient Node<E> last;
 //成员内部类
 private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
 }

          这就是,整个LinkedList的大体结构,一个成员内部类定义了每个节点的内容,数据值和一个指向前一个节点的prev指针和一个指向后一个节点的next指针。在整个LinkedList中,有一个头指针指向整个队列的头部,一个尾指针指向整个队列的尾部。整个队列的结构如下图:

三、add方法添加元素           了解了LinkedList内部的组成原理,我们接下来看看,怎么在任意位置添加结点元素,比较一下他优于ArrayList的地方是怎么实现的。

public boolean add(E e) {
        linkLast(e);
        return true;
}
//主要实现还是linkLast
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
        size++;
        modCount++;
 }

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

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    
 void linkBefore(E e, Node<E> succ) {
     // assert succ != null;
     final Node<E> pred = succ.prev;
     final Node<E> newNode = new Node<>(pred, e, succ);
     succ.prev = newNode;
     if (pred == null)
         first = newNode;
     else
         pred.next = newNod
         size++;
        modCount++;
 }

          首先判断,指定的索引是否大于链表中节点个数size,如果index == size表示,将要添加在最后一个元素的后面,和上述一样,如果不是在最后位置添加元素,将数据域和node(index)(方法不具体看,就是返回索引值为index的结点)

假设我要插入的结点的index为1,pred接受succ.prev返回的前一个结点(即0号结点),构建一个newnode 向前指向pred,向后指向succ

然后将succ的前指针指向newnode

然后将pred的next指针指向newnode完成添加。

我们捋顺了看:

四、remove删除结点           看完了添加,删除就显得简单些,无非分为两种,从头部删除,从中间删除,从头部删除和从尾部添加一样简单,从中间删除就是把此结点的前一个结点的next指向此结点的后一个结点,并把后一个结点的prev指向此节点的前一个结点,就是跳过此结点,最终将此结点null交给GC大人解决。为了篇幅,我们不再赘述。 五、低效的get方法           最后,和大家看看一个方法,我们知道链表是不支持随机访问的,如果你要查找某个结点的元素值,你必须要从头开始遍历直至找到那个元素结点(查找时,效率比ArrayList低下),但是我们的LinkedList 中提供有get(index)方法貌似有随机访问的能力。我们看看代码:

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
    Node<E> node(int index) {
        // assert isElementIndex(index);

        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;
        }
    }

          从源代码中我们可以清晰的看到,所谓的get方法也就是,调用node方法遍历整个链表,只是其中稍微做了点优化,如果index的值小于size/2从头部遍历,否则从尾部遍历。可见效率一样低下,所以我们以后写程序的时候,如果遇到数据量不大但是需要经常遍历查找的时候使用ArrayList而不是LinkedList,如果数据量非常的大,但是不是很经常的查找时使用LinkedList。           本文是作者查阅书籍和博客总结得来,如有错误,望大家指出!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏有趣的Python

Python装饰器-专题笔记学会装饰器,Python更进阶函数作用域什么是闭包Python装饰器支持闭包的语言有这样的特性:

学会装饰器,Python更进阶 函数作用域到闭包到装饰器讲解,及闭包和装饰器的运用。 [√] 慕课网Meshare_huang老师: python进阶 ? 函数...

2644
来自专栏云霄雨霁

Java--通配符类型

1544
来自专栏zaking's

用js来实现那些数据结构07(链表01-链表的实现)

  前面讲解了数组,栈和队列。其实大家回想一下。它们有很多相似的地方。甚至栈和队列这两种数据结构在js中的实现方式也都是基于数组。无论增删的方式、遵循的原则如何...

36310
来自专栏苦逼的码农

谈谈fail-fast与fail-safe

fail-fast的字面意思是“快速失败”。当我们在遍历集合元素的时候,经常会使用迭代器,但在迭代器遍历元素的过程中,如果集合的结构被改变的话,就会抛出异常,防...

784
来自专栏龙首琴剑庐

Java集合框架一览笔录

1、集合概念 集合类主要负责保存、盛装其他数据,因此集合类也被称为容器类。所以的集合类都位于java.util包下,后来为了处理多线程环境下的并发安全问题,ja...

2767
来自专栏开发之途

Java集合框架源码解析之LinkedList

1053
来自专栏Danny的专栏

Java基础——List接口

  如上图:ArrayList, LinkedList, Vector, Stack是List4个常用的实现类。

672
来自专栏小勇DW3

ArrayList在foreach删除倒数第二个元素不抛并发修改异常的问题

平时我们使用ArrayList比较多,但是我们是否知道ArrayList在进行foreach的时候不能直接通过list的add或者move方法进行删除呢,

823
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题17合并两个排序的链表

本题的详细解析均在代码注释中: /** * 题目:输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。 * @author 大闲人...

3787
来自专栏拭心的安卓进阶之路

深入理解 Java 泛型

首先提个问题: Java 泛型的作用是什么?泛型擦除是什么?泛型一般用在什么场景? 如果这个问题你答不上来,那这篇文章可能就对你有些价值。 什么是泛...

2599

扫码关注云+社区