LinkedList是基于链表实现的，它的数据结构可以表示为下图
linkedlist.jpg
这里的data每个都是一个Link对象,它的结构如下
private static final class Link<ET> {
ET data;
Link<ET> previous, next;
Link(ET o, Link<ET> p, Link<ET> n) {
data = o;
previous = p;
next = n;
}
}
这里的voidLink是在LinkedList的构造方法中创建的
public LinkedList() {
voidLink = new Link<E>(null, null, null);
voidLink.previous = voidLink;
voidLink.next = voidLink;
}
每次add都会对next，previous重新指向，最终形成上图的结构
add方法
private boolean addLastImpl(E object) {
Link<E> oldLast = voidLink.previous;
Link<E> newLink = new Link<E>(object, oldLast, voidLink);
voidLink.previous = newLink;
oldLast.next = newLink;
size++;
modCount++;
return true;
}
现在说说ArrayList和LinkedList的方法性能上的比较
测试数据：1000条和10000条
add方法：
从实现原理上来看，将道理，应该是ArrayList耗费的时间要长一点，因为它需要对数据进行拷贝、扩容，但实际上测试下来，ArrayList用的时间要少一点，在测试的次数中，所占比达到80%左右。（不知道什么原因，求大神告知）
remove方法：
remove最后一条，ArrayList占优。remove中间的数据，当条数较少时（1000条测试），ArrayList占优，有可能是因为数据拷贝时间要少于LinkedList中的for循环，对比下源码
public E remove(int location) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
Link<E> previous = link.previous;
Link<E> next = link.next;
previous.next = next;
next.previous = previous;
size--;
modCount++;
return link.data;
}
throw new IndexOutOfBoundsException();
}
ArrayList的remove源码请见另一篇文章。
当数据量大了以后，System.arraycopy可能要消耗更多的时间，所以此种情况下，LinkedList占优
get方法：
这个是ArrayList占优的
arrayList的get方法很简单
@SuppressWarnings("unchecked") @Override public E get(int index) {
if (index >= size) {
throwIndexOutOfBoundsException(index, size);
}
return (E) array[index];
}
而LinkedList的get方法需要对指针重新指向
