Java LinkedList实现详解

一、什么是LinkedList

LinkedList是Java中的一个双向链表类。它继承了AbstractSequentialList并且实现了List、Deque、Cloneable和Serializable接口。

相对于Arraylist来说，LinkedList的插入和删除操作更加高效。正因为它是一个链表，所以它的内存布局不是连续的，这就为它提供了灵活性和可调整性。

java LinkedList类有以下构造器:

    public LinkedList ()
    public LinkedList (Collection  c)

二、LinkedList的常用API

1、boolean add(E e)

在LinkedList的结尾添加元素，返回值为true。

    LinkedList<String> list = new LinkedList<>();
    list.add("Java");
    list.add("Go");
    list.add("Python");

2、void add(int index, E element)

将元素插入LinkedList指定的位置。

    LinkedList<String> list = new LinkedList<>();
    list.add("Java");
    list.add("Go");
    list.add("Python");
    list.add(1,"C++");

3、boolean addAll(Collection c)

将传入的集合中的所有元素添加到LinkedList的结尾。如果添加成功，则返回true。

    List<String> list1 = new LinkedList<>();
    list1.add("Java");
    list1.add("Go");
    list1.add("Python");

    List<String> list2 = new LinkedList<>();
    list2.add("C++");
    list2.add(".Net");
    list2.add("JavaScript");

    list1.addAll(list2);

4、void addFirst(E e)

将指定元素添加到LinkedList的开头。

    LinkedList<String> list = new LinkedList<>();
    list.add("Java");
    list.add("Go");
    list.add("Python");
    list.addFirst("C++"); //在list的开头添加元素"C++"

5、E remove()

移除且返回LinkedList的头元素。

    LinkedList<String> list = new LinkedList<>();
    list.add("Java");
    list.add("Go");
    list.add("Python");
    list.remove(); //Java被删除

6、E remove(int index)

按照指定位置移除元素。

    LinkedList<String> list = new LinkedList<>();
    list.add("Java");
    list.add("Go");
    list.add("Python");
    list.remove(1); //列表中的第二个元素被删除

7、boolean remove(Object o)

在LinkedList中移除指定的元素。

    LinkedList<String> list = new LinkedList<>();
    list.add("Java");
    list.add("Go");
    list.add("Python");
    list.remove("Go"); //Go被删除

8、void clear()

移除LinkedList中的所有元素。这个方法很快，它只需要O(1)时间。

    LinkedList<String> list = new LinkedList<>();
    list.add("Java");
    list.add("Go");
    list.add("Python");
    list.clear(); //清空所有元素

三、LinkedList与Stack

1、什么是Stack

堆栈（英语：stack）又称栈或堆叠，是计算机科学中的一种抽象数据类型。只能在某一端（称为栈顶，top）进行加入数据（push）和读取数据（pop）的运算。

这里，我们将LinkedList和Stack进行比较，探究它们之间的联系。

首先，我们先来看一下用ArrayList实现Stack的方法。

    class Stack
    {
        private ArrayList<Object> data = new ArrayList<Object>();

        public void push(Object o)
        {
            data.add(o);
        }

        public Object pop() throws Exception
        {
            if(data.size() <= 0)
            {
                throw new Exception("Stack is empty");
            }
            return data.remove(data.size()-1);
        }

        public boolean isEmpty()
        {
            return data.size() == 0;
        }

        public Object peek() throws Exception
        {
            if(data.size() <=0)
            {
                throw new Exception("Stack is empty");
            }
            return data.get(data.size()-1);
        }
    }

接下来看用LinkedList实现Stack的方法。

    class Stack
    {
        private LinkedList<Object> linkdata = new LinkedList<Object>();

        public void push(Object o)
        {
            linkdata.addFirst(o);
        }

        public Object pop() throws Exception
        {
            if(linkdata.isEmpty())
            {
                throw new Exception("Stack is empty");
            }
            return linkdata.removoFirst();
        }

        public boolean isEmpty()
        {
            return linkdata.size() == 0;
        }

        public Object peek() throws Exception
        {
            if(linkdata.isEmpty())
            {
                throw new Exception("Stack is empty");
            }
            return linkdata.getFirst();
        }
    }

显然的，用LinkedList实现Stack是一项很简单的任务，只需要将addFirst方法替换成push方法即可。LinkedList也实现了Deque，removeFirst方法也等同于pop方法。

四、LinkedList与Queue

1、什么是Queue

队列（英语：Queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出（FIFO, First In First Out）的数据结构，队列中出现的元素称为队元素，新元素的插入称为入队，而队列允许删除操作的一端则称为队头。

下面看一下如何用LinkedList实现一个Queue.

    class Queue
    {
        private LinkedList<Object> queue = new LinkedList<>();

        //入队
        public void enqueue(Object o)
        {
            queue.addLast(o);
        }
        //出队
        public Object dequeue() throws NoSuchMethodException
        {
            if(queue.isEmpty())
            {
                throw new NoSuchMethodException("Queue is Empty");
            }
            return queue.removeFirst();
        }
        //是否为空
        public boolean isEmpty()
        {
            return queue.isEmpty();
        }
        //打印队列
        public void printQueue()
        {
            System.out.print("[");
            for(int i=0;i < queue.size();i++)
            {
                System.out.print(queue.get(i)+" ");
            }
            System.out.print("]\n");
        }
    }

五、LinkedList的优缺点

1、优点

①随机访问ArrayList比LinkedList快，因为ArrayList可以直接访问内存地址；而LinkedList需要遍历元素。但是ArrayList在插入和删除元素时的效率较低。

②LinkedList内部是双向链表，所以它可以分别访问首元素和尾元素；

③LinkedList可以充当队列和堆栈；不需要更改底层的实现即可提供这两种数据结构的行为。

2、缺点

虽然LinkedList提供了一种可调整大小的数组的替代方案，但是，在性能和时间方面，它会比ArrayList更慢。也就是说，它在访问集合中的任何给定元素方面效率较低。

所以，在迭代过程中，维护开销可能会很大，因为在迭代一半之前，我们不知道它的方向。

六、总结

LinkedList是Java中的一个双向链表类。它比Arraylist在插入和删除操作更加高效。它可以访问首尾元素，可以充当队列和堆栈，添加与删除操作快。但是，在访问集合中的任何给定元素方面效率较低。所以要根据具体应用场景进行选择。