一、簡介

• LinkedList 是一個繼承于AbstractSequentialList的雙向鏈表。它也可以被當(dāng)作堆棧、隊列或雙端隊列進(jìn)行操作。
• LinkedList 實(shí)現(xiàn) List 接口，能進(jìn)行隊列操作。
• LinkedList 實(shí)現(xiàn) Deque 接口，即能將LinkedList當(dāng)作雙端隊列使用。
• ArrayList底層是由數(shù)組支持，而LinkedList 是由雙向鏈表實(shí)現(xiàn)的，其中的每個對象包含數(shù)據(jù)的同時還包含指向鏈表中前一個與后一個元素的引用。

二、構(gòu)造函數(shù)

1. LinkedList(): 生成空的鏈表
2. LinkedList(Collection C): 根據(jù)一個集合創(chuàng)建一個鏈表。

三、常用方法

1、增加：

• boolean add(E e)：在鏈表后添加一個元素；
• void add(int index, E element)：在指定位置插入一個元素；
• void addFirst(E e)：在鏈表頭部插入一個元素；
• void addLast(E e)：在鏈表尾部添加一個元素；
• void push(E e)：與addFirst方法一致；
• boolean offer(E e)：在鏈表尾部插入一個元素 ；
• boolean offerFirst(E e)：在頭部添加；
• boolean offerLast(E e)：在尾部添加。

2、刪除：

• Object remove() ：移除鏈表中第一個元素;
• boolean remove(E e)：移除指定元素；
• Object removeFirst(E e)：刪除頭，獲取元素并刪除；
• Object removeLast(E e)：刪除尾；
• Object poll()：查詢并移除第一個元素。
• Object pollFirst()：刪除頭；
• Object pollLast()：刪除尾；
• Object pop()：和removeFirst方法一致，刪除頭；

3、查：

• Object get(int index)：按照下標(biāo)獲取元素；
• Object getFirst()：獲取第一個元素；
• Object getLast()：獲取最后一個元素；
• Object peek()：獲取第一個元素，但是不移除；
• Object peekFirst()：獲取第一個元素，但是不移除；
• Object peekLast()：獲取最后一個元素，但是不移除；

一個例子：

public class LinkedListDemo {
    public static void main(String[] srgs) {
        LinkedList linkedList = new LinkedList();

        linkedList.add(1);        
        linkedList.add(1, 2);      
        linkedList.addFirst(0);   
        linkedList.addLast(3);   
        linkedList.push(-1); 
        linkedList.offer(4);   
        linkedList.offerFirst(-2); 
        linkedList.offerLast(5);  

        System.out.println("LinkedList: " + linkedList); 
        linkedList.remove(); 
        System.out.println("removeFirst(): " + linkedList.removeFirst()); 
        System.out.println("removeLast(): " + linkedList.removeLast());  
        System.out.println("After remove:" + linkedList); 
        linkedList.poll();                                       
        linkedList.pollFirst();                                           
        linkedList.pollLast();                                            
        System.out.println("After poll():" + linkedList);     
        linkedList.pop();                                                
        System.out.println("After pop():" + linkedList); 
        
        linkedList.add(4);
        linkedList.add(5);
        System.out.println("get():" + linkedList.get(1));
        System.out.println("getFirst(): " + linkedList.getFirst());    
        System.out.println("getLast(): " + linkedList.getLast());        
        System.out.println("peek(): " + linkedList.peek());               
        System.out.println("peekFirst(): " + linkedList.peekFirst());  
        System.out.println("peekLast(): " + linkedList.peekLast()); 
    }
}      

輸出結(jié)果：

LinkedList: [-2, -1, 0, 1, 2, 3, 4, 5]
removeFirst(): -1
removeLast(): 5
After remove:[0, 1, 2, 3, 4]
After poll():[2, 3]
After pop():[3]
get():4
getFirst(): 3
getLast(): 5
peek(): 3
peekFirst(): 3
peekLast(): 5

4、其他

import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] srgs) {
        LinkedList linkedList = new LinkedList();
        linkedList.add(3);
        linkedList.add(4);
        linkedList.add(5);

        // 判斷此列表包含指定元素，如果是，則返回true
        System.out.println("contains(1) is :" + linkedList.contains(1)); 
        // 獲取但不移除此列表的頭 
        System.out.println("element(): " + linkedList.element());  
        // 返回此列表的元素個數(shù)        
        System.out.println("size is : " + linkedList.size());
        // 將此列表中指定位置的元素替換為指定的元素             
        linkedList.set(1, 3);                                             
        System.out.println("After set(1, 3):" + linkedList);
        // 返回此列表中首次出現(xiàn)的指定元素的索引
        System.out.println("indexOf(3): " + linkedList.indexOf(3));        
        // 返回此列表中最后出現(xiàn)的指定元素的索引
        System.out.println("lastIndexOf(3): " + linkedList.lastIndexOf(3));
        System.out.println("subList(2,3): " + linkedList.subList(2,3));
    }
}

輸出結(jié)果：

contains(1) is :false
element(): 3
size is : 3
After set(1, 3):[3, 3, 5]
indexOf(3): 0
lastIndexOf(3): 1
subList(2,3): [5]

四、遍歷

1、迭代器遍歷

Iterator<Integer> iterator = linkedList.iterator();
while(iterator.hasNext()){
    iterator.next();

2、for循環(huán)get()遍歷

for(int i = 0; i < linkedList.size(); i++){
    linkedList.get(i);
}

3、Foreach循環(huán)遍歷

for(Integer i : linkedList) {
    // some code
};

4、通過pollFirst()或pollLast()遍歷

while(linkedList.size() != 0){
    linkedList.pollFirst();
}

5、通過removeFirst()或removeLast()遍歷

while(linkedList.size() != 0){
    linkedList.removeFirst();
}

注意：

• 遍歷LinkedList時，使用removeFirst()或removeLast()效率最高，而for循環(huán)get()效率最低，應(yīng)避免使用這種方式進(jìn)行。
• 使用pollFirst()或pollLast()或removeFirst()或removeLast()遍歷時，會刪除原始數(shù)據(jù)，若只單純的讀取，應(yīng)當(dāng)選用第一種或第三種方式。

import java.util.Iterator;
import java.util.LinkedList;

public class LinkedListLoop {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        for(int i = 0; i < 3; i++){
            linkedList.add(i);
        }
        // 迭代器遍歷
        Iterator<Integer> iterator = linkedList.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());;
        }

        // 順序遍歷(隨機(jī)遍歷)
        for(int i = 0; i < linkedList.size(); i++){
            System.out.println(linkedList.get(i));
        }

        // 另一種for循環(huán)遍歷
        for(Integer i : linkedList) {
            System.out.println(i);
        };

        //  通過pollFirst()或pollLast()來遍歷LinkedList
        LinkedList<Integer> temp1 = new LinkedList<>();
        temp1.addAll(linkedList);
        while(temp1.size() != 0){
            System.out.println(temp1.pollFirst());
        }

        // 通過removeFirst()或removeLast()來遍歷LinkedList
        LinkedList<Integer> temp2 = new LinkedList<>();
        temp2.addAll(linkedList);
        while(temp2.size() != 0){
            System.out.println(temp2.removeFirst());
        }
    }
}