资讯专栏INFORMATION COLUMN

Java容器类研究5:LinkedList

frank_fun / 2047人阅读

摘要:提供了顺序访问的方法,当然,大部分方法都依赖于来实现,所以将锅甩给了子类。实现了自己的遍历方法利用了链表结构的特性,进行遍历。其中有如下属性记录遍历状态。该方法位于中到数组中这里返回的不是,其实是

java.util.LinkedList

Java中有现成的队列可以用吗

有,就是LinkedList。LinkedList实现的接口如下,其实也可以当做stack使用:

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

Deque是一个双端队列的接口,而Deque又继承了接口Queue。所以LinkedList可以作为队列、双端队列来使用。

AbstractSequentialList提供了顺序访问的方法,当然,大部分方法都依赖于ListIterator来实现,所以将锅甩给了子类。

LinkedList用什么结构来实现

同样很简单,是一个Node的双向链表结构。

    private static class Node {
        E item;
        Node next;
        Node prev;

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

有属性first和last记录着链表的开始和结束节点。

在链表中通过下标取值是低效的

在LinkedList中,大量的方法需要先获得指定下标的节点,具体实现如下:

    Node node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

可以看出,开发者已经尽力优化,根据index大小决定从何处开始遍历。

LinkedList实现了自己的ListIterator

遍历方法利用了链表结构的特性,进行遍历。其中有如下属性记录遍历状态。

    private Node lastReturned; //记录最近一次返回的节点
    private Node next;    //记录下一个要返回的节点
    private int nextIndex;   //记录下一个要返回的位置
    private int expectedModCount = modCount;  //记录期望的修改次数
LinkedList的Spliterator采用什么样的分割策略

LinkedList每次划分,不是采用的1/2策略,而是每次分裂出来的一块数据都增加一个BATCH_UNIT(1024)的大小。比较有趣的是,每次分裂出来的Spliterator并不是LinkedList自己实现的Spliterator,而是一个ArraySpliterator,ArraySpliterator采用的是1/2的分裂策略。所以LinkedList每次分裂都想尽可能快的分裂出更多的元素,并且分裂过程中将链表结构转化为数组结构,这样做可能是出于性能的考虑,具体什么原因还是比较纳闷的。

        //该方法位于class LLSpliterator中
        public Spliterator trySplit() {
            Node p;
            int s = getEst();
            if (s > 1 && (p = current) != null) {
                int n = batch + BATCH_UNIT;
                if (n > s)
                    n = s;
                if (n > MAX_BATCH)
                    n = MAX_BATCH;
                //copy到数组中
                Object[] a = new Object[n];
                int j = 0;
                do { a[j++] = p.item; } while ((p = p.next) != null && j < n);
                current = p;
                batch = j;
                est = s - j;
                //这里返回的不是LLSpliterator,其实是ArraySpliterator
                return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
            }
            return null;
        }

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/67799.html

相关文章

  • Java 基础 | Collection 集合概览

    摘要:说到复盘基础,并不是所有的都会复盘,没那个时间更没那个必要。比如,一些基础的语法以及条件语句,极度简单。思前想后,我觉得整个计划应该从集合开始,而复盘的方式就是读源码。通常,队列不允许随机访问队列中的元素。 ​showImg(https://segmentfault.com/img/remote/1460000020029737?w=1080&h=711); 老读者都知道,我是自学转行...

    codergarden 评论0 收藏0
  • Java容器研究1:Collection

    摘要:集合类关系是和的父接口。相等必须是对称的,约定只能和其它相等,亦然。和接口在中引入,这个单词是和的合成,用来分割集合以给并行处理提供方便。这些并不立即执行,而是等到最后一个函数,统一执行。 集合类关系: Collection ├List │├LinkedList │├ArrayList │└Vector │ └Stack └Set Map ...

    AprilJ 评论0 收藏0
  • Java容器研究6:Vector

    摘要:不同点是线程安全的,方法有关键字修饰。容量增长策略默认的增长策略是每次在原容量的基础上。的怎么做到线程安全的实现了自己的,为了保证并发线程安全的共享一个,开发者在等方法中也加入了。与类继承自,的实现不止一种方式,比如。 java.util.Vector Vector与ArrayList的异同 相同点:随机存取,可通过位置序号直接获取数据。都是通过一个数组来存放元素。 不同点:Vecto...

    Charles 评论0 收藏0
  • Java 持有对象(11)

    摘要:如果一个程序只包含固定数量且其生命周期都是已知的对象,那么这是一个非常简单的程序。 如果一个程序只包含固定数量且其生命周期都是已知的对象,那么这是一个非常简单的程序。 1.泛型和类型安全的容器 通过使用泛型,可以在编译期防止将错误类型的对象放置到容器中. 2.基本概念 Java容器类库的用途是保存对象,并将其划分为两个不同的概念:Collection,Map. Collection...

    summerpxy 评论0 收藏0
  • Week 2 - Java 容器 - 详细剖析 List 之 ArrayList, Vector,

    摘要:底层使用的是双向链表数据结构之前为循环链表,取消了循环。快速随机访问就是通过元素的序号快速获取元素对象对应于方法。而接口就是用来标识该类支持快速随机访问。仅仅是起标识作用。,中文名为双端队列。不同的是,是线程安全的,内部使用了进行同步。 前言 学习情况记录 时间:week 2 SMART子目标 :Java 容器 记录在学习Java容器 知识点中,关于List的需要重点记录的知识点。...

    MartinDai 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<