Vector，ArrayList，LinkedList的异同
2019-11-09 16:52:48
供稿：网友
一.概况三者都来自于List，其中vector，ArrayList底层实现是数组，而LinkedList的底层实现是单链表。三者有如下特点：1.Vector，ArrayList查找快，增删慢。LinkedList相反，查找慢，增删快；2.vector是线程安全的。ArrayList，LinkedLIst是线程不安全的二.本文主要分析内容1.ArrayList和LInkedLIst为什么有如上差异，增删数据的速度差距；为什么查找多，增删少时候用ArrayList，相反情况用LinkedList2.数组和链表的概念和各自的特性3.动态分配内存，静态分配内存的概念和特点4.Android内存分区和各自的特点用途三.问题的解决1.“Vector，ArrayList查找快，增删慢。LinkedList相反，查找慢，增删快”的原因：由于前两者的底部实现是数组而后者的底部实现是单链表。2.为什么数组和链表在查询和增加删除会存在前者查找快，增删慢的原因：先看区别：数组静态分配内存，链表动态分配内存；数组元素在栈区，链表元素在堆区；数组在内存中连续，链表不连续；数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。所以：查找元素时候在数组中可以根据下标直接定位，而链表只能顺序查询，数组中即要去第i个元素，a[i]即可，而链表是线性结构，要取第i个元素，需用指针往后遍历i次才能找到（数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)），造成前者查快，后者查慢。增删的时候由于数组在内存中是连续的增加或者删除一个别的元素也都要跟着动，而链表在内存中是不连续的只是持有下个元素的node信息，所以增加和删除元素时候只要前后的元素做改变就可以了，也就造成前者增删慢，后者快（数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)）。3. 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。同时数组从栈中静态分配空间, 对于程序员方便快速,但自由度小；链表动态地进行存储分配，可以适应数据动态地增减的情况。4. Android内存分区：1.寄存器：最快的存储区, 由编译器根据需求进行分配,我们在程序中无法控制.2. 栈：存放基本类型的变量数据和对象的引用，但对象本身不存放在栈中，而是存放在堆（new 出来的对象）或者常量池中（字符串常量对象存放在常量池中。）3. 堆：存放所有new出来的对象。4. 静态域：存放静态成员（static定义的）5. 常量池：存放字符串常量和基本类型常量（public static final）。这里我们主要关心栈，堆。对于栈和常量池中的对象可以共享，对于堆中的对象不可以共享。栈中的数据大小和生命周期是可以确定的，当没有引用指向数据时，这个数据就会消失。堆中的对象的由垃圾回收器负责回收，因此大小和生命周期不需要确定 ，具有很大的灵活性。四.总结1.三者各自的特性2.ArrayList和LInkedLIst的特性对比和形成差异的原因3.简单介绍了Android中内存RAM。这里只是简单的说了一下堆栈，后面会有一个文章来介绍我们的代码到底在内存的哪里运行参考：http://blog.csdn.net/aa449649823/article/details/50116895
