在分析之前，我们线看一下具体的ArrayList 和 LinkedList 源码分析
其实看完源码后，我们多多少少能得出如下的结论
线性存储
1. 随机访问优势
public E get(int index) {
//检查下标是否符合
rangeCheck(index);
//直接通过下标访问，还有更快的么
return elementData(index);
}
2, 插入性能堪忧困难
删除也会哦
//添加数据操作
public boolean add(E e) {
//先执行扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//添加数据
elementData[size++] = e;
return true;
}
//确认新的容量是否符合， 返回符合的容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//使用指定容量扩容
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//扩容操作
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//可以在这里看到，容量一旦不够，就需要进行扩容，关键这个扩容是需要，复制完整的原始数据
grow(minCapacity);
}
private void grow(int minCapacity) {
// 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);
elementData = Arrays.copyOf(elementData, newCapacity);
}
链式存储
1.访问元素困难
//暴力遍历查找，所以在大数据查找的时候简直是灾难
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
2. 毫无压力的插入
没有扩容之后，操作看起来变得复杂，其实没了拷贝之后，性能飞起
public boolean addAll(int index, Collection<? extends E> c) {
//检查下标参数
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
//重点在这里，创建链结构
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
//记录修改次数
modCount++;
return true;
}
总结
上面这些实际上是都是在极度条件的下判断出来的, 只有在几百条数据的时候，并且没有删除数据，适合日志这种类型的，我个人还是建议使用 ArrrayList， 为什么 ？
- 真实存储的是引用（4字节），创建数据存储空间，和ArrayList，LinkedList 没关系
- 在创建的时候，尽量给予相当的容量，这样ArrayList的性能能达到最佳的水平
- 这两种数据结构都不支持，并非修改， 支持并发访问
- 频繁的在插入数据，例如，排序, 删除, 还是自觉使用链式存储吧
