双向链表实现的list
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
看字段就知道他大概怎么玩的了
总结
- 首尾增加元素开销固定,O(1)
- 不支持随机访问,查询复杂度O(n)
- 空间占比大,每一个节点都需要创建一个Node对象
- ArrayList想要在指定位置插入或删除元素时,主要耗时的是System.arraycopy动作,会移动index后面所有的元素;LinkedList主耗时的是要先通过for循环找到index,然后直接插入或删除。这就导致了两者并非一定谁快谁慢