首页 > > 程序设计 > Java技术 >

数据结构:用实例分析ArrayList与LinkedList的读…

2020-06-04 16:04:05来源：博客园 阅读 ()

新老客户大回馈,云服务器低至5折

数据结构:用实例分析ArrayList与LinkedList的读写性能

目录

  • 背景
  • ArrayList
  • LinkedList
  • 实例分析
    • 1、增加数据
    • 2、插入数据
    • 3、遍历数据
      • 3.1、LinkedList遍历改进
  • 总结

背景

ArrayList与LinkedList是Java编程中经常会用到的两种基本数据结构，在书本上一般会说明以下两个特点：

  • 对于需要快速随机访问元素，应该使用ArrayList。
  • 对于需要快速插入，删除元素，应该使用LinkedList。

该文通过实际的例子分析这两种数据的读写性能。

ArrayList

ArrayList是实现了基于动态数组的数据结构：

private static final int DEFAULT_CAPACITY = 10;
...
transient Object[] elementData;
...
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

LinkedList

LinkedList是基于链表的数据结构。

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;
        }
    }
...    
transient Node<E> first;
transient Node<E> last;
...
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++;
    }

实例分析

  • 通过对两个数据结构分别增加、插入、遍历进行读写性能分析
1、增加数据
public class ArrayListAndLinkList {
    public final static int COUNT=100000;
    public static void main(String[] args) {

        // ArrayList插入
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        Long start = System.currentTimeMillis();
        System.out.println("ArrayList插入开始时间：" + sdf.format(start));

        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < COUNT; i++) {
            arrayList.add(i);
        }

        Long end = System.currentTimeMillis();
        System.out.println("ArrayList插入结束时间：" + sdf.format(end));
        System.out.println("ArrayList插入" + (end - start) + "毫秒");


        // LinkedList插入
        start = System.currentTimeMillis();
        System.out.println("LinkedList插入开始时间：" + sdf.format(start));
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < COUNT; i++) {
            linkedList.add(i);
        }
        end = System.currentTimeMillis();
        System.out.println("LinkedList插入结束时间：" + sdf.format(end));
        System.out.println("LinkedList插入结束时间" + (end - start) + "毫秒");
     }
}

输出如下：
两者写入的性能相差不大！
在这里插入图片描述

2、插入数据

在原有增加的数据上，在index:100的位置上再插入10万条数据。

public class ArrayListAndLinkList {
    public final static int COUNT=100000;
    public static void main(String[] args) {

        // ArrayList插入
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        Long start = System.currentTimeMillis();
        System.out.println("ArrayList插入开始时间：" + sdf.format(start));

        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < COUNT; i++) {
            arrayList.add(i);
        }
        for (int i = 0; i < COUNT; i++) {
            arrayList.add(100,i);
        }

        Long end = System.currentTimeMillis();
        System.out.println("ArrayList插入结束时间：" + sdf.format(end));
        System.out.println("ArrayList插入" + (end - start) + "毫秒");


        // LinkedList插入
        start = System.currentTimeMillis();
        System.out.println("LinkedList插入开始时间：" + sdf.format(start));
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < COUNT; i++) {
            linkedList.add(i);
        }
        for (int i = 0; i < COUNT; i++) {
            linkedList.add(100,i);
        }
        end = System.currentTimeMillis();
        System.out.println("LinkedList插入结束时间：" + sdf.format(end));
        System.out.println("LinkedList插入结束时间" + (end - start) + "毫秒");
     }
}

输出如下：
ArrayList的性能明显比LinkedList的性能差了很多。
在这里插入图片描述
看下原因：
ArrayList的插入源码：

  public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

ArrayList的插入原理：在index位置上插入后，在index后续的数据上需要做逐一复制。
在这里插入图片描述
LinkedList的插入源码：

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
 }
 ...
  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++;
    }

LinkedList的插入原理：在原来相互链接的两个节点（Node）断开，把新的结点插入到这两个节点中间，根本不存在复制这个过程。
在这里插入图片描述

3、遍历数据

在增加和插入的基础上，利用get方法进行遍历。

public class ArrayListAndLinkList {
    public final static int COUNT=100000;
    public static void main(String[] args) {

        // ArrayList插入
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        Long start = System.currentTimeMillis();
        System.out.println("ArrayList插入开始时间：" + sdf.format(start));

        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < COUNT; i++) {
            arrayList.add(i);
        }
        for (int i = 0; i < COUNT; i++) {
            arrayList.add(100,i);
        }

        Long end = System.currentTimeMillis();
        System.out.println("ArrayList插入结束时间：" + sdf.format(end));
        System.out.println("ArrayList插入" + (end - start) + "毫秒");


        // LinkedList插入
        start = System.currentTimeMillis();
        System.out.println("LinkedList插入开始时间：" + sdf.format(start));
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < COUNT; i++) {
            linkedList.add(i);
        }
        for (int i = 0; i < COUNT; i++) {
            linkedList.add(100,i);
        }
        end = System.currentTimeMillis();
        System.out.println("LinkedList插入结束时间：" + sdf.format(end));
        System.out.println("LinkedList插入结束时间" + (end - start) + "毫秒");

        // ArrayList遍历
        start = System.currentTimeMillis();
        System.out.println("ArrayList遍历开始时间：" + sdf.format(start));
        for (int i = 0; i < 2*COUNT; i++) {
            arrayList.get(i);
        }
        end = System.currentTimeMillis();
        System.out.println("ArrayList遍历开始时间：" + sdf.format(end));
        System.out.println("ArrayList遍历开始时间" + (end - start) + "毫秒");

        // LinkedList遍历
        start = System.currentTimeMillis();
        System.out.println("LinkedList遍历开始时间：" + sdf.format(start));
        for (int i = 0; i < 2*COUNT; i++) {
            linkedList.get(i);
        }
        end = System.currentTimeMillis();
        System.out.println("LinkedList遍历开始时间：" + sdf.format(end));
        System.out.println("LinkedList遍历开始时间" + (end - start) + "毫秒");

    }
}

输出如下：
在这里插入图片描述
两者的差异巨大：
我们看一下LInkedList的get方法：从头遍历或从尾部遍历结点

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
 ...
 Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
3.1、LinkedList遍历改进

我们采用迭代器对LinkedList的遍历进行改进：

		...
		// LinkedList遍历
        start = System.currentTimeMillis();
        System.out.println("LinkedList遍历开始时间：" + sdf.format(start));
        Iterator<Integer> iterator = linkedList.iterator();
        while(iterator.hasNext()){
            iterator.next();
        }
        end = System.currentTimeMillis();
        System.out.println("LinkedList遍历开始时间：" + sdf.format(end));
        System.out.println("LinkedList遍历开始时间" + (end - start) + "毫秒");

再看下结果：
两者的遍历性能接近。
在这里插入图片描述

总结

  • List使用首选ArrayList。对于个别插入删除非常多的可以使用LinkedList。
  • LinkedList，遍历建议使用Iterator迭代器，尤其是数据量较大时LinkedList避免使用get遍历。

原文链接:https://www.cnblogs.com/zhuhuix/p/13042761.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：Java Spring注入一个接口的多个实现类在map里如何实现？案例详

下一篇：拼多多三面惨败，问题在于java中间件、数据库与spring框架.卡壳

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签