首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

ArrayList、Vector、LinkedList的存储性能和特性简述

ArrayList 和Vector都是使用数组方式存储数据,此数组元素数大于实际存储的数据以便增加和插入元素,它们都允许直接按序号索引元素,但是插入元素要涉及数组元素移动等内存操作,所以索引数据快而插入数据慢,Vector中的方法由于添加了synchronized修饰,因此Vector是线程安全的容器,但性能上较ArrayList差,因此已经是Java中的遗留容器。LinkedList使用双向链表实现存储(将内存中零散的内存单元通过附加的引用关联起来,形成一个可以按序号索引的线性结构,这种链式存储方式与数组的连续存储方式相比,内存的利用率更高),按序号索引数据需要进行前向或后向遍历,但是插入数据时只需要记录本项的前后项即可,所以插入速度较快。Vector属于遗留容器(Java早期的版本中提供的容器,除此之外,Hashtable、Dictionary、BitSet、Stack、Properties都是遗留容器),已经不推荐使用,但是由于ArrayList和LinkedListed都是非线程安全的,如果遇到多个线程操作同一个容器的场景,则可以通过工具类Collections中的synchronizedList方法将其转换成线程安全的容器后再使用(这是对装潢模式的应用,将已有对象传入另一个类的构造器中创建新的对象来增强实现)。

02

排序(四):堆排序

在直接选择排序中,待排序的数据元素集合构成一个线性表结构,要从有n个数据元素的线性表中选择出一个最小的数据元素需要比较n-1次。如果能把待排序的数据元素集合构成一个完全二叉树结构,则每次选择出一个最大(或最小)的数据元素只需比较完全二叉树的高度次,即lb(n)次。这就是堆排序的基本思想。 下面给出一个完全二叉树的性质(在代码中会用到): 对于具有n个结点的完全二叉树,如果按照从上到下和从左到右的顺序对所有结点从0开始顺序编号,则对于序号为i的结点有: (1)如果i>0,则序号为i的结点的双亲结点的序号为(i-1)/2("/"表示);如果i=0,则序号为i的结点为根结点,无双亲结点。 (2)如果2i+1<n,则序号为i的结点的左孩子结点的序号为2i+1;如果2i+1≥n,则序号为i的结点无左孩子。 (3)如果2i+2<n,则序号为i的结点的右孩子结点的序号为2i+2;如果2i+2≥n,则序号为i的结点无右孩子。 堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]。即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。

02

扫码

添加站长 进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

    运营活动

    活动名称
    广告关闭
    领券