LinkedList简介
LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList实现List接口，能对它进行队列操作。
LinkedList实现Deque接口，即能将LinkedList当作双端队列使用。
LinkedList实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList是非同步的。
AbstractSequentialList实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些函数。这些接口都是随机访问List的，LinkedList是双向链表；既然它继承于AbstractSequentialList，就相当于已经实现了“get(int index)这些接口”。
LinkedList与Collection关系如下图：
LinkedList的本质是双向链表。
(01) LinkedList继承于AbstractSequentialList，并且实现了Dequeue接口。
(02) LinkedList包含两个重要的成员：header和size。
header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。
size是双向链表中节点的个数。
总结：
(01) LinkedList实际上是通过双向链表去实现的。
它包含一个非常重要的内部类：Entry。Entry是双向链表节点所对应的数据结构，它包括的属性有：当前节点所包含的值，上一个节点，下一个节点。
(02) 从LinkedList的实现方式中可以发现，它不存在LinkedList容量不足的问题。
(03) LinkedList的克隆函数，即是将全部元素克隆到一个新的LinkedList对象中。
(04) LinkedList实现java.io.Serializable。当写入到输出流时，先写入“容量”，再依次写入“每一个节点保护的值”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。
(05) 由于LinkedList实现了Deque，而Deque接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。
LinkedList遍历方式
LinkedList支持多种遍历方式。建议不要采用随机访问的方式去遍历LinkedList，而采用逐个遍历的方式。
(01) 第一种，通过迭代器遍历。即通过Iterator去遍历。
for(Iterator iter = list.iterator(); iter.hasNext();)
iter.next();
(02) 通过快速随机访问遍历LinkedList
int size = list.size();
for (int i=0; i<size; i++) {
list.get(i);
}
(03) 通过另外一种for循环来遍历LinkedList
for (Integer integ:list)
;
(04) 通过pollFirst()来遍历LinkedList
while(list.pollFirst() != null)
;
(05) 通过pollLast()来遍历LinkedList
while(list.pollLast() != null)
;
(06) 通过removeFirst()来遍历LinkedList
try {
while(list.removeFirst() != null)
;
} catch (NoSuchElementException e) {
}
(07) 通过removeLast()来遍历LinkedList
try {
while(list.removeLast() != null)
;
} catch (NoSuchElementException e) {
}
测试其中遍历方式效率的代码如下：
package lxh.demo.listdemotest; import java.util.Iterator; import java.util.LinkedList; /** * 测试LinkedList的几种遍历方式和效率 * @author Ray * */ public class LinkedListThruTest { public static void main(String[] args) { LinkedList list = new LinkedList(); for(int i = 0; i < 50000; i++) { list.add(i); } iteratorLinkedListThruIterator(list); iteratorLinkedListThruForeach(list); iteratorThroughFor2(list); } /* * 通过Iterator遍历LinkedList */ private static void iteratorLinkedListThruIterator(LinkedList list) { //记录开始时间 long startTime = System.currentTimeMillis(); for(Iterator iter = list.iterator(); iter.hasNext();) { iter.next(); } long endTime = System.currentTimeMillis(); System.out.println("iteratorLinkedListThruIterator: " + (endTime-startTime) + "ms"); } /* * 通过快速随机访问遍历LinkedList */ private static void iteratorLinkedListThruForeach(LinkedList list) { //记录开始时间 long startTime = System.currentTimeMillis(); for(int i = 0; i < list.size(); i++) { list.get(i); } //记录结束时间 long endTime = System.currentTimeMillis(); System.out.println("iteratorLinkedListThruForeach: " + (endTime-startTime) + "ms"); } /* * 通过另一种for循环来遍历LinkedList */ private static void iteratorThroughFor2(LinkedList list) { //记录开始时间 long startTime = System.currentTimeMillis(); for(Object integ:list) { ; } //记录结束时间 long endTime = System.currentTimeMillis(); System.out.println("iteratorThroughFor2: " + (endTime-startTime) + "ms"); } } |
测试结果:
iteratorLinkedListThruIterator: 3ms iteratorLinkedListThruForeach: 953ms iteratorThroughFor2: 1ms |
总结:无论如何，千万不要通过随机访问去遍历LinkedList！
LinkedList示例
下面通过一个示例来学习如何使用LinkedList的常用API
package lxh.demo.listdemotest; import java.util.LinkedList; /** * LinkedList测试程序 * @author 沐兮沐楚 * */ public class LinkedListTest01 { public static void main(String[] args) { testLinkedListAPIs(); } /* * 测试LinkedList中部分API */ private static void testLinkedListAPIs() { String val = null; //新建一个LinkedList LinkedList llist = new LinkedList(); //依次添加元素 llist.add("1"); llist.add("2"); llist.add("3"); //将"4"添加到第一个位置 llist.add(0, "4"); System.out.println("element: " + llist); System.out.println("\nTest \"addFirst(),removeFirst(),getFirst()\""); //1.将10添加到第一个位置 llist.addFirst("10"); System.out.println("llist: " + llist); //2.将第一个元素删除 System.out.println("llist.removeFirst(): " + llist.removeFirst()); System.out.println("llist: " + llist); //3.获取第一个元素 System.out.println("llist.getFirst(): " + llist.getFirst()); System.out.println("\nTest \"offerFirst(), pollFirst(), peekFirst()\""); //1.将10添加到第一个位置,返回true llist.offerFirst("10"); System.out.println("llist: " + llist); //2.将第一个元素删除,失败返回null System.out.println("llist.pollFirst(): " + llist.pollFirst()); System.out.println("llist: " + llist); //3.获取最后一个元素 System.out.println("llist.getLast(): " + llist.getLast()); //将第三个元素设置300. 不建议在LinkedList中使用此操作,效率低 llist.set(2, "300"); //获取第三个元素. 不建议在LinkedList中使用此操作,因为效率低 System.out.println("\nget(2): " + llist.get(2)); //将LinkedList转换为数组 String[] arr = (String[]) llist.toArray(new String[0]); for(String str : arr) { System.out.println("str: " + str); } } } |
测试结果:
element: [4, 1, 2, 3] Test "addFirst(),removeFirst(),getFirst()" llist: [10, 4, 1, 2, 3] llist.removeFirst(): 10 llist: [4, 1, 2, 3] llist.getFirst(): 4 Test "offerFirst(), pollFirst(), peekFirst()" llist: [10, 4, 1, 2, 3] llist.pollFirst(): 10 llist: [4, 1, 2, 3] llist.getLast(): 3 get(2): 300 str: 4 str: 1 str: 300 str: 3 |
总结起来如下表格：
第一个元素（头部） 最后一个元素（尾部）
抛出异常 特殊值 抛出异常 特殊值
插入 addFirst(e) offerFirst(e) addLast(e) offerLast(e)
移除 removeFirst() pollFirst() removeLast() pollLast()
检查 getFirst() peekFirst() getLast() peekLast()