你的位置:首页 > Java教程

[Java教程]【JAVA集合】LinkedList


以下内容基于jdk1.7.0_79源码;

什么是LinkedList

List接口的链表实现,并提供了一些队列,栈,双端队列操作的方法;

LinkedList补充说明

与ArrayList对比,LinkedList插入和删除操作更加高效,随机访问速度慢;

可以作为栈、队列、双端队列数据结构使用;

非同步,线程不安全;

与ArrayList、Vector一样,LinkedList的内部迭代器存在“快速失败行为”;

支持null元素、有顺序、元素可以重复;

LinkedList继承的类以及实现的接口

以上接口和类中,关于Iterable接口、Collection接口、List接口、 Cloneable、 java.io.Serializable接口、AbstractCollection类、AbstractList类的相关说明,在介绍ArrayList的时候,已经有了个大概说明,这里将主要了解下Queue接口、Deque接口、AbstractSequentialList类以及LinkedList类;

Queue接口

队列接口,定义了一些队列的基本操作,

注意使用时优先选择以下蓝色字体方法(offer、poll、peek),队列通常不允许null元素,因为我们通常调用poll方法是否返回null来判断队列是否为空,但是LinkedList是允许null元素的,所以,在使用LinkedList最为队列的实现时,不应该将null元素插入队列;

boolean add(E e);

将对象e插入队列尾部,成功返回true,失败(没有空间)抛出异常IllegalStateException

boolean offer(E e);

将对象e插入队列尾部,成功返回true,失败(没有空间)返回false;

E remove();

获取并移除队列头部元素,如果队列为空,抛出NoSuchElementException异常;

E poll();

获取并移除队列头部元素,如果队列为空,返回null;

E element();

获取但不移除队列头部元素,如果队列为空,抛出NoSuchElementException异常;

E peek();

获取但不移除队列头部元素,如果队列为空,返回null;

举个简单的例子,基于LinkedList实现的队列,代码如下:

package com.pichen.basis.col;import java.util.LinkedList;import java.util.Queue;public class LinkListTest {  public static void main(String[] args) {    Queue<Integer> linkedListQueue = new LinkedList<Integer>();    //入队    linkedListQueue.offer(3);    linkedListQueue.offer(4);    linkedListQueue.offer(2);    linkedListQueue.offer(1);    //出队    Integer tmp;    while((tmp = linkedListQueue.poll()) != null){      System.out.println(tmp);    }        System.out.println(linkedListQueue.peek());  }}

Deque接口

双端队列接口,继承队列接口,支持在队列两端进行入队和出队操作;

除了Collection接口Queue接口中定义的方法外,Deque还包括以下方法

void addFirst(E e);

将对象e插入到双端队列头部,容间不足时,抛出IllegalStateException异常;

void addLast(E e);

将对象e插入到双端队列尾部,容间不足时,抛出IllegalStateException异常;

boolean offerFirst(E e);

将对象e插入到双端队列头部

boolean offerLast(E e);

将对象e插入到双端队列尾部;

E removeFirst();

获取并移除队列第一个元素,队列为空,抛出NoSuchElementException异常;

E removeLast();

获取并移除队列最后一个元素,队列为空,抛出NoSuchElementException异常;

E pollFirst();

获取并移除队列第一个元素,队列为空,返回null;

E pollLast();

获取并移除队列最后一个元素,队列为空,返回null;

E getFirst();

获取队列第一个元素,但不移除,队列为空,抛出NoSuchElementException异常;

E getLast();

获取队列最后一个元素,但不移除,队列为空,抛出NoSuchElementException异常;

E peekFirst();

获取队列第一个元素,队列为空,返回null;

E peekLast();

获取队列最后一个元素,队列为空,返回null;

boolean removeFirstOccurrence(Object o);

移除第一个满足 (o==null ? e==null : o.equals(e)) 的元素

boolean removeLastOccurrence(Object o);

移除最后一个满足 (o==null ? e==null : o.equals(e)) 的元素

void push(E e);

将对象e插入到双端队列头部;

E pop();

移除并返回双端队列的第一个元素

Iterator<E> descendingIterator();

双端队列尾部到头部的一个迭代器;

AbstractSequentialList类

 一个抽象类,基于迭代器实现数据的随机访问,以下方法的含义, 之前也说过,简单地说,就是数据的随机存取(利用了一个索引index);

public E get(int index)

public E set(int index, E element)

public void add(int index, E element)

public E remove(int index)

public boolean addAll(int index, Collection<? extends E> c)

LinkedList类

LinkedList的具体实现,

LinkedList中有两个关键成员属性,队头结点和队尾结点:

transient Node<E> first; //队头节点transient Node<E> last; //队尾节点

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;    }  }

至于LinkedList提供的每个方法的含义,在前面队列、双端队列、集合等接口中都有说明了,这里简单的举一两个方法的具体实现,对照源码了解下,其实就是链表的操作:

poll方法,出队操作

  public E poll() {    final Node<E> f = first;    return (f == null) ? null : unlinkFirst(f);  }

  /**   * Unlinks non-null first node f.   */  private E unlinkFirst(Node<E> f) {    // assert f == first && f != null;    final E element = f.item;    final Node<E> next = f.next;    f.item = null;    f.next = null; // help GC    first = next;    if (next == null)      last = null;    else      next.prev = null;    size--;    modCount++;    return element;  }

获取并移除双端队列头部元素,如上代码,主要实现在unlinkFirst方法内,首先直接获取被删节点,临时存储其具体引用的对象element和下个引用next,然后将被删节点对象引用和下个节点引用置null给gc回收,改变双端队列队头结点为被删节点的下个引用next,如果next为空,将双端队列的队尾结点last置null,否则将next节点的前引用置null;队列长度减减,操作次数加加(快速失败机制),返回被删节点引用的具体对象;

public E get(int index)方法,随机访问方法

  public E get(int index) {    checkElementIndex(index);    return node(index).item;  }

  /**   * Returns the (non-null) Node at the specified element index.   */  Node<E> node(int index) {    // assert isElementIndex(index);    if (index < (size >> 1)) {      Node<E> x = first;      for (int i = 0; i < index; i++)        x = x.next;      return x;    } else {      Node<E> x = last;      for (int i = size - 1; i > index; i--)        x = x.prev;      return x;    }  }

LinkedList随机访问性能较差,首先是判断索引index合法性,然后调用node(int index)方法,在node方法中,做了一点优化,先判断要访问节点的索引是在队列的前半部分还是后半部分,如果在前半部分则从队头开始遍历,否则从队尾开始遍历,如上代码所示。

注意事项

适用场合很重要,注意和ArrayList区分开来,根据集合的各自特点以及具体场景,选择合适的List实现;

这里举个简单例子,分别使用ArrayList和LinkedList,测试下两个集合随机访问的性能,可以发现使用LinkedList随机访问的效率较ArrayList差很多;

package com.pichen.basis.col;import java.util.ArrayList;import java.util.Arrays;import java.util.Iterator;import java.util.LinkedList;import java.util.List;import java.util.ListIterator;import java.util.Stack;import java.util.Vector;public class Test {  public static void main(String[] args) {    //初始化linkedList和arrayList数据    LinkedList<Integer> linkedList = new LinkedList<Integer>();    for(int i = 0; i < 10000; i++){      linkedList.offerLast(i);    }    List<Integer> arrayList = new ArrayList<Integer>();    for(int i = 0; i < 10000; i++){      arrayList.add(i);    }        long s, e;        s = System.currentTimeMillis();    for(int i = 0; i < 10000; i++){      linkedList.get(i);    }    e = System.currentTimeMillis();    System.out.println("linkedList:" + (e - s) + "ms");        s = System.currentTimeMillis();    for(int i = 0; i < 10000; i++){      arrayList.get(i);    }    e = System.currentTimeMillis();    System.out.println("arrayList:" + (e - s) + "ms");      }}

结果打印:

linkedList:56msarrayList:1ms