文档章节

Jdk1.8 Collections Framework源码解析(2)-LinkedList

灯-塔
 灯-塔
发布于 2017/08/31 20:18
字数 1457
阅读 9
收藏 0
JDK

ArrayList的插入和删除元素的操作会花费线性时间,那么有没有插入和删除元素比较省时的集合呢,看下LinkedList这个实现。 老样子,先看看它实现了那些接口。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

之前看过的接口不看了。先看下java.util.Deque。

public interface Deque<E> extends Queue<E>  

这个接口扩展了java.util.Queue,Queue也是Java Collections Framework中一个重要的接口,它表示了队列。当然队列本身也属于集合(java.util.Collection是更高层次的抽象)。

public interface Queue<E> extends Collection<E>{  
    boolean add(E e);  
    boolean offer(E e);  
    E remove();  
    E poll();  
    E element();  
    E peek();  
} 

Queue提供了添加、删除和获取元素的方法,每种方法提供2个版本。如添加元素,add和offer都可以完成这个操作,区别在于add方法如果添加失败会抛出异常,而offer方法则会返回false。Queue接口只提供队列的抽象概念,但并没有定义元素的操作顺序。其实现可以提供先入先出或者先入后出(栈)这样的性质。

大概了解了java.util.Queue后继续看java.util.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();  
    boolean removeFirstOccurrence(Object o);  
    boolean removeLastOccurrence(Object o);  
    void push(E e);  
    E pop();  
    Iterator<E> descendingIterator();  
}

像Queue接口一样,Deque也对这些操作方法提供了2个版本。

接下来看一下java.util.AbstractSequentialList这个抽象类,这个类的作用和java.util.AbstractList作用一样,提供一些“骨架”实现。区别在于这个类提供了“按次序访问”的基础,而AbstractList提供了“自由访问”的基础。也就是说,如果我们要实现一个基于链表的集合的话,可以继承这个类;要实现基于数组的集合的话,就继承AbstractList类。

在看LinkedList的源代码之前,还是先思考一下,如果自己实现LinkedList要怎么做?

思考中......

既然是链表,那么内部一定会有一个“链”,而“链”是由“环”组成,说明内部会有“环”这样的概念。每个环都和下一个环相扣,有两个特殊的环,首环和尾环。首先,没有任意一环的下一环是首环,尾环没有下一环;然后,首环和尾环上是不携带数据的(当然普通环也是可以保存null元素滴)。如果再从代码上考虑一下,每一个环都有下一个环的引用,这样可以构成一个链。但每个环也可以即有上一个环的引用,又有下一个环的引用,也可以构成链。它们有什么区别呢?其实这就是所谓的单向链表和双向链表,java.util.LinkedList内部使用双向链表实现。那可以使用单向链表实现吗?那就试试吧。 这个不放参考一些之前《算法4》的一个实现。 通过查看OpenJDK的源码我们可是可以,对比不同JDK版本,的实现。

看来一下,LinkedList 类开头的注释,大概是这样说的, LinkedList 是基于 List 的一个双向链表实现的一个数据结构。

Doubly-linked list implementation of the {@code List} and {@code Deque} interfaces. Implements all optional list operations, and permits all elements (including {@code null}).

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    transient Node<E> first;

    transient Node<E> last;

通过上面的源码,我们看到,做为双向链表实现,必然会有一个 头指针 first 和 尾指针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;
        }
    }

我们在看看LikedList 的 的添加操作:

    /**
     * Links e as first element.
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

    /**
     * Links e as last element.
     */
    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++;
    }

    /**
     * Inserts element e before non-null Node succ.
     */
    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 = newNode;
        size++;
        modCount++;
    }

元素数据的查询,主要是通过下面的2个方法来实现的:

   /**
     * Returns the index of the first occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the lowest index {@code i} such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     *
     * @param o element to search for
     * @return the index of the first occurrence of the specified element in
     *         this list, or -1 if this list does not contain the element
     */
    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

    /**
     * Returns the index of the last occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the highest index {@code i} such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     *
     * @param o element to search for
     * @return the index of the last occurrence of the specified element in
     *         this list, or -1 if this list does not contain the element
     */
    public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

LikedList 默认是从头部开始查询,同时也提供了从尾部查询的方法。

© 著作权归作者所有

灯-塔
粉丝 4
博文 39
码字总数 63914
作品 0
广州
程序员
私信 提问
LinkedList工作原理

1.学习LinkedList的必要性 在ArrayList工作原理中,我们了解到ArrayList和LinkedList是List接口的两个重要实现。并且ArrayList是一个动态数组的实现。因此ArrayList在队列中插入和删除元素方...

kukudeku
2016/09/03
146
0
Java集合:Map接口总结

一、HashMap 基于哈希表的 Map 接口的实现,允许存入 null 值和 null 键,无序存储且线程不同步; HashMap 初始容量默认为16,扩容一定是2的指数,加载因子默认值为0.75; HashMap采用Itera...

阿阿阿阿阿局
2016/08/08
55
0
Java集合,LinkedList底层实现和原理

概述 文章的内容基于JDK1.7进行分析,之所以选用这个版本,是因为1.8的有些类做了改动,增加了阅读的难度,虽然是1.7,但是对于1.8做了重大改动的内容,文章也会进行说明。 LinkedList类是L...

郑加威
2018/02/27
2.5K
1
Vector及LinkedList源码解析

1、本文主要内容 Vector及LinkedList介绍 Vector源码解析 LinkedList源码解析 总结 java容器这个系列,虽然较为简单,但本着有始有终的原则,还是必须要写下去。同时感觉一篇只写一个容器,实...

某昆
2018/07/22
0
0
Java How to Program学习笔记_第十六章_Java集合(Generic Collections)——章节小结(Summary)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/hpdlzu80100/article/details/84963920 自己选择的路,含着泪也要走完,继续学习Java! Summary Section 16.1 ...

预见未来to50
2018/12/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

PCB设计-Allegro软件入门系列-allegro环境变量和快捷键

Allegro作为一款高速PCB设计的EDA软件,有完善的约束规则设计和信号完整性电源完整性仿真等各种专业工具深受电子行业从业者喜爱。 对于该软件来说,电子从业者接触最多的就是Allegro的画板功...

demyar
28分钟前
4
0
腾讯云存储

1、进入腾讯云平台,创建 2、进入配置查看域名 3、查看KEY参数 4、将2、3中的参数录入到cms后台 然后点测试按钮查看情况

迅睿CMS-PHP开源CMS程序
29分钟前
4
0
ES 6.x 版本 待验证的CURL命令查询操作

1. 查询数据 curl -H "Content-Type: application/json" -XGET http://elastic:123456@127.0.0.1:9200/alias1/_search -d '{"query": {"match_all": {}}}' 2. 添加数据 如果有不指定ID可以自......

coord
37分钟前
4
0
如何写好论文摘要:研究人员不得不知的小秘诀

我们为何要写摘要? 它的目的为何? 简而言之,摘要的目的就是简单的讨论这篇文章让读者更容易的了解这篇文。 它能在读者与作者之间搭起一条桥梁。当您搜索信息时,您无法一下阅读整篇文章,...

论文辅导员
39分钟前
4
0
移动端、PC端(前后台)、小程序常用的UI框架

移动端、PC端(前后台)、小程序常用的UI框架 1.移动端UI库 ①.Vant UI 官方地址:https://youzan.github.io/vant/#/zh-CN/intro github地址:https://github.com/youzan/vant 优点:用来做移...

jason_kiss
40分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部