本篇內容包括：LinkedList 的概述、LinkedList 的結構既雙向鏈表實現與LinkedList-Node 結構、LinkedList 的使用（構造方法&常用方法）、關于 Queue 隊列的介紹、關于 ArrayList 和 LinkedList 的區別以及算法：翻轉鏈表！
一、LinkedList 概述
LinkedList 是用鏈表作為數據存儲結構的 List 集合，鏈表數據結構的特點是每個元素分配的空間不必連續，因此鏈表很適合數據的動態插入和刪除，但是其隨機訪問和遍歷速度比較慢。另外，LinkedList還提供了 List 接口中沒有定義的方法，專門用于操作表頭和表尾元素，可以當作堆棧、隊列和雙向隊列使用。
LinkedList 是以鏈表實現的，插入、刪除時只需要改變前后兩個節點指針指向即可，實現了真正的動態，不需要處理固定容量的問題，但是喪失了隨機訪問的能力 （索引訪問）。
LinkedList 是一個雙向鏈表實現，插入、刪除時只需要改變前后兩個節點指針指向即可，實現了真正的動態，不需要處理固定容量的問題。LinkedList 在當數據量很大或者操作很頻繁的情況下，添加和刪除元素時具有比 ArrayList 更好的性能。但在元素的查詢和修改方面要弱于ArrayList。
LinkedList 與 ArrayList 一樣 LinKedList 也不是線程安全的。
二、LinkedList 的結構
1、雙向鏈表實現
LinKedList 的數據存儲是基于雙向鏈表實現。
LinkedList 類每個結點用內部類 Node 表示，LinkedList 通過 first 和 last 引用分別指向鏈表的第一個和最后一個元素，當鏈表為空時，first 和 last 都為 NULL 值。
關于 LinKedList 操作數據時：
- 插入數據（很快）：先是在雙向鏈表中找到要插入節點的位置 index，找到之后，再插入一個新節點。 雙向鏈表查找 index 位置的節點時，有一個加速動作：若 index < 雙向鏈表長度的 1/2，則從前向后查找，否則，從后向前查找；
- 刪除數據（很快）：先是在雙向鏈表中找到要插入節點的位置 index，找到之后，進行如下操作：
node.previous.next = node.next; node.next.previous = node.previous; node = null，查找節點過程和插入一樣； - 獲取數據（很慢）：每次獲取數據都需要從 Head 節點從頭開始查找；
- 遍歷數據（很慢）：同獲取數據一樣，每次遍歷數據都需要從頭開始。
2、LinkedList-Node 結構
LinkedList 類內部的 Node 結點代碼如下：
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;}}
Node 節點一共有三個屬性：item 代表節點值，prev 代表節點的前一個節點，next 代表節點的后一個節點。每個結點都有一個前驅和后繼結點，并且在 LinkedList 中也定義了兩個變量分別指向鏈表中的第一個和最后一個結點。
三、LinkedList 的使用
1、構造方法
| 方法名 | 方法說明 |
|---|---|
public LinkedList() | 此構造函數用于構造一個空列表。 |
public LinkedList(Collection<? extends E> c) | 此構造函數將按照集合的迭代器返回的順序構造一個包含指定集合元素的列表 |
2、常用方法_作為隊列（Linked繼承了Queue）
| 方法名 | 方法說明 |
|---|---|
boolean add(E e) | 此方法將指定的元素追加到此列表/隊列的末尾 |
E remove() | 此方法檢索并刪除此列表的頭部（第一個元素），如果此列表為空，則報錯 |
E removeFirst() | 此方法刪除并返回此列表中的第一個元素，如果此列表為空，則報錯 |
E removeLast() | 此方法檢索并刪除此列表的最后一個元素，如果此列表為空，則報錯 |
E poll() | 此方法檢索并刪除此列表的頭部（第一個元素） |
E pollFirst() | 此方法檢索并刪除此列表的第一個元素，如果此列表為空，則返回null |
E pollLast() | 此方法檢索并刪除此列表的最后一個元素，如果此列表為空，則返回null |
E element() | 此方法檢索但不刪除此列表的頭部（第一個元素） |
3、常用方法_作為棧（FILO 先進后出的棧）
| 方法名 | 方法說明 |
|---|---|
void push(E e) | 此方法將元素推送到此列表所表示的堆棧上 |
E pop() | 此方法從此列表表示的堆棧中彈出一個元素 |
E peek() | 此方法檢索但不刪除此列表的頭部（第一個元素） |
E peekFirst() | 此方法檢索但不刪除此列表的第一個元素，如果此列表為空，則返回null |
E peekLast() | 此方法檢索但不刪除此列表的最后一個元素，如果此列表為空，則返回null |
4、常用方法_作為鏈表
| 方法名 | 方法說明 |
|---|---|
void add(int index, E e) | 此方法將指定的元素插入此列表中的指定位置。 |
E remove(int index) | 此方法刪除此列表中指定位置的元素 |
E remove(Object o) | 此方法從該列表中刪除指定元素的第一個匹配項（如果存在） |
E set(int index, E e) | 此方法使用指定的元素替換此列表中指定位置的元素 |
E get(int index) | 此方法返回此列表中指定位置的元素 |
E getFirst() | 此方法返回此列表中的第一個元素 |
E getLast() | 此方法返回此列表中的最后一個元素 |
int size() | 此方法返回此列表中的元素數 |
boolean contains(Object o) | 如果此列表包含指定的元素，則此方法返回true |
boolean isEmpty() | 如果此列表為空，則此方法返回true |
int indexOf(Object o) | 此方法返回此列表中第一次出現的指定元素的索引，如果此列表不包含該元素，則返回-1 |
int lastIndexOf(Object o) | 此方法返回此列表中指定元素最后一次出現的索引，如果此列表不包含該元素，則返回-1 |
void clear() | 此方法將從此列表中刪除所有元素 |
Object clone() | 此方法返回返回此LinkedList的淺表副本 |
Object[] toArray() | 此方法以適當的順序（從第一個元素到最后一個元素）返回包含此列表中所有元素的數組 |
<T> T[] toArray(T[] a) | 此方法以適當的順序（從第一個元素到最后一個元素）返回包含此列表中所有元素的數組，返回數組的運行時類型是指定數組的運行時類型 |
四、相關知識點
1、關于 Queue 隊列
隊列（Queue）：也是一種操作受限的線性表，只允許在表的一端進行插入，而在表的另一端進行刪除。向隊列中插入元素稱為入隊或進隊；刪除元素稱為出隊或離隊。
這和我們日常生活中的排隊是一致的，最早排隊的也是最早離隊的。其操作的特性是先進先出（First In First Out, FIFO），故又稱為先進先出的線性表。基本上，一個隊列就是一個先入先出（FIFO）的數據結構
在Java 中 Queue 接口與 List、Set 同一級別，都是繼承了 Collection 接口。LinkedList 實現了 Deque 接口。
2、關于 ArrayList 和 LinkedList 的區別
在結構上，ArrayList 底層是數組，在內存上是連續的；LinkedList 底層是雙向鏈表，在內存上是不連續的
在性能上，ArrayList 由于內存上連續，支持隨機查詢，查詢速度更快，但是在增刪時由于會涉及到，數據的移動和數組的擴容，往往是要慢于 LinkedList 的，但并不絕對，可以提前設置好足夠的數組空間，并采用尾插的方式
3、算法：翻轉鏈表
假設鏈表為 1→2→3→?，我們想要把它改成 ?←1←2←3。
在遍歷鏈表時，將當前節點的 next 指針改為指向前一個節點。由于節點沒有引用其前一個節點，因此必須事先存儲其前一個節點。在更改引用之前，還需要存儲后一個節點。最后返回新的頭引用。
class Solution {public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}
}
