java中LinkedList使用迭代器优化移除批量元素原理

本文主要介绍了java中LinkedList使用迭代器优化移除批量元素原理,分享给大家,具体如下:

public interface Iterator<E> {
    /**
     *是否还有下一个元素
     */
    boolean hasNext();
    /**
     *下一个元素
     */
    E next();
    /**
     * 从集合中删除最后一个返回的元素
     */
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    /**
     * 传入一个Consumer对剩余的每个元素执行指定的操作,直到所有元素已处理或操作引发异常
     */
    default void forEachRemaining(Consumer<? super E> action) {
        //requireNonNull 静态方法将会在参数为null时主动抛出NullPointerException 异常。
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}
public interface ListIterator<E> extends Iterator<E> {

    /**
     * 是否有后继
     */
    boolean hasNext();
    /**
     * 后继节点
     */
    E next();

    /**
     * 是否有前驱
     */
    boolean hasPrevious();

    /**
     * 前驱节点
     */
    E previous();

    /**
     * 下一个节点的下标
     */
    int nextIndex();

    /**
     * 前驱节点的下标
     */
    int previousIndex();

    /**
     * 移除元素
     */
    void remove();

    /**
     * 替换最后返回的元素
     */
    void set(E e);

    /**
     * 插入一个结点到最后返回的元素之后
     */
    void add(E e);
}

普通版 ArrayListdie迭代器

调用方法:list.iterator();

public Iterator<E> iterator() {
        return new Itr();
    }
    private class Itr implements Iterator<E> {
        int cursor;       // 当前下标
        int lastRet = -1; // 最后一个元素的索引,没有返回1
        int expectedModCount = modCount;//创建迭代器时列表被修改的次数,防止多线程操作。快速失败
        /**
        * 先检查一下是否列表已经被修改过
        * 做一些简单的越界检查
        * 返回元素,并且记录下返回元素的下标给lastRet,当前下标+1,
        */
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
        /**
        * 调用ArrayListdie自身的remove方法移除元素
        * ArrayListdie自身的remove 会修改modCount的值所以需要更新迭代器的expectedModCount
        * expectedModCount = modCount;
        */
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
        //把剩下为next遍历的所有元素做一个遍历消费
        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }
        //检查是否列表已经被修改了
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

增强版本 ArrayListdie迭代器

实现了ListIterator接口,ListIterator接口继承Iterator接口。并且ListItr extends Itr。Itr有的方法其都有。并且增加了

  • hasPrevious 是否有前驱
  • nextIndex 下一个索引位置
  • previousIndex 前驱的索引位置
  • previous 前驱元素
  • set 替换最后返回的元素
  • add 插入一个结点到最后返回的元素之后
private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index;
        }
        public boolean hasPrevious() {
            return cursor != 0;
        }
        public int nextIndex() {
            return cursor;
        }
        public int previousIndex() {
            return cursor - 1;
        }
        public E previous() {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }
        //根据lastRet设置元素
        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
            try {
                ArrayList.this.set(lastRet, e);
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

重点看一下LinkedList的迭代器

调用方法:list.iterator();

重点看下remove方法

private class ListItr implements ListIterator<E> {
        //返回的节点
        private Node<E> lastReturned;
        //下一个节点
        private Node<E> next;
        //下一个节点索引
        private int nextIndex;
        //修改次数
        private int expectedModCount = modCount;

        ListItr(int index) {
            //根据传进来的数字设置next等属性,默认传0
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }
        //直接调用节点的后继指针
        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();
            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }
        //返回节点的前驱
        public E previous() {
            checkForComodification();
            if (!hasPrevious())
                throw new NoSuchElementException();

            lastReturned = next = (next == null) ? last : next.prev;
            nextIndex--;
            return lastReturned.item;
        }
        /**
        * 最重要的方法,在LinkedList中按一定规则移除大量元素时用这个方法
        * 为什么会比list.remove效率高呢;
        */
        public void remove() {
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();

            Node<E> lastNext = lastReturned.next;
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = null;
            expectedModCount++;
        }

        public void set(E e) {
            if (lastReturned == null)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.item = e;
        }

        public void add(E e) {
            checkForComodification();
            lastReturned = null;
            if (next == null)
                linkLast(e);
            else
                linkBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }
    }

LinkedList 源码的remove(int index)的过程是
先逐一移动指针,再找到要移除的Node,最后再修改这个Node前驱后继等移除Node。如果有批量元素要按规则移除的话这么做时间复杂度O(n²)。但是使用迭代器是O(n)。

先看看list.remove(idnex)是怎么处理的

LinkedList是双向链表,这里示意图简单画个单链表
比如要移除链表中偶数元素,先循环调用get方法,指针逐渐后移获得元素,比如获得index = 1;指针后移两次才能获得元素。
当发现元素值为偶数是。使用idnex移除元素,如list.remove(1);链表先Node node(int index)返回该index下的元素,与get方法一样。然后再做前驱后继的修改。所以在remove之前相当于做了两次get请求。导致时间复杂度是O(n)。

继续移除下一个元素需要重新再走一遍链表(步骤忽略当index大于半数,链表倒序查找)

以上如果移除偶数指针做了6次移动。

删除2节点
get请求移动1次,remove(1)移动1次。

删除4节点
get请求移动2次,remove(2)移动2次。

迭代器的处理

迭代器的next指针执行一次一直向后移动的操作。一共只需要移动4次。当元素越多时这个差距会越明显。整体上移除批量元素是O(n),而使用list.remove(index)移除批量元素是O(n²)

到此这篇关于java中LinkedList使用迭代器优化移除批量元素原理的文章就介绍到这了,更多相关LinkedList 迭代器批量移除内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • java中ArrayList和LinkedList的区别详解

    ArrayList和LinkedList都实现了List接口,有以下的不同点: 1.ArrayList是基于索引的数据接口,它的底层是数组.它可以以O(1)时间复杂度对元素进行随机访问.与此对应,LinkedList是以元素列表的形式存储它的数据,每一个元素都和它的前一个和后一个元素链接在一起,在这种情况下,查找某个元素的时间复杂度是O(n). 2.相对于ArrayList,LinkedList的插入,添加,删除操作速度更快,因为当元素被添加到集合任意位置的时候,不需要像数组那样重新计算大小或者

  • 分析Java中ArrayList与LinkedList列表结构的源码

    一.ArrayList源码分析(JDK7) ArrayList内部维护了一个动态的Object数组,ArrayList的动态增删就是对这个对组的动态的增加和删除. 1.ArrayList构造以及初始化 ArrayList实例变量 //ArrayList默认容量 private static final int DEFAULT_CAPACITY = 10; //默认空的Object数组, 用于定义空的ArrayList private static final Object[] EMPTY_ELE

  • java LinkedList类详解及实例代码

    java  LinkedList类详解 LinkedList的特有功能 A:添加功能 public void addFirst(Object e); public void addLast(Object e); B:特有功能 public Object getFirst(); public Object getLast(); C:删除功能 public Object removeFirst(); public Object removeLast(); 实例代码: import java.util

  • 解析Java中的队列和用LinkedList集合模拟队列的方法

    API中对队列的说明: public interface Queue<E> extends Collection<E> 在处理元素前用于保存元素的 collection.除了基本的 Collection 操作外,队列还提供其他的插入.提取和检查操作.每个方法都存在两种形式:一种抛出异常(操作失败时),另一种返回一个特殊值(null 或 false,具体取决于操作).插入操作的后一种形式是用于专门为有容量限制的 Queue 实现设计的:在大多数实现中,插入操作不会失败. 队列通常(但

  • Java LinkedList的实现原理图文详解

    一.概述 先来看看源码中的这一段注释,我们先尝试从中提取一些信息: Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).All of the operations perform as could be expected for a doubly-l

  • Java集合框架LinkedList详解及实例

    Java集合框架LinkedList详解 LinkedList定义 package java.util; public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ transient int size = 0; transient Node<E> first;

  • JAVA LinkedList和ArrayList的使用及性能分析

    第1部分 List概括List的框架图List 是一个接口,它继承于Collection的接口.它代表着有序的队列.AbstractList 是一个抽象类,它继承于AbstractCollection.AbstractList实现List接口中除size().get(int location)之外的函数.AbstractSequentialList 是一个抽象类,它继承于AbstractList.AbstractSequentialList 实现了"链表中,根据index索引值操作链表的全部函数

  • java中LinkedList使用迭代器优化移除批量元素原理

    本文主要介绍了java中LinkedList使用迭代器优化移除批量元素原理,分享给大家,具体如下: public interface Iterator<E> { /** *是否还有下一个元素 */ boolean hasNext(); /** *下一个元素 */ E next(); /** * 从集合中删除最后一个返回的元素 */ default void remove() { throw new UnsupportedOperationException("remove"

  • Java中LinkedList详解和使用示例_动力节点Java学院整理

    第1部分 LinkedList介绍 LinkedList简介 LinkedList 是一个继承于AbstractSequentialList的双向链表.它也可以被当作堆栈.队列或双端队列进行操作. LinkedList 实现 List 接口,能对它进行队列操作. LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用. LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆. LinkedList 实现java.io.Serial

  • Java中LinkedList原理代码解析

    本文研究的主要是Java中LinkedList原理的相关内容,具体介绍如下. 一句话概括,Java中的LinkedList其实就是使用双向链表,LinkedList的基本操作就是对双向链表的操作. 上面可以清晰的看出,链表中每个元素对应一个节点,节点里面包含三部分,一个是前一个节点的引用,一个是元素内容,一个是后一个节点的引用. 向链表中添加元素的过程就是在链表尾部追加一个节点 void linkLast(E e) { final Node<E> l = last; final Node<

  • Java中LinkedList真的是查找慢增删快

    测试结果 废话不多说,先上测试结果.作者分别在ArrayList和LinkedList的头部.尾部和中间三个位置插入与查找100000个元素所消耗的时间来进行对比测试,下面是测试结果 (感谢@Hosalo的指正,在这里说明一下测试的环境,尾部插入是在空表的基础上测试的,头部和中间位置插入是在已存在100000个元素的表上进行测试的) 插入 查找 ArrayList尾部 26ms 4ms ArrayList头部 2887ms 3ms ArrayList中间 1936ms 4ms LinkedLis

  • Java中LinkedList的模拟实现

    目录 关于LinkedList 模拟实现LinkedList 准备工作 头插 尾插 在任意位置插入 删除remove 删除removeAll 找元素下标indexOf 找元素下标lastIndexOf 判断链表是否包含某个元素 获得链表长度 链表判空 清空链表 关于LinkedList LinkedList的底层是用一个双向链表实现的,即一个结点中除了有一个引用指向下一个结点的地址,还有一个引用指向前一个结点的地址 LinkedList还有三个成员变量: size,表示该链表中结点的个数 fir

  • Java中BIO、NIO和AIO的区别、原理与用法

    目录 IO BIO NIO AIO 区别及联系 各自适用场景 使用方式 IO 什么是IO? 它是指计算机与外部世界或者一个程序与计算机的其余部分的之间的接口.它对于任何计算机系统都非常关键,因而所有 I/O 的主体实际上是内置在操作系统中的.单独的程序一般是让系统为它们完成大部分的工作. 在 Java 编程中,直到最近一直使用 流 的方式完成 I/O.所有 I/O 都被视为单个的字节的移动,通过一个称为 Stream 的对象一次移动一个字节.流 I/O 用于与外部世界接触.它也在内部使用,用于将

  • 详解Java中的迭代迭代器Iterator与枚举器Enumeration

    迭代器Iterator接口 1.迭代器接口 Iterable 内置方法iterator(), 返回一个新建的 Iterator. 如: public interface Iterable { Iterator Iterator(); } Iterator 有 hasNext() 和 next() 两个方法要实现. public interface Iterator { boolean hasNext(); Item next(); void remove(); //可选实现 } 2.实现 导入

  • Java中List集合的深入介绍(超级推荐!)

    目录 1,Java集合介绍 2,List介绍 2.1 ArrayList集合 2.2 LinkedList集合 3,List常用方法 3.1 ArrayList 基本操作 3.2 LinkedList 基本操作 4,ArrayList和LinkedList比较 5,ArrayList源码分析 6,LinkedList源码分析 7,小结 1,Java集合介绍 作为一个程序猿,Java集合类可以说是我们在工作中运用最多.最频繁的类.相比于数组(Array)来说,集合类的长度可变,更加方便开发. Ja

  • 简单探索 Java 中的惰性计算

    前言 惰性计算(尽可能延迟表达式求值)是许多函数式编程语言的特性.惰性集合在需要时提供其元素,无需预先计算它们,这带来了一些好处. 首先,您可以将耗时的计算推迟到绝对需要的时候.其次,您可以创造无限个集合,只要它们继续收到请求,就会继续提供元素.第三,map 和 filter 等函数的惰性使用让您能够得到更高效的代码(请参阅 参考资料 中的链接,加入由 Brian Goetz 组织的相关讨论).Java 并没有为惰性提供原生支持,但一些框架和后继语言支持这种惰性. 假定使用此伪代码片段来打印列表

  • 深入理解Java中没那么简单的单例模式

    前言 大家都知道关于Java中单例(Singleton)模式是一种广泛使用的设计模式.单例模式的主要作用是保证在Java程序中,某个类只有一个实例存在.一些管理器和控制器常被设计成单例模式. 单例模式有很多好处,它能够避免实例对象的重复创建,不仅可以减少每次创建对象的时间开销,还可以节约内存空间:能够避免由于操作多个实例导致的逻辑错误.如果一个对象有可能贯穿整个应用程序,而且起到了全局统一管理控制的作用,那么单例模式也许是一个值得考虑的选择. 单例模式有很多种写法,大部分写法都或多或少有一些不足

随机推荐