Java容器浅入深出之LinkedList

List接口下的主要两个实现类, ArrayList已经讨论过了。 这次再看看LinkedList的底层实现。

底层实现

LinkedList所实现的接口和继承的父类和ArrayList差不多, 但是它多实现了一个Deque接口。

LinkedList是基于链表实现的,其中每个元素其实是每个节点内部的element。

LinkedList只保存一个空的节点,这个节点的上一个节点就是队尾, 下一个节点就是队首。

LinkedList的添加元素操作相对于ArrayList是非常快的,因为ArrayList需要对其实例内部的数组进行重新布局整理,而LinkedList只需要在内部的链表的某个位置插入一个节点, 这个节点的element就是插入的元素。 具体的实现是addBefore方法。

而LinkedList在内部元素的随机访问上比ArrayList慢多了,因为ArrayList是直接对内部数组进行索引的,而LinkedList是从实例内部存储的空节点(这个空节点的上一个节点是队首,下一个节点是队尾)开始遍历。需要通过循环,对每一个节点进行访问(不但需要访问节点,还得访问节点内部的属性),因此性能上比ArrayList低多了。

Iterator的实现上也有区别。ArrayList使用的还是父类AbstractList的迭代器实现而LinkedList自己在类内部实现了迭代器。

LinkedList的方法有很多相似的,也有很多1.5、 1.6之后添加的新方法,然而而这些新方法仅仅是对此类内部的原有方法进行了封装,换汤不换药。