Java容器类研究5：LinkedList

frank_fun 发布于2019-08-15 12:13 / 2029人阅读

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

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

云服务器 GPU云服务器 LinkedList 自定义容器类 java目前研究 java研究网

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

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

Java 基础 | Collection 集合概览

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

codergarden 2019-08-19 10:26 评论0 收藏0
Java容器类研究1：Collection

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

AprilJ 2019-08-15 12:07 评论0 收藏0
Java容器类研究6：Vector

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

Charles 2019-08-15 12:16 评论0 收藏0
Java 持有对象（11）

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

summerpxy 2019-08-16 12:46 评论0 收藏0
Week 2 - Java 容器 - 详细剖析 List 之 ArrayList, Vector,

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

MartinDai 2019-08-16 18:35 评论0 收藏0