Java集合框架（四）— LinkedList

image.png

LinkedList的定义

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable

LinkedList是AbstractSequentialList的子类。

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

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

LinkedList的API

// Collection中定义的API
boolean             add(E object)
boolean             addAll(Collection<? extends E> collection)
void                clear()
boolean             contains(Object object)
boolean             containsAll(Collection<?> collection)
boolean             equals(Object object)
int                 hashCode()
boolean             isEmpty()
Iterator<E>         iterator()
boolean             remove(Object object)
boolean             removeAll(Collection<?> collection)
boolean             retainAll(Collection<?> collection)
int                 size()
<T> T[]             toArray(T[] array)
Object[]            toArray()

// List新增的API
void                add(int location, E object)
boolean             addAll(int location, Collection<? extends E> collection)
E                   get(int location)
int                 indexOf(Object object)
int                 lastIndexOf(Object object)
ListIterator<E>     listIterator(int location)
ListIterator<E>     listIterator()
E                   remove(int location)
E                   set(int location, E object)
List<E>             subList(int start, int end)

// Deque的API
void          addFirst(E object)
void          addLast(E object)
Object        clone()
Iterator<E>   descendingIterator()
E             element()
E             getFirst()
E             getLast()
boolean       offer(E o)
boolean       offerFirst(E e)
boolean       offerLast(E e)
E             peek()
E             peekFirst()
E             peekLast()
E             poll()
E             pollFirst()
E             pollLast()
E             pop()
void          push(E e)
E             remove()
boolean       remove(Object object)
E             removeFirst()
boolean       removeFirstOccurrence(Object o)
E             removeLast()
boolean       removeLastOccurrence(Object o)

LinkedList的本质是双向链表。
(01) LinkedList继承于AbstractSequentialList，并且实现了Deque接口。
(02) LinkedList包含两个重要的成员：header 和 size。
　　header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。
　　size是双向链表中节点的个数。

LinkedList构造函数

public LinkedList() {
    }

public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

LinkedList四种遍历方式

package LinkedListDemo;

import java.io.ObjectOutputStream;
import java.util.Iterator;
import java.util.LinkedList;

/**
 * @ClassName: LinkedListIterator
 * @Author Sandy
 * @Date: 2018/12/3
 * @Version v1.0.0
 * @Description: //TODO
 */

public class LinkedListIterator {

    public static void iteratorLinkedListByIterator(LinkedList linkedList){
        long startTime;
        long endTime;

        Iterator iterator = linkedList.iterator();
        startTime = System.currentTimeMillis();
        while(iterator.hasNext()){
            iterator.next();
        }
        endTime = System.currentTimeMillis();
        long interval = endTime - startTime;
        System.out.println("通过迭代器遍历LinkedList效率为：" + interval);
    }

    public static void iteratorLinkedListByRandomAccess(LinkedList linkedList){

        long startTime;
        long endTime;

        Object value;

        startTime = System.currentTimeMillis();
        for(int i = 0; i < linkedList.size(); i++){
            value = linkedList.get(i);
        }
        endTime = System.currentTimeMillis();

        long interval = endTime - startTime;
        System.out.println("通过随机访问遍历LinkedList效率为：" + interval);
    }

    public static  void iteratorLinkedListByFor(LinkedList linkedList){

        long startTime;
        long endTime;

        startTime = System.currentTimeMillis();
        for(Object object:linkedList)
            ;
        endTime = System.currentTimeMillis();

        long interval = endTime - startTime;
        System.out.println("通过For循环遍历LinkedList效率为：" + interval);

    }

    public  static  void iteratorLinkedListByPop(LinkedList linkedList){

        long startTime;
        long endTime;

        startTime = System.currentTimeMillis();
        while(linkedList.pollFirst() != null)
            ;
        endTime = System.currentTimeMillis();

        long interval = endTime - startTime;
        System.out.println("通过Poll遍历LinkedList效率为：" + interval);
    }

    public static void main(String[] args) {

        LinkedList linkedList = new LinkedList();
        for(int i = 0; i < 10000; i++){
            linkedList.add(i);
        }

        //效率对比
        iteratorLinkedListByIterator(linkedList);
        iteratorLinkedListByRandomAccess(linkedList);
        iteratorLinkedListByFor(linkedList);
        iteratorLinkedListByPop(linkedList);
    }

}

输出

通过迭代器遍历LinkedList效率为：3
通过随机访问遍历LinkedList效率为：95
通过For循环遍历LinkedList效率为：1
通过Poll遍历LinkedList效率为：2