ArrayList与linkedList的用法区别及扩容方式 |
您所在的位置：网站首页 › arraylist与list的区别 › ArrayList与linkedList的用法区别及扩容方式 |
ArrayList与linkedList的用法区别及扩容方式
|
ArrayList与linkedList的用法区别及扩容方式
1. Array Array（数组）是基于索引(index)的数据结构，它使用索引在数组中搜索和读取数据是很快的。 Array获取数据的时间复杂度是O(1),但是要删除数据却是开销很大，因为这需要重排数组中的所有数据, (因为删除数据以后, 需要把后面所有的数据前移) 缺点:数组初始化必须指定初始化的长度, 否则报错 例如： int[] a = new int[4];//推介使用int[] 这种方式初始化 int c[] = {23,43,56,78};//长度：4，索引范围：[0,3]2. List List—是一个有序的集合，可以包含重复的元素，提供了按索引访问的方式，它继承Collection。 List有两个重要的实现类：ArrayList和LinkedList List是一个接口，不可以实例化, 不能写成如下： List list = new List();//错误类继承关系
3. ArrayList ArrayList: 可以看作是能够自动增长容量的数组ArrayList的toArray方法返回一个数组ArrayList的asList方法返回一个列表 ArrayList底层的实现是Array, 数组扩容实现
4. 使用数组长度分配空间性能对比 注意:长度尽量使用2的幂作为长度, 计算机分配空间大都使用次幂去分配, 减少碎片空间 我们下来看一下代码: package javatest; import java.util.ArrayList; import java.util.List; /** * @ClassName Jtest * @Description TODO * @Author lingxiangxiang * @Date 4:54 PM * @Version 1.0 **/ public class Jtest { public static int length = 1048576; //10的20次幂 public static List list1 = new ArrayList(); public static List list2 = new ArrayList(length); public static void addList(int sign) { long start = System.currentTimeMillis(); for (int i = 0; i < length; i++) { if (sign == 0) { list1.add(sign); } else { list2.add(sign); } } long end = System.currentTimeMillis(); System.out.println(sign + " exec time is: " + (end - start)); } public static void main(String[] args) { addList(0); addList(1); } }执行结果: 0 exec time is: 251 exec time is: 17 ArrayList在初始化的时候指定长度肯定是要比不指定长度的性能好很多, 这样不用重复的申请空间, 复制数组, 销毁老的分配空间了 5. LinkList LinkList是一个双链表,在添加和删除元素时具有比ArrayList更好的性能. 但在get与set方面弱于ArrayList.当然,这些对比都是指数据量很大或者操作很频繁。
链表不需要连续的空间, 大小不确定 6. 对比 时间复杂度 操作数组链表随机访问O(1)O(N)头部插入O(N)O(1)头部删除O(N)O(1)尾部插入O(1)O(1)尾部删除O(1)O(1)小结 同样查找, 时间复杂度都是O(N), 但是数组要比链表快因为数组的连续内存, 会有一部分或者全部数据一起进入到CPU缓存, 而链表还需要在去内存中根据上下游标查找, CPU缓存比内存块太多数据大小固定, 不适合动态存储, 动态添加, 内存为一连续的地址, 可随机访问, 查询速度快链表代销可变, 扩展性强, 只能顺着指针的方向查询, 速度较慢7. ArrayList的源码分析 7.1 ArrayList的主要成员变量 private static final int DEFAULT_CAPACITY = 10; // ArrayList的默认长度是多少 private static final Object[] EMPTY_ELEMENTDATA = {}; // ArrayList的默认空元素链表 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // ArrayList存放的数据 transient Object[] elementData; // non-private to simplify nested class access // ArrayList的长度 private int size; 7.2 ArrayList的构造函数 // 构造一个初始化容量为10的空列表 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_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); } } // 构造一个包含指定集合的元素列表, 按照它们由集合迭代器返回的顺序 public ArrayList(Collection |
【本文地址】
今日新闻 |
推荐新闻 |