上篇文章我们介绍了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（双端队列）：

        		
网友评论