前面一节介绍了ArrayList，本节介绍LinkedList。LinkedList也是List接口的实现类，与ArrayList不同之处是采用的存储结构不同，ArrayList的数据结构为线性表，而LinkedList数据结构是链表。链表数据结构的特点是每个元素分配的空间不必连续、插入和删除元素时速度非常快、但访问元素的速度较慢。
LinkedList是一个双向链表, 当数据量很大或者操作很频繁的情况下，添加和删除元素时具有比ArrayList更好的性能。但在元素的查询和修改方面要弱于ArrayList。LinkedList类每个结点用内部类Node表示，LinkedList通过first和last引用分别指向链表的第一个和最后一个元素，当链表为空时，first和last都为NULL值。LinkedList数据结构如下图所示：
图 14-11 LinkedList数据结构
LinkedList类内部的Node结点代码如下：
//存储对象的结构 Node, LinkedList的内部类
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;
}
}Node节点一共有三个属性：item代表节点值，prev代表节点的前一个节点，next代表节点的后一个节点。每个结点都有一个前驱和后继结点，并且在 LinkedList中也定义了两个变量分别指向链表中的第一个和最后一个结点。
transient Node<E> first;
transient Node<E> last;
1、添加元素到LinkedList
LinkedList提供了多个添加元素的方法：
● boolean add(E e)
在链表尾部添加一个元素，如果成功，返回true，否则返回false。
● void addFirst(E e)
在链表头部插入一个元素。
● addLast(E e)
在链表尾部添加一个元素。
● void add(int index, E element)
在指定位置插入一个元素。
添加元素到LinkedList示例代码如下:
package adddemo;
import java.util.LinkedList;
public class LinkedListAddDemo {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("first");
linkedList.add("second");
linkedList.add("third");
System.out.println(linkedList);
linkedList.addFirst("addFirst");
System.out.println(linkedList);
linkedList.addLast("addLast");
System.out.println(linkedList);
linkedList.add(2, "addByIndex");
System.out.println(linkedList);
}
}代码通过add、addFirst、addLast方法加入元素，并通过println输出链表元素。输出结果如下图所示：
图 14-12 LinkedListAddDemo输出结果
2、从LinkedList中删除元素
LinkedList提供了多个删除元素的方法：
● boolean remove(Object o)
从当前链表中移除指定的元素。
● E remove(int index)
从当前链表中移除指定位置的元素。
● E removeFirst()
从当前链表中移除第一个元素。
● E removeLast()
从当前链表中移除最后一个元素。
● E remove()
从当前链表中移除第一个元素，同removeLast()相同。
从LinkedList删除元素示例代码如下:
package com.milihua.remove;
import java.util.LinkedList;
public class LinkedListRemoveDemo {
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("first");
linkedList.add("second");
linkedList.add("second");
linkedList.add("third");
linkedList.add("four");
linkedList.add("five");
System.out.println(linkedList);
linkedList.remove();
System.out.println("remove: " + linkedList);
linkedList.remove("second");
System.out.println("remove(Object): " + linkedList);
linkedList.remove("six");
System.out.println("remove(Object) not exist: " + linkedList);
linkedList.remove(2);
System.out.println("remove(index): " + linkedList);
linkedList.removeFirst();
System.out.println("removeFirst: " + linkedList);
linkedList.removeLast();
System.out.println("removeLast:" + linkedList);
System.out.println("----------------------------------");
linkedList.clear();
linkedList.add("first");
linkedList.add("second");
linkedList.add("first");
linkedList.add("third");
linkedList.add("first");
linkedList.add("five");
System.out.println(linkedList);
linkedList.removeFirstOccurrence("first");
System.out.println("removeFirstOccurrence: " + linkedList);
linkedList.removeLastOccurrence("first");
System.out.println("removeLastOccurrence: " + linkedList);
}
}代码通过add方法加入元素，再通过remove、removeFirst、removeLast等方法移除元素，并通过println输出操作后的链表元素。输出结果如下图所示：
图 14-13 LinkedListRemoveDemo输出结果
3、从LinkedList中获取元素
LinkedList提供了多个获取元素的方法：
● E get(int index)
从当前链表中获取指定位置的元素。
● E getFirst()
从当前链表中获取第一个元素。
● E getLast()
从当前链表中获取最后一个元素。
从LinkedList获取元素示例代码如下:
package com.milihua.getdemo;
import java.util.LinkedList;
public class LinkedListGetDemo {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("first");
linkedList.add("second");
linkedList.add("second");
linkedList.add("third");
linkedList.add("four");
linkedList.add("five");
System.out.println(linkedList);
linkedList.get(3);
System.out.println("get(index): " + linkedList.get(3));
linkedList.getFirst();
System.out.println("getFirst: " + linkedList.getFirst());
linkedList.getLast();
System.out.println("getLast: " + linkedList.getLast());
System.out.println(linkedList);
}
}代码通过add方法加入元素，再通过get、getFirst、getLast方法获取元素，并通过println输出操作后的链表元素。输出结果如下图所示：
图 14-14 LinkedListGetDemo输出结果
4、LinkedList的遍历方法
同前面介绍的集合类遍历方式一样，LinkedList可以通过迭代器、foreach语句、for循环语句等方法遍历集合的所有元素。
遍历LinkedList元素示例代码如下:
package com.milihua.traverse;
import java.util.Iterator;
import java.util.LinkedList;
public class LinkedListTraverseDemo {
public static void main(String[] args) {
LinkedList<Integer> llist = new LinkedList<Integer>();
for (int i = 0; i < 100000; i++)
llist.addLast(i);
//通过一般for循环来遍历LinkedList
long start = System.currentTimeMillis();
int size = llist.size();
for (int i=0; i<size; i++) {
llist.get(i);
}
long end = System.currentTimeMillis();
long total = end - start;
System.out.println("byCommonFor------->" + total+" ms");
//通过迭代器来遍历LinkedList
start = System.currentTimeMillis();
for(Iterator iter = llist.iterator(); iter.hasNext();)
iter.next();
end = System.currentTimeMillis();
total = end - start;
System.out.println("byIterator------->" + total+" ms");
//通过foreach来遍历LinkedList
start = System.currentTimeMillis();
for (Integer integ:llist)
;
end = System.currentTimeMillis();
total = end - start;
System.out.println("byForEach------->" + total+" ms");
}
}代码采用for循环、迭代器、foreach方式，遍历包含10万个元素的LinkedList，通过输出结果可以看出，foreach语句效率最高，其次是迭代器，效率最差的是for循环。输出结果如下图所示：
图 14-15 LinkedListTraverseDemo输出结果
■ 知识点拨
LinkedList存储元素的数据结构是双向链表结构，由存储元素的结点连接而成，每一个节点都包含前一个节点的引用，后一个节点的引用和节点存储的值。当一个新节点插入时，只需要修改其中保持先后关系的节点的引用即可。