下标小于链表长度的一半时，从前往后遍历；否则从后往前遍历，这样从理论上说，就节省了一半的时间。
如果下标为 0 或者 list.size() - 1 的话，时间复杂度为 O ( 1 ) O(1) O(1)。这种情况下，可以使用 getFirst() 和 getLast() 方法。
public E getFirst() { final LinkedList.Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } public E getLast() { final LinkedList.Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; }
first 和 last 在链表中是直接存储的，所以时间复杂度为 O ( 1 ) O(1) O(1)。
2）add(E e) 方法默认将元素添加到链表末尾，所以时间复杂度为 O ( 1 ) O(1) O(1)。
public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final LinkedList.Node<E> l = last; final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
3）add(int index, E element) 方法将新的元素插入到指定的位置，需要先通过遍历查找这个元素，然后再进行插入，所以时间复杂度为 O ( n ) O(n) O(n)。
public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); }
如果下标为 0 或者 list.size() - 1 的话，时间复杂度为 O ( 1 ) O(1) O(1)。这种情况下，可以使用 addFirst() 和 addLast() 方法。
public void addFirst(E e) { linkFirst(e); } private void linkFirst(E e) { final LinkedList.Node<E> f = first; final LinkedList.Node<E> newNode = new LinkedList.Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; }
linkFirst() 只需要对 first 进行更新即可。
public void addLast(E e) { linkLast(e); } void linkLast(E e) { final LinkedList.Node<E> l = last; final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
linkLast() 只需要对 last 进行更新即可。
需要注意的是，有些文章里面说，LinkedList 插入元素的时间复杂度近似 O ( 1 ) O(1) O(1)，其实是有问题的，因为 add(int index, E element) 方法在插入元素的时候会调用 node(index) 查找元素，该方法之前我们之间已经确认过了，时间复杂度为 O ( n ) O(n) O(n)，即便随后调用 linkBefore() 方法进行插入的时间复杂度为 O ( 1 ) O(1) O(1)，总体上的时间复杂度仍然为 O ( n ) O(n) O(n) 才对。
void linkBefore(E e, LinkedList.Node<E> succ) { // assert succ != null; final LinkedList.Node<E> pred = succ.prev; final LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }
4）remove(int index) 方法将指定位置上的元素删除，考虑到需要调用 node(index) 方法查找元素，所以时间复杂度为 O ( n ) O(n) O(n)。
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } E unlink(LinkedList.Node<E> x) { // assert x != null; final E element = x.item; final LinkedList.Node<E> next = x.next; final LinkedList.Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }
通过时间复杂度的比较，以及源码的分析，我相信小伙伴们在选择的时候就有了主意，对吧？
需要注意的是，如果列表很大很大，ArrayList 和 LinkedList 在内存的使用上也有所不同。LinkedList 的每个元素都有更多开销，因为要存储上一个和下一个元素的地址。ArrayList 没有这样的开销。
但是，ArrayList 占用的内存在声明的时候就已经确定了（默认大小为 10），不管实际上是否添加了元素，因为复杂对象的数组会通过 null 来填充。LinkedList 在声明的时候不需要指定大小，元素增加或者删除时大小随之改变。
另外，ArrayList 只能用作列表；LinkedList 可以用作列表或者队列，因为它还实现了 Deque 接口。
我在写这篇文章的时候，遇到了一些问题，所以请教了一些大厂的技术大佬，结果有个朋友说，“如果真的不知道该用 ArrayList 还是 LinkedList，就选择 ArrayList 吧！”
我当时以为他在和我开玩笑呢，结果通过时间复杂度的分析，好像他说得有道理啊。查询的时候，ArrayList 比 LinkedList 快，这是毋庸置疑的；插入和删除的时候，之前有很多资料说 LinkedList 更快，时间复杂度为 O ( 1 ) O(1) O(1)，但其实不是的，因为要遍历列表，对吧？
反而 ArrayList 更轻量级，不需要在每个元素上维护上一个和下一个元素的地址。
我这样的结论可能和大多数文章得出的结论不符，那么我想，选择权交给小伙伴们，你们在使用的过程中认真地思考一下，并且我希望你们把自己的思考在留言区放出来。
