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在插入和刪除操作更加高效。它可以訪問首尾元素，可以充當隊列和堆棧，添加與刪除操作快。但是，在訪問集合中的任何給定元素方面效率較低。所以要根據具體應用場景進行選擇。