Java 集合深入理解(8):AbstractSequentialList

今天有点无聊,来学学 AbstractSequentialList 解解闷 吧!

AbstractSequentialList 没有什么特别的,这里介绍是为了理解 LinkedList 更容易。

什么是 AbstractSequentialList

( Sequential 相继的,按次序的)

AbstractSequentialList 继承自 AbstractList,是 LinkedList 的父类,是 List 接口 的简化版实现。

简化在哪儿呢?简化在 AbstractSequentialList 只支持按次序访问,而不像 AbstractList 那样支持随机访问。

想要实现一个支持按次序访问的 List的话,只需要继承这个抽象类,然后把指定的抽象方法实现就好了。需要实现的方法:

  • size()
  • listIterator(),返回一个 ListIterator

你需要实现一个 ListIterator, 实现它的 hasNext(), hasPrevious(), next(), previous(), 还有那几个 获取位置 的方法,这样你就得到一个不可变的 ListIterator 了。如果你想让它可修改,还需要实现 add(), remove(), set() 方法。

正如在 每个 Collection 接口 中提倡的那样,AbstractSequentialList 的子类需要提供两个构造函数,一个无参,一个以 Collection 为参数。

成员函数

AbstractSequentialList 在 AbstractList 的基础上实现了以下方法:

1.获取迭代器:

public Iterator<E> iterator() {
    //调用继承自
    return listIterator();
}

//继承 AbstractList 的 listIterator()
public ListIterator<E> listIterator() {
    return listIterator(0);
}

//需要实现类实现的方法
public abstract ListIterator<E> listIterator(int index);

2.add(int, E) 添加元素到指定位置,将当前处于该位置(如果有的话)和任何后续元素的元素移到右边(添加一个到它们的索引):

public void add(int index, E element) {
    try {
        //调用 ListIterator.add()
        listIterator(index).add(element);
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

如果 Listerator 的实现类实现 add() 方法,会报 UnsupportedOperationException 错。

3.addAll(int index, Collection

用获取到的 listIterator 逐个添加集合中的元素,这就要考验 ListIterator.add 方法的实现效率了,总不能每次都后移一位吧

的确在目前集合框架中 AbstractSequentialList 的唯一实现类 LinkedList 实现的 ListIterator 中,由于 LinkedList 的双休链表特性,每次 add 只需要调整指针指向就可以了。

4.get(int index) 获取指定位置的元素:

public E get(int index) {
    try {
        return listIterator(index).next();
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

5.set(int index, E element) 修改指定位置的元素为新的:

public E set(int index, E element) {
    try {
        ListIterator<E> e = listIterator(index);
        E oldVal = e.next();
        e.set(element);
        return oldVal;
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

6.remove(int index) 删除指定位置的元素:

public E remove(int index) {
    try {
        ListIterator<E> e = listIterator(index);
        E outCast = e.next();
        e.remove();
        return outCast;
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

总结

可以看到, AbstractSequentialList 把父类 AbstractList 中没有实现或者没有支持的操作都实现了,而且都是调用的 ListIterator 相关方法进行操作。

Java 集合深入理解:AbstractList 中我们介绍了 RandomAccess,里面提到,支持 RandomAccess 的对象,遍历时使用 get 比 迭代器更快。

而 AbstractSequentialList 只支持迭代器按顺序 访问,不支持 RandomAccess,所以遍历 AbstractSequentialList 的子类,使用 for 循环 get() 的效率要 <= 迭代器遍历:

int i=0, n=list.size(); i &lt; n; i++)
      list.get(i);

get()太慢,还不如用迭代器:

for (Iterator i=list.iterator(); i.hasNext(); )
     i.next();

Thanks

http://www.trinea.cn/android/arraylist-linkedlist-loop-performance/

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编舟记

命令行中 tree 的多重实现

692
来自专栏一枝花算不算浪漫

[Java Collection]List分组之简单应用.

2705
来自专栏Ryan Miao

java8-Stream之数值流

在Stream里元素都是对象,那么,当我们操作一个数字流的时候就不得不考虑一个问题,拆箱和装箱。虽然自动拆箱不需要我们处理,但依旧有隐含的成本在里面。Java8...

2685
来自专栏机器学习入门

挑战程序竞赛系列(84):3.6极限情况(1)

挑战程序竞赛系列(84):3.6极限情况(1) 传送门:POJ 1981: Circle and Points 题意: 平面上有N个点,给定半径为1的圆,最多...

1878
来自专栏xingoo, 一个梦想做发明家的程序员

【设计模式】—— 解释器模式Interpret

  模式意图   自定义某种语言后,给定一种文法标准,定义解释器,进行解析。   做过搜索的朋友们可能更了解一些,平时我们搜索所需要的词库,通常就需要用这种方...

1826
来自专栏debugeeker的专栏

source insight coredump分析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

381
来自专栏数据之美

java 中 16 进制 HEX 转换成字节码形式的 UTF-8

恩,又碰到个蛋疼的编码转换问题了:要把形如 \xE9\xBB 的字符串转成中文。。。 在python中我们直接 print "\xE9\xBB\x84" ...

1945
来自专栏微信公众号:Java团长

Java中的十个&quot;单行代码编程&quot;(One Liner)

本文列举了十个使用一行代码即可独立完成(不依赖其他代码)的业务逻辑,主要依赖的是Java8中的Lambda和Stream等新特性以及try-with-resou...

812
来自专栏CSDN技术头条

Java中的十个“单行代码编程”(One Liner)

本文列举了十个使用一行代码即可独立完成(不依赖其他代码)的业务逻辑,主要依赖的是 Java8 中的 Lambda 和 Stream 等新特性以及 try-wit...

1203
来自专栏Ryan Miao

Java中ArrayList remove会遇到的坑

前言 平时最常用的莫过于ArrayList和HashMap了,面试的时候也是问答的常客。先不去管容量、负载因子什么的,就是简单的使用也会遇到坑。 ? Rem...

2517

扫码关注云+社区