①LinkedList简单介绍

1. 是一个继承于AbstractSequentialList的双向链表。它可以被当成堆栈、队列或双端队列进行操作。
2. 实现了List接口，能对它进行队列操作。
3. 实现了Deque接口，能当作双端队列使用。
4. 实现了Cloneable接口，覆盖了clone(),能克隆。
5. 实现了java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
6. 是非同步的

②LinkedList构造函数

// 默认构造函数LinkedList()// 创建一个LinkedList，保护Collection中的全部元素。LinkedList(Collection
      collection)

③AbstractSequentialList简介

介绍一下AbstractSequentialList。毕竟，LinkedList是AbstractSequentialList的子类。

1）AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些函数。这些接口都是随机访问List的，LinkedList是双向链表；既然它继承于AbstractSequentialList，就相当于已经实现了“get(int index)这些接口”。

2）我们若需要通过AbstractSequentialList自己实现一个列表，只需要扩展此类，并提供 listIterator() 和 size() 方法的实现即可。若要实现不可修改的列表，则需要实现列表迭代器的 hasNext、next、hasPrevious、previous 和 index 方法即可。 LinkedList是AbstractSequentialList的子类。

3）AbstractSequentialList实现了get(int index)、set(int indext, E element)、add(int index,E element)和remove（int index）这些函数。这些接口都是随机访问List的，LinkedList是双向链表，既然它继承了AbstractSequentialList，就相当于已经实现了这些接口。

4）若需要通过AbstractSequentialList自己实现一个列表，只需要扩展此类，并提供listIterator()和size()方法的实现即可。若要实现不可修改的列表，则需要实现列表迭代器的hasNext、next、hasPrevious、previous和index方法即可。

 

④LinkedList其他介绍

1）LinkedList包含两个重要的成员: header和size

2）Header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量:previous,next,element。Previous是该节点的上一个节点，next是该节点的下一个节点，next是该节点的下一个节点，element是该节点所包含的值。

3）先对LinkedList的整体实现进行大致说明：

    LinkedList实际上是通过双向链表去实现的。既然是双向链表，那么它的顺序访问会非常高效，而随机访问效率比较低。

    既然LinkedList是通过双向链表的，但是它也实现了List接口{

也就是说，它实现了get(int location)、remove(int location)等“根据索引值来获取、删除节点的函数”}。

4）LinkedList是如何实现List的这些接口的，如何将“双向链表和索引值联系起来的”？

    实际原理非常简单，它就是通过一个计数索引值来实现的。例如，当我们调用get(int location)时，首先会比较“location”和“双向链表长度的1/2”；若前者大，则从链表头开始往后查找，直到location位置；否则，从链表末尾开始先前查 找，直到location位置。

 

⑤LinkedList其他介绍

(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

(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) {}

 

测试这些遍历方式效率的代码如下

 

import java.util.List;import java.util.Iterator;import java.util.LinkedList;import java.util.NoSuchElementException;/* * @desc 测试LinkedList的几种遍历方式和效率 * * @author skywang */public class LinkedListThruTest {    public static void main(String[] args) {        // 通过Iterator遍历LinkedList        iteratorLinkedListThruIterator(getLinkedList()) ;                // 通过快速随机访问遍历LinkedList        iteratorLinkedListThruForeach(getLinkedList()) ;        // 通过for循环的变种来访问遍历LinkedList        iteratorThroughFor2(getLinkedList()) ;        // 通过PollFirst()遍历LinkedList        iteratorThroughPollFirst(getLinkedList()) ;        // 通过PollLast()遍历LinkedList        iteratorThroughPollLast(getLinkedList()) ;        // 通过removeFirst()遍历LinkedList        iteratorThroughRemoveFirst(getLinkedList()) ;        // 通过removeLast()遍历LinkedList        iteratorThroughRemoveLast(getLinkedList()) ;    }        private static LinkedList getLinkedList() {        LinkedList llist = new LinkedList();        for (int i=0; i<100000; i++)            llist.addLast(i);        return llist;    }    /**     * 通过快迭代器遍历LinkedList     */    private static void iteratorLinkedListThruIterator(LinkedList
     
       list) {        if (list == null)            return ;        // 记录开始时间        long start = System.currentTimeMillis();                for(Iterator iter = list.iterator(); iter.hasNext();)            iter.next();        // 记录结束时间        long end = System.currentTimeMillis();        long interval = end - start;        System.out.println("iteratorLinkedListThruIterator：" + interval+" ms");    }    /**     * 通过快速随机访问遍历LinkedList     */    private static void iteratorLinkedListThruForeach(LinkedList
      
        list) {        if (list == null)            return ;        // 记录开始时间        long start = System.currentTimeMillis();                int size = list.size();        for (int i=0; i
       
         list) {        if (list == null)            return ;        // 记录开始时间        long start = System.currentTimeMillis();                for (Integer integ:list)             ;        // 记录结束时间        long end = System.currentTimeMillis();        long interval = end - start;        System.out.println("iteratorThroughFor2：" + interval+" ms");    }    /**     * 通过pollFirst()来遍历LinkedList     */    private static void iteratorThroughPollFirst(LinkedList
        
          list) {        if (list == null)            return ;        // 记录开始时间        long start = System.currentTimeMillis();        while(list.pollFirst() != null)            ;        // 记录结束时间        long end = System.currentTimeMillis();        long interval = end - start;        System.out.println("iteratorThroughPollFirst：" + interval+" ms");    }    /**     * 通过pollLast()来遍历LinkedList     */    private static void iteratorThroughPollLast(LinkedList
         
           list) {        if (list == null)            return ;        // 记录开始时间        long start = System.currentTimeMillis();        while(list.pollLast() != null)            ;        // 记录结束时间        long end = System.currentTimeMillis();        long interval = end - start;        System.out.println("iteratorThroughPollLast：" + interval+" ms");    }    /**     * 通过removeFirst()来遍历LinkedList     */    private static void iteratorThroughRemoveFirst(LinkedList
          
            list) { if (list == null) return ; // 记录开始时间 long start = System.currentTimeMillis(); try { while(list.removeFirst() != null) ; } catch (NoSuchElementException e) { } // 记录结束时间 long end = System.currentTimeMillis(); long interval = end - start; System.out.println("iteratorThroughRemoveFirst：" + interval+" ms"); } /** * 通过removeLast()来遍历LinkedList */ private static void iteratorThroughRemoveLast(LinkedList
           
             list) { if (list == null) return ; // 记录开始时间 long start = System.currentTimeMillis(); try { while(list.removeLast() != null) ; } catch (NoSuchElementException e) { } // 记录结束时间 long end = System.currentTimeMillis(); long interval = end - start; System.out.println("iteratorThroughRemoveLast：" + interval+" ms"); }}
           
          
         
        
       
      
     

 执行结果

iteratorLinkedListThruIterator：8 ms

iteratorLinkedListThruForeach：3724 ms

iteratorThroughFor2：5 ms

iteratorThroughPollFirst：8 ms

iteratorThroughPollLast：6 ms

iteratorThroughRemoveFirst：2 ms

iteratorThroughRemoveLast：2 ms

由此可见，遍历LinkedList时，使用removeFist()或removeLast()效率最高。但用它们遍历时，会删除原始数据；若单纯只读取，而不删除，应该使用第3种遍历方式。

无论如何，千万不要通过随机访问去遍历LinkedList！

 

⑦LinkedList示例

import java.util.List;import java.util.Iterator;import java.util.LinkedList;import java.util.NoSuchElementException;/* * @desc LinkedList测试程序。 * * @author skywang * @email  kuiwu-wang@163.com */public class LinkedListTest {    public static void main(String[] args) {        // 测试LinkedList的API        testLinkedListAPIs() ;        // 将LinkedList当作 LIFO(后进先出)的堆栈        useLinkedListAsLIFO();        // 将LinkedList当作 FIFO(先进先出)的队列        useLinkedListAsFIFO();    }        /*     * 测试LinkedList中部分API     */    private static void testLinkedListAPIs() {        String val = null;        //LinkedList llist;        //llist.offer("10");        // 新建一个LinkedList        LinkedList llist = new LinkedList();        //---- 添加操作 ----        // 依次添加1,2,3        llist.add("1");        llist.add("2");        llist.add("3");        // 将“4”添加到第一个位置        llist.add(1, "4");                System.out.println("\nTest \"addFirst(), removeFirst(), getFirst()\"");        // (01) 将“10”添加到第一个位置。  失败的话，抛出异常！        llist.addFirst("10");        System.out.println("llist:"+llist);        // (02) 将第一个元素删除。        失败的话，抛出异常！        System.out.println("llist.removeFirst():"+llist.removeFirst());        System.out.println("llist:"+llist);        // (03) 获取第一个元素。          失败的话，抛出异常！        System.out.println("llist.getFirst():"+llist.getFirst());        System.out.println("\nTest \"offerFirst(), pollFirst(), peekFirst()\"");        // (01) 将“10”添加到第一个位置。  返回true。        llist.offerFirst("10");        System.out.println("llist:"+llist);        // (02) 将第一个元素删除。        失败的话，返回null。        System.out.println("llist.pollFirst():"+llist.pollFirst());        System.out.println("llist:"+llist);        // (03) 获取第一个元素。          失败的话，返回null。        System.out.println("llist.peekFirst():"+llist.peekFirst());            System.out.println("\nTest \"addLast(), removeLast(), getLast()\"");        // (01) 将“20”添加到最后一个位置。  失败的话，抛出异常！        llist.addLast("20");        System.out.println("llist:"+llist);        // (02) 将最后一个元素删除。        失败的话，抛出异常！        System.out.println("llist.removeLast():"+llist.removeLast());        System.out.println("llist:"+llist);        // (03) 获取最后一个元素。          失败的话，抛出异常！        System.out.println("llist.getLast():"+llist.getLast());        System.out.println("\nTest \"offerLast(), pollLast(), peekLast()\"");        // (01) 将“20”添加到第一个位置。  返回true。        llist.offerLast("20");        System.out.println("llist:"+llist);        // (02) 将第一个元素删除。        失败的话，返回null。        System.out.println("llist.pollLast():"+llist.pollLast());        System.out.println("llist:"+llist);        // (03) 获取第一个元素。          失败的话，返回null。        System.out.println("llist.peekLast():"+llist.peekLast());                 // 将第3个元素设置300。不建议在LinkedList中使用此操作，因为效率低！        llist.set(2, "300");        // 获取第3个元素。不建议在LinkedList中使用此操作，因为效率低！        System.out.println("\nget(3):"+llist.get(2));        // ---- toArray(T[] a) ----        // 将LinkedList转行为数组        String[] arr = (String[])llist.toArray(new String[0]);        for (String str:arr)             System.out.println("str:"+str);        // 输出大小        System.out.println("size:"+llist.size());        // 清空LinkedList        llist.clear();        // 判断LinkedList是否为空        System.out.println("isEmpty():"+llist.isEmpty()+"\n");    }    /**     * 将LinkedList当作 LIFO(后进先出)的堆栈     */    private static void useLinkedListAsLIFO() {        System.out.println("\nuseLinkedListAsLIFO");        // 新建一个LinkedList        LinkedList stack = new LinkedList();        // 将1,2,3,4添加到堆栈中        stack.push("1");        stack.push("2");        stack.push("3");        stack.push("4");        // 打印“栈”        System.out.println("stack:"+stack);        // 删除“栈顶元素”        System.out.println("stack.pop():"+stack.pop());                // 取出“栈顶元素”        System.out.println("stack.peek():"+stack.peek());        // 打印“栈”        System.out.println("stack:"+stack);    }    /**     * 将LinkedList当作 FIFO(先进先出)的队列     */    private static void useLinkedListAsFIFO() {        System.out.println("\nuseLinkedListAsFIFO");        // 新建一个LinkedList        LinkedList queue = new LinkedList();        // 将10,20,30,40添加到队列。每次都是插入到末尾        queue.add("10");        queue.add("20");        queue.add("30");        queue.add("40");        // 打印“队列”        System.out.println("queue:"+queue);        // 删除(队列的第一个元素)        System.out.println("queue.remove():"+queue.remove());            // 读取(队列的第一个元素)        System.out.println("queue.element():"+queue.element());        // 打印“队列”        System.out.println("queue:"+queue);    }}

 

 运行 结果

Test "addFirst(), removeFirst(), getFirst()"

llist:[10, 1, 4, 2, 3]

llist.removeFirst():10

llist:[1, 4, 2, 3]

llist.getFirst():1

Test "offerFirst(), pollFirst(), peekFirst()"

llist:[10, 1, 4, 2, 3]

llist.pollFirst():10

llist:[1, 4, 2, 3]

llist.peekFirst():1

Test "addLast(), removeLast(), getLast()"

llist:[1, 4, 2, 3, 20]

llist.removeLast():20

llist:[1, 4, 2, 3]

llist.getLast():3

Test "offerLast(), pollLast(), peekLast()"

llist:[1, 4, 2, 3, 20]

llist.pollLast():20

llist:[1, 4, 2, 3]

llist.peekLast():3

get(3):300

str:1

str:4

str:300

str:3

size:4

isEmpty():true

useLinkedListAsLIFO

stack:[4, 3, 2, 1]

stack.pop():4

stack.peek():3

stack:[3, 2, 1]

useLinkedListAsFIFO

queue:[10, 20, 30, 40]

queue.remove():10

queue.element():20

queue:[20, 30, 40]