1.linkedList的实现

    linkedlist的实现是基于数据结构：双向链表。模型图如

        对于linkedList没有像arrayList一样有扩容的概念。也不需要移动数据。所以对于新增和删除操作add和remove，LinkedList比较占优势。

2.双向链表的实现

参考：简单双向链表的增删改查

3.linkedList的继承关系

        从继承图中可以看出LinkList实现了List接口，实现了list接口中的所有方法，同时页实现了Queue接口，所以linkedList同时具备了对队列和栈操作的特点。

4.Linkedlist实现的方法

5.重要属性

LinkedList执行栈操作或队列操作就是对first节点和last节点的操作

6.Node节点

LinkedList实现的方法就不再一一叙述。

7.LinkedList遍历

1.通过迭代器遍历。即通过Iterator去遍历

for(Iterator iter = list.iterator(); iter.hasNext();)
iter.next();

2.通过快速随机访问遍历LinkedList

int size = list.size();
for (int i=0; i<size; i++) {
    list.get(i);       
}

3.通过另外一种for循环来遍历LinkedList

for (Integer integ:list)
;

4. 通过pollFirst()来遍历LinkedList

while(list.pollFirst() != null)
;

5.通过pollLast()来遍历LinkedList

while(list.pollLast() != null)
;

6. 通过removeFirst()来遍历LinkedList

try {
    while(list.removeFirst() != null)
        ;
} catch (NoSuchElementException e) {
}

7.通过removeLast()来遍历LinkedList

try {
    while(list.removeLast() != null)
        ;
} catch (NoSuchElementException e) {
}

8.测试：

package com.dzqc.yx;
 
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
 
/*
 * @desc 测试LinkedList的几种遍历方式和效率
 *
 * @author skywang
 */
public class BkApplication {
    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<Integer> 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<Integer> list) {
        if (list == null)
            return ;
 
        // 记录开始时间
        long start = System.currentTimeMillis();
 
        int size = list.size();
        for (int i=0; i<size; i++) {
            list.get(i);
        }
        // 记录结束时间
        long end = System.currentTimeMillis();
        long interval = end - start;
        System.out.println("iteratorLinkedListThruForeach：" + interval+" ms");
    }
 
    /**
     * 通过另外一种for循环来遍历LinkedList
     */
    private static void iteratorThroughFor2(LinkedList<Integer> 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<Integer> 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<Integer> 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<Integer> 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<Integer> 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");
    }
 
}

运行结果：

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

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