以下内容纯属记录个人对知识的理解，不对之处欢迎指出
1、ArrayList和 LinkedList 都实现了List接口，相同部分：
boolean add(Object o) ：向集合中加入一个对象的引用
void clear()：删除集合中所有的对象，即不再持有这些对象的引用
boolean isEmpty() ：判断集合是否为空
boolean contains(Object o) ： 判断集合中是否持有特定对象的引用
Iterartor iterator() ：返回一个Iterator对象，可以用来遍历集合中的元素
boolean remove(Object o) ：从集合中删除一个对象的引用
int size() ：返回集合中元素的数目
Object[] toArray() ： 返回一个数组，该数组中包括集合中的所有元素
关于：Iterator() 和toArray() 方法都用于集合的所有的元素，前者返回一个Iterator对象，后者返回一个包含集合中所有元素的数组。
2、 ArrayList和 LinkedList不同部分
2.1.ArrayList采用数组结构存储数据，按索引随机访问数据效率较高
2.2.LinkedList采用链式数组结构存储数据，添加和删除效率较高
2.3.LinkedList多提供了addFirst、addLast、removeFirst、removeFirstOccurrence、removeLast、removeLastOccurrence等方法。
3.效率理解
数组和链表的区别可以参考数组与链表的区别 讲解
3.1时间效率速度
ArrayList的内部实现是基于基础的对象数组的，因此，它使用get方法访问列表中的任意一个元素时(random access)，它的速度要比LinkedList快。LinkedList中的get方法是按照顺序从列表的一端开始检查，直到另外一端。对LinkedList而言，访问列表中的某个指定元素没有更快的方法了。
3.2空间复杂度
在LinkedList中有一个私有的内部类，定义如下：
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev,Eelement,Node next) {
this.item= element;
this.next= next;
this.prev= prev;
}
}
每个Node对象reference列表中的一个元素，同时还有在LinkedList中它的上一个元素和下一个元素。一个有多个元素的LinkedList对象将有多个链接在一起的Node对象，每个对象都对应于列表中的一个元素。这样的话，在一个LinkedList结构中将有一个很大的空间开销，因为它要存储这多个Node对象的相关信息。
ArrayList使用一个内置的数组来存储元素，所以在插入数据的时候，数组长度不够时，会增加数组长度，数组增加的长度采用以下方式增加
private void grow(intminCapacity) {
// overflow-conscious code
int oldCapacity =elementData.length;
int newCapacity = oldCapacity + (oldCapacity >>1);
if(newCapacity - minCapacity <0)
newCapacity = minCapacity;
if(newCapacity -MAX_ARRAY_SIZE>0)
newCapacity =hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData= Arrays.copyOf(elementData,newCapacity);
}
所以没有足够的空间来存放新的元素，数组将不得不被重新进行分配以便能够增加新的元素。会存在一种数组长度>数据长度造成空间浪费同时也需要复制完所有的数组内容。
纯属个人理解，希望不会误导读者。
网友评论