今天我们说一下 LinkedList ,在列表的使用中,我们很多时候会纠结于列表的选择,是选择数组实现的 ArrayList 还是选择链表实现的 LinkedList.
属性
列表的基本属性有三个,和 ArrayList 类似,第一个属性是:
列表大小
用来表示列表存储的元素个数,
链表的扩容非常自由,所以它的初始化容量是0
transient int size = 0;
两个数据元素
LinkedList 是一个双向链表,所以它有两个重要元素,就是头和尾.
transient Node<E> first;
transient Node<E> last;
其中我们有一个 Node 对象.
这是一个很常见的对象,它有着元素内容,前后的元素的引用.
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
调整链表
LinkedList 提供几个内部的调整方法,比如:在最前面新增,在最后新增,在某个元素前面新增,移除最前面的,移除最后面的,移除某个元素.
这些操作基本上是对于链表中点的引用的调整,来实现这些个方法的.具体的不详细赘述.
返回某个元素
我们都知道列表相对于数组最方便的地方在于新增元素,因为我们只需要将点连接到后面就可以了.而不需要考虑在新增一个元素的时候去检查数组长度.
但是相对于这一点来说,链表也有不方便的一点,就是去获取某个特定的元素:
Node<E> node(int 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;
}
}
在 这里我们看到了,当我们需要获取第 n 个元素的时候,链表需要先检查我们的第 n 个元素是举例头和尾哪个点更近一些,之后再从头或尾开始计算,一个一个去遍历,直到到达我们所需要的点为止.
所以这个操作要消耗很多的行为,所以当数据量很大的时候,这种寻找一个点的方式就会变得很慢.
当然,这种慢是仅限于在取出的点距离头尾相对较远的情况,如果取出的点是距离头尾很近的情况下,这种速度的影响其实微乎其微.
ArrayList 和 LinkedList 的差异
所以我们根据上面可以得到结论:
- 当对于数据列表只是单纯的存储的情况下,
LinkedList的效率要更高一些,因为它避免了在新增一个元素的时候为了考虑扩容的情况所消耗的成本.- 当对于数据列表需要频繁取值的情况下,
ArrayList的效率要更高一点,因为数组在查询某个元素的情况下是可以直接定位到对应的元素位置.
所以我们可以看出,在使用列表的时候,列表的选择其实对于我们的运行效率产生了相当的影响.
关于 LinkedList 我们就研究到这里,之后我们有机会会继续研究其它的集合类.
欢迎关注我的博客: 既然来了就坐坐吧
小站刚开始起步,欢迎您的驾到.
