2.3 List集合的另一种典型实现——LinkedList类

上一节介绍了List集合的一种典型实现ArrayList，明白了ArrayList是由数组构成的，本节介绍List集合的另一种典型实现——LinkedList类，这是一个由链表构成的类。

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是它并不会按线性的顺序存储数据，而是在每一个节点里存储到下一个节点的指针（Pointer）。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取数据的优点，同时链表由于增加了节点的指针域，空间开销比较大。

了解完链表后，下面给出LinkedList的定义。

2.3.1 LinkedList定义

LinkedList是一个用链表实现的集合，元素有序且可以重复。LinkedList类结构如图2-3所示。

和ArrayList集合一样，LinkedList集合也实现了Cloneable接口和Serializable接口，分别用来支持克隆以及支持序列化。List接口则定义了一套List集合类型的方法规范。

注意：

相对于ArrayList集合，LinkedList集合多了一个Deque接口，这是一个双向队列接口，双向队列就是两端都可以进行增加和删除操作。

2.3.2 字段属性

字段属性代码显示如下：

注意：

这里出现了一个Node类，这是LinkedList类中的一个内部类，其中每一个元素代表一个Node类对象，LinkedList集合就是由许多个Node对象类似于手拉着手构成，如图2-4所示。

上图的LinkedList有四个元素，也就是由4个Node对象组成，size=4，head指向第一个elementA，tail指向最后一个节点elementD。

2.3.3 构造函数

LinkedList有两个构造函数，第一个是默认的空的构造函数，第二个是将已有元素的集合Collection的实例添加到LinkedList中，调用的是addAll()方法，这个方法下面介绍。

注意：

LinkedList没有初始化链表大小的构造函数，因为链表不像数组，一个定义好的数组是必须先要有确定的大小，然后再去分配内存空间，而链表不一样，它没有确定的大小，通过指针的移动来指向下一个内存地址的分配。

2.3.4 添加元素

1. addFirst（E e）

将指定元素添加到链表头，如图2-5所示。

2. addLast（E e）和add（E e）

将指定元素添加到链表尾，如图2-6所示。

3. add（int index，E element）

将指定的元素插入此列表中的指定位置，如图2-7所示。

2.3.5 删除元素

删除元素和添加元素一样，也是通过更改指向上一个节点和指向下一个节点的引用即可，这里就不作图形展示了。

1. remove()和removeFirst()

该命令为从此列表中移除并返回第一个元素。

2. removeLast()

该命令为从该列表中删除并返回最后一个元素。

3. remove（int index）

该命令为删除此列表中指定位置的元素。

4. remove（Object o）

如果该命令存在，则表示从该列表中删除第一次出现的指定元素。

此方法本质上和remove（int index）没多大区别，通过循环判断元素进行删除，需要注意的是，是删除第一次出现的元素，不是所有的。

2.3.6 修改元素

通过调用set（int index，E element）方法，用指定的元素替换此列表中指定位置的元素。

这里主要是通过node（index）方法获取指定索引位置的节点，然后修改此节点位置的元素即可。

2.3.7 查找元素

1. getFirst()

该命令为返回此列表中的第一个元素。

2. getLast()

该命令为返回此列表中的最后一个元素。

3. get（int index）

该命令为返回指定索引处的元素。

4. indexOf（Object o）

该命令为返回此列表中指定元素第一次出现的索引，如果此列表不包含元素，则返回-1。

2.3.8 遍历集合

1. 普通for循环

上述代码很简单，利用LinkedList的get（int index）方法，遍历出所有的元素。

但是需要注意的是，get（int index）方法每次都要遍历该索引之前的所有元素，如代码中的一个LinkedList集合，放入了A，B，C，D四个元素。总共需要四次遍历：

第一次遍历打印A：只需遍历一次。

第二次遍历打印B：需要先找到A，然后再找到B打印。

第三次遍历打印C：需要先找到A，然后找到B，最后找到C打印。

第四次遍历打印D：需要先找到A，然后找到B和C，最后找到D打印。

这样如果集合元素很多，越查找到后面（当然此处的get方法进行了优化，查找前半部分从前面开始遍历，查找后半部分从后面开始遍历，但是需要的时间还是很多）花费的时间越多。那么如何改进呢？

2. 迭代器

在LinkedList集合中也有一个内部类ListItr，方法实现大体相似，通过移动游标指向每一次要遍历的元素，不用在遍历某个元素之前都从头开始。其方法实现也比较简单：

这里需要重点注意的是modCount字段，前面在增加和删除元素的时候，都会进行自增操作modCount，这是因为如果一边迭代，一边用集合自带的方法进行删除或者新增操作时，都会抛出异常。（使用迭代器的增删方法不会抛异常）。

2.3.9 迭代器和for循环效率差异

打印结果为：

10000个元素两者之间都相差一倍多的时间，如果是十万或百万个元素，那么两者之间相差的速度会越来越大。下面通过图形来解释，如图2-8所示。

普通for循环：每次遍历一个索引的元素之前，都要访问之间所有的索引。

迭代器：每次访问一个元素后，都会用游标记录当前访问元素的位置，遍历一个元素，记录一个位置。如图2-9所示。