ＪＡＶＡ器皿浅入深出之LinkedList

ＪＡＶＡ容器浅入深出之LinkedList

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

 

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

 

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

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

 

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

 

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

 

迭代器实现上也有区别。 ArrayList使用的还是父类AbstractList的迭代器实现

而LinkedList自己在类内部实现了迭代器。

 

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