Java LinkedList

Java LinkedList，ArrayList随机访问效率很高，但插入和删除性能比较低；LinkedList同样实现了List接口，它的特点与ArrayList几乎正好相反，本文我们就来详细介绍LinkedList。

除了实现了List接口外，LinkedList还实现了Deque和Queue接口，可以按照队列、栈和双端队列的方式进行操作。

用法

LinkedList的构造方法与ArrayList类似，有两个：一个是默认构造方法，另外一个可以接受一个已有的Collection，如下所示：

public LinkedList()
public LinkedList(Collection<? extends E> c)

比如，可以这么创建：

List<String> list = new LinkedList<>();
List<String> list2 = new LinkedList<>(
        Arrays.asList(new String[]{"a", "b", "c"}));

LinkedList与ArrayList一样，同样实现了List接口，而List接口扩展了Collection接口，Collection又扩展了Iterable接口，所有这些接口的方法都是可以使用的，本文不再赘述。LinkedList还实现了队列接口Queue，所谓队列就类似于日常生活中的各种排队，特点就是先进先出，在尾部添加元素，从头部删除元素，它的接口定义为：

public interface Queue<E> extends Collection<E> {
    boolean add(E e);
    boolean offer(E e);
    E remove();
    E poll();
    E element();
    E peek();
}

Queue扩展了Collection，它的主要操作有三个：

• 在尾部添加元素（add、offer）；
• 查看头部元素（element、peek），返回头部元素，但不改变队列；
• 删除头部元素（remove、poll），返回头部元素，并且从队列中删除。

每种操作都有两种形式，有什么区别呢？

区别在于，对于特殊情况的处理不同。特殊情况是指队列为空或者队列为满，为空容易理解，为满是指队列有长度大小限制，而且已经占满了。LinkedList的实现中，队列长度没有限制，但别的Queue的实现可能有。在队列为空时，element和remove会抛出异常NoSuchElementException，而peek和poll返回特殊值null；在队列为满时，add会抛出异常IllegalStateException，而offer只是返回false。

把LinkedList当作Queue使用也很简单，比如，可以这样：

public class coolcou {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("a");
        queue.offer("b");
        queue.offer("c");
        while(queue.peek() !=null){
            System.out.println(queue.poll());
        }
    }
}

输出结果：

我们在介绍函数调用原理的时候介绍过栈。栈也是一种常用的数据结构，与队列相反，它的特点是先进后出、后进先出，类似于一个储物箱，放的时候是一件件往上放，拿的时候则只能从上面开始拿。Java中没有单独的栈接口，栈相关方法包括在了表示双端队列的接口Deque中，主要有三个方法：

void push(E e);
E pop();
E peek();

解释如下。
1）push表示入栈，在头部添加元素，栈的空间可能是有限的，如果栈满了，push会抛出异常IllegalStateException。
2）pop表示出栈，返回头部元素，并且从栈中删除，如果栈为空，会抛出异常NoSuch-ElementException。
3）peek查看栈头部元素，不修改栈，如果栈为空，返回null。

把LinkedList当作栈使用也很简单，比如，可以这样：

public class coolcou {
    public static void main(String[] args) {
        Deque<String> stack = new LinkedList<>();
        stack.push("a");
        stack.push("b");
        stack.push("c");
        while(stack.peek() != null){
            System.out.println(stack.pop());
        }
    }
}

输出结果：

Java中有一个类Stack，单词意思是栈，它也实现了栈的一些方法，如push/pop/peek等，但它没有实现Deque接口，它是Vector的子类，它增加的这些方法也通过synchronized实现了线程安全，具体就不介绍了。不需要线程安全的情况下，推荐使用LinkedList。

栈和队列都是在两端进行操作，栈只操作头部，队列两端都操作，但尾部只添加、头部只查看和删除。有一个更为通用的操作两端的接口Deque。Deque扩展了Queue，包括了栈的操作方法，此外，它还有如下更为明确的操作两端的方法：

void addFirst(E e);
void addLast(E e);
E getFirst();
E getLast();
boolean offerFirst(E e);
boolean offerLast(E e);
E peekFirst();
E peekLast();
E pollFirst();
E pollLast();
E removeFirst();
E removeLast();

xxxFirst操作头部，xxxLast操作尾部。与队列类似，每种操作有两种形式，区别也是在队列为空或满时处理不同。为空时，getxxx/removexxx会抛出异常，而peekxxx/pollxxx会返回null。队列满时，addxxx会抛出异常，offerxxx只是返回false。

栈和队列只是双端队列的特殊情况，它们的方法都可以使用双端队列的方法替代，不过，使用不同的名称和方法，概念上更为清晰。

Deque接口还有一个迭代器方法，可以从后往前遍历：

Iterator<E> descendingIterator();

比如，看如下代码：

Deque<String> deque = new LinkedList<>(
        Arrays.asList(new String[]{"a", "b", "c"}));
Iterator<String> it = deque.descendingIterator();
while(it.hasNext()){
    System.out.print(it.next()+" ");
}

输出结果：

简单总结下：LinkedList的用法是比较简单的，与ArrayList用法类似，支持List接口，只是，LinkedList增加了一个接口Deque，可以把它看作队列、栈、双端队列，方便地在两端进行操作。如果只是用作List，那应该用ArrayList还是LinkedList呢？我们需要了解LinkedList的实现原理。

LinkedList特点

用法上，LinkedList是一个List，但也实现了Deque接口，可以作为队列、栈和双端队列使用。实现原理上，LinkedList内部是一个双向链表，并维护了长度、头节点和尾节点，这决定了它有如下特点。

1）按需分配空间，不需要预先分配很多空间。
2）不可以随机访问，按照索引位置访问效率比较低，必须从头或尾顺着链接找，效率为O(N/2)。
3）不管列表是否已排序，只要是按照内容查找元素，效率都比较低，必须逐个比较，效率为O(N)。
4）在两端添加、删除元素的效率很高，为O(1)。
5）在中间插入、删除元素，要先定位，效率比较低，为O(N)，但修改本身的效率很高，效率为O(1)。
理解了LinkedList和ArrayList的特点，就能比较容易地进行选择了，如果列表长度未知，添加、删除操作比较多，尤其经常从两端进行操作，而按照索引位置访问相对比较少，则LinkedList是比较理想的选择。

酷客教程相关文章：

• Java ArrayList迭代
• Java ArrayList
• Java 泛型与数组
• Java 定义泛型类、方法和接口