盐城高端网站建设,清新织梦淘宝客模板淘客网站程序源码,做外汇看新闻在什么网站看,棋牌类网站怎么做ArrayList、LinkedList、与Vector的区别 解读ArrayList 是一个可改变大小的数组LinkedList 是一个双向链表Vector 属强同步类 拓展知识面ArrayList是如何扩容#xff1f;如何利用List实现LRU#xff1f; 解读
List主要有ArrayList、LinkedList与Vector几种实现。这三者都实现… ArrayList、LinkedList、与Vector的区别 解读ArrayList 是一个可改变大小的数组LinkedList 是一个双向链表Vector 属强同步类 拓展知识面ArrayList是如何扩容如何利用List实现LRU 解读
List主要有ArrayList、LinkedList与Vector几种实现。这三者都实现了List接口使用方式也极其相似主要区别在于因为实现方式的不同所以对不同的操作就有不同的效率。
ArrayList 是一个可改变大小的数组
当更多的元素加入到ArrayList中时其大小将会动态的增长内部的元素可以直接通过get与set方法进行访问因为ArrayList本质上就是数组。
LinkedList 是一个双向链表
在添加和删除元素的时间具有比ArrayList更好的性能但是在get与set方面是弱于ArrayList。当然了这些对比都是指数据量很大或者操作很频繁的情况下的对比如果数据量和运算量很小那么就没有对比的意义。
Vector 属强同步类
Vector和ArrayList类似但它属于强同步类。如果你的程序本身是线程安全的(thread-safe没有在多个线程之间共享同一个集合或者对象)那么使用ArrayList是更好的选择。 Vector和ArrayList在更多元素添加进来时会请求更大的空间。Vector每次请求是它自身大小的双倍空间而ArrayList每次对size增长50%。 而LinkedList还实现了Queue个Deque接口该接口与List相比其提供了更多的方法包括offer()、peek()、poll()等。
注意默认情况下ArrayList的初始容量非常小所以如果可以预估数据量的话分配一个较大的初始值才属于最佳操作这样可以减少调整大小的开销。
拓展知识面
ArrayList是如何扩容
首先我们要明白ArrayList是基于数组的这个上面讲到了我们都知道申请数组的时间只能申请一个定长的数组那么List是如何实现数组扩容的呢ArrayList的扩容有几个步骤
检查新增元素后是否会超过数组的容量若超过则进行下一步扩容设置新增容量为原始(旧/老)容量的1.5倍最多不超过2^31-1在Java8中ArrayList的容量最大是Integer.MAX_VALUE-8这是由于在Java8中ArrayList内部实现进行了一些改进使用了一些数组复制的技巧来提高性能和内存的利用率而这些技巧需要额外的8个元素的空间来进行优化。之后呢申请一个容量为1.5倍的数组将原有数组的元素复制到新数组中自此扩容完成。
如何利用List实现LRU
LRU即最近最少使用策略基于时空局部性原理(最近访问的未来也会被访问的)往往作为缓存淘汰的策略如Redis和GuavaMap都使用了这种套胎策略。
我们可以基于LinkedList来实现LRU因为LinkedList基于双向链表每个节点都会记录上一个和下一个的节点具体实现方式如下
public class LruListCacheE {private final int maxSize;private final LinkedListE list new LinkedList();public LruListCache (int maxSize) {this.maxSize maxSize;} public void add(E e) {if(list.size() maxSize) {list.addFrist(e);}else{list.removeLast(); list.addFrist(e);}}public E get(int index) {E e list.get(index);list.remove(e);add(e);return e;}Overridepublic String toString() {return list.toString();}}OK如果不懂数组和链表的区别的话随后我有一个专门的数据结构的专栏会讲到栈和队列、数组和链表以及二叉树的遍历等等内容。会做详细解说。
