ArrayList
ArrayList和array的区别：前者可以存放任意对象(object的子类)，后者只能存放同种元素。前者只能存放对象类型。后者可以存基本类型和对象类型。
ArrayList内部维护了一个动态的object数组，ArrayList的动态增删就是对这个数组的增加和删除。ArrayList是未经同步的。若在多线程环境下访问一个ArrayList实例，并且至少一个线程对其作了结构性修改，那么必须在外部做同步（结构性修改指的是任何添加或者删除了一个或多个元素的操作，以及显示改变内部数组尺寸的操作，set不是结构性修改）。
ArrayList实现了RandomAccess接口即提供了随机访问的功能，在ArrayList中我们可以通过元素的序号快速获取元素对象，这就是快速随机访问。 ArrayList实现了Cloneable接口，即覆盖了函数clone()，能被克隆。ArrayList实现了Serializable接口，意味着ArrayList支持序列化，能通过序列化去传输。ArrayList建议在单线程中使用，多线程中可以选择Vector和CopyOnWriteArrayList(适合读多写少情景，写写之间需要同步，同步是使用reetrantlock实现的。写操作时把数据复制到一份副本中，然后修改副本元素，修改完成后才用副本元素替换老元素)。
elementData是object类型的数组，他保存了添加到ArrayList中的元素，实际上elementData是个动态数组，我们能通过构造函数来指定它的初始容量，如果通过不含参数的构造函数来创建ArrayList，则elementData的容量默认是10，elementData数组的大小会根据ArrayList的容量增长而动态增长。具体增长方式，参考ensureCapacity()函数。size是动态数组的实际大小。
ArrayList的构造函数
第一个构造方法使用提供的initialCapacity来初始化elementData数组的大小。第二个构造方法调用第一个构造方法并传入参数10，即elementData数组大小为10。第三个构造方法将提供的集合转成数组返回给elementData（返回若不是object[]将调用Arrays.copyOf()方法将其转为object[]）
ArrayList的add方法：
当添加一个元素时，要进行扩容检查，然后把元素添加到数组末尾。添加成功后会返回true。若在指定位置添加一个元素，则要先判断索引是否越界，然后进行数组复制，目的是空出index的位置插入element，并将index后的元素位移一个位置
进行扩容时，会把新数组的长度设为旧数组长度的1.5倍，最后进行数组复制操作。
如果向ArrayList中添加一个集合，则要先把集合通过toArray()转换为数组，然后添加到list的数据尾部，最后更新容器大小
ArrayList的remove方法：
remove(int index) 时要进行数组越界检查，并把index后的元素往前移动，数组最后一个元素置空。返回值是被删除的元素
remove(Object o)可以传入obejct参数，删去指定的元素，如果ArrayList中存的是Integer，则remove要传入((Integer)3)才是删去这个指定元素
ArrayList的更新操作：
set方法会返回旧的元素。
查看是否包含：和remove的代码类似，用循环比较
获取ArrayList中的单个对象，用get(int index)方法
ArrayList实现序列化的方式：当写入到输出流时，先写入“容量”，再依次写入每一个元素，当读出输入流时，先读取“容量”，再依次读取每一个元素
ArrayList的遍历方式有三种：使用2的效率最高，使用迭代器的效率最低。
1） 通过迭代器遍历，即通过Iterator去遍历
2） 随机访问，通过索引值去遍历，由于ArrayList实现RandomAccess接口，所以支持通过索引值访问随机元素
3） for循环遍历
ArrayList和Vector的区别：几乎完全相同，后者每次扩容为原来的两倍，前者是1.5倍。后者是强同步类(synchronized)，开销比前者大，访问慢。Stack是Vector的子类
Arrays.asList()方法，返回的ArrayList是一个AbstractList的子类，此类只有set，get等方法，没有add，remove方法。如果：
List<Integer> list = Arrays.asList(1,2,3)，则该list对象不能add，remove
我们可以这样做：
List<Integer> list = new ArrayList<>( Arrays.asList(1,2,3))。
另外：
这里的输出结果是1，原因是，Arrays.asList()中，其接收的参数原型是泛型变长参数来的，而基本类型是不能作为泛型的参数，所以应该使用包装类型。
这样就能得到正确的结果
LinkedList：
LinkedList与ArrayList都实现List接口，只是后者是数组实现，前者是双向循环链表实现。基于链表实现的方式使得其在插入和删除时更优于ArrayList，而随机访问比ArrayList逊色些
LinkedList可以被当作队列或双端队列进行操作。
其实现了List接口，能对它进行队列操作。
其实现了Deque接口，能把它当做双端队列使用。
其实现了Cloneable接口，即覆盖了函数clone()，能克隆。
其实现了Serializable接口，所以支持序列化，能通过序列化传输。
是非同步的。
LinkedList有以上两个属性，size和ArrayList一样用来计数，表示list的数量，header是头结点，Entry是链表的节点对象。Entry是LinkedList的内部类，定义了当前存储的元素，该元素的上一个和下一个元素。
LinkedList的构造函数：LinkedList不用提前指定容量，所以构造函数没有int类型的
LinkedList的add操作
因为是循环双向的，所以在list尾部添加相当于在header前面添加元素。所以在addBefore()中，新节点的下一个节点是header，上一个节点是header.previous即尾节点。可以发现，header作为头结点不保存数据，header中的element永远等于null。增加操作的核心逻辑：1.将元素转换为链表节点。2.增加节点的前后引用(即pre和next分别指向哪个节点)。3.前节点的next指向该节点，后节点的pre指向该节点。
LinkedList的修改操作：重点是entry方法，此方法后面会介绍
LinkedList的删除操作
通过遍历找到要被删除的节点，找到后把此节点的前后引用调整好，将自身置空，让gc可以尽快回收
LinkedList的查询操作：
通过entry方法根据index查询到节点。如下图代码：entry方法中采用了二分查找，判断index与size中间位置的距离，从而决定从header向前还是向后查找。查找操作的效率较低，index对应的元素越靠近中间费的时间越长，而向链表两端插入和删除元素是很高效的，如果不是两端，都需要对链表进行遍历查找
LinkedList看是否包含：
和remove操作类似，都需要遍历链表
LinkedList有peek()获取头元素,peekFirst()获取头元素,peekLast()获取尾元素；poll()和remove()也都有first,last方法
总结：LinkedList的克隆函数，是把全部元素克隆到一个新的LinkedList对象中。LinkedList没有实现RandomAccess接口，使用foreach循环比较快，使用for循环会很慢。
ArrayList和LinkedList的比较：
1. 顺序插入的速度，前者较快。因为它是基于数组实现，数组事先new好了，只要往指定位置塞一个数据就好。后者每次顺序插入时将new一个对象处来，加上一些引用赋值的操作，所以顺序插入时后者必然慢于前者。
2. LinkedList中维护了待插入的元素，还维护了Entry的前置和后继Entry，如果Entry非常多，那么LinkedList将比ArrayList更耗费一些内存。
3. 使用各自效率最高的方式，前者的遍历效率高于后者。
4. 有些说法认为LinkedList做插入和删除更快，其实LinkedList做插入删除慢在寻址，快在只需要改变前后Entry的引用地址。ArrayList插入删除慢在数组元素的批量copy，快在寻址。所以如果待插入，删除的元素是在前半段尤其是非常靠前的位置时，后者效率大大快过前者，因为前者要批量copy大量元素，对于后者，因为是双向的，所以在第2个元素后插入一个数据和在倒数第2个元素后插入一个元素没有差别，但是前者由于要批量copy的元素越来越少，速度必然追上乃至超过后者。
5. 如果不能确定做的插入删除操作在哪儿，建议使用后者，因为其执行效率稳定，而且前者可能会扩容，ArrayList底层数组扩容是一个既消耗时间又消耗空间的操作。
6. 两者都可以调用toArray()方法，转换成一个数组。
7. 两者的remove和contains方法都依赖equals方法。
8. 使用下标访问一个元素，ArrayList的时间复杂度是O(1),LinkedList是O(n)
LinkedList有peek()方法，ArrayList没这个方法。List接口也没有这个方法，必须LinkedList ls = new LinkedList(),ls.peek()只有这样才能调用peek方法
数组和链表的对比：
数组：内存中数组是一块连续的区域，数组需要预留空间，先申请占内存的大小，插入和删除效率低，因为插入时要有数据后移，删除时要有数据前移。随机读取的效率很高。
链表：内存中可以存在任何地方，不要求连续，每个数据都保存了下一个数据的内存地址，增加和删除数据很容易。查找数据的效率低，因为不具有随机访问性，要从第一个数据开始访问。不用指定大小。
标签：LinkedList,ArrayList,元素,List,插入,数组,节点 From： https://www.cnblogs.com/MarkLeeBYR/p/17109776.html