自己動手實現java資料結構（二） 連結串列
1.連結串列介紹
前面我們已經介紹了向量，向量是基於陣列進行資料儲存的 線性表 。今天，要介紹的是線性表的另一種實現方式--- 連結串列 。
連結串列和向量都是線性表，從使用者的角度上依然被視為一個線性的列表結構。但是，連結串列內部儲存資料的方式卻和向量大不相同：連結串列的核心是 節點 。節點儲存"資料"的同時還維護著"關聯節點的引用"。 要理解連結串列，首先必須理解連結串列的內部節點結構 。
最簡單的連結串列結構是 單向連結串列 ，單向連結串列中的內部節點儲存著資料( data )和其關聯的下一個節點的引用( next )。
data 代表儲存的資料， next 代表所關聯下一個節點的引用
一個邏輯上儲存了 【a，b，c】 三個元素的連結串列，長度為3，三個元素分別被三個節點儲存。
2.連結串列ADT介紹
連結串列作為線性表的一種，和向量一樣實現了List介面。
/**
* 列表ADT 介面定義
*/
public interface List <E> {
/**
* @return 返回當前列表中元素的個數
*/
int size();
/**
* 判斷當前列表是否為空
* @return 如果當前列表中元素個數為0，返回true；否則，返回false
*/
boolean isEmpty();
/**
* 返回元素"e"在列表中的下標值
* @param e查詢的元素"e"
* @return返回"obj"元素在列表中的下標值;
*"obj"不存在於列表中，返回-1;
*/
int indexOf(E e);
/**
* 判斷元素"e"是否存在於列表中
* @param e查詢的元素"e"
* @return返回"true"代表存在，返回"false"代表不存在;
*/
boolean contains(E e);
/**
* 在列表的末尾插入元素"e"
* @param e 需要插入的元素
* @return插入成功，返回true；否則返回false
* */
boolean add(E e);
/**
* 在列表的下標為"index"位置處插入元素"e"
* @param index 插入位置的下標
* @param e需要插入的元素
*/
void add(int index, E e);
/**
*從列表中找到並且移除"e"物件
* @param e需要被移除的元素"e"
* @return找到並且成功移除返回true；否則返回false
*/
boolean remove(E e);
/**
* 移除列表中下標為"index"位置處的元素
* @param index需要被移除元素的下標
* @return返回被移除的元素
*/
E remove(int index);
/**
* 將列表中下標為"index"位置處的元素替代為"e"
* @param index 需要被替代元素的下標
* @param e新的元素
* @return返回被替代的元素
*/
E set(int index,E e);
/**
* 返回列表中下標為"index"位置處的元素
* @param index 查詢元素的"index"元素
* @return返回找到的元素
*/
E get(int index);
/**
* 清除列表中所有元素
* */
void clear();
/**
* 獲得迭代器
* */
Iterator<E> iterator();
}
3.連結串列實現細節
由於使用java作為實現的語言，因此在設計上參考了jdk自帶的連結串列資料結構： java.util.LinkedList 類。
LinkedList是一個雙端雙向連結串列，因此我們的連結串列實現也是一個 雙端雙向連結串列 。相比單向連結串列，雙端雙向連結串列功能更加強大，當然也稍微複雜一點。
3.1 連結串列內部節點
雙端雙向連結串列內部節點的特點是：每個節點同時擁有該節點 "前驅" 和 "後繼" 的節點引用( 雙向 )。
需要注意的是，對於內部節點兩端的引用在不同地方存在著不同稱呼。如" 前驅 (predecess)"/" 後繼 (success)"、" 前一個 (previous)"/" 下一個 (next)"、" 左 (left)/ 右 (right)"等。不必糾結於名詞叫法，用自己的方式理解就行。 "重要的不是它們叫什麼，而是它們是什麼" 。
個人認為" 左 (left)/ 右 (right)"的稱呼比較形象(比較像一群小人，手拉手)，所以在這篇部落格中統一使用這種叫法。同時為了描述的簡潔，下文中的" 連結串列 "預設指的就是" 雙端雙向連結串列 "。
連結串列內部節點結構示意圖：
在我們的連結串列實現中，將內部節點抽象為一個私有的靜態內部類。首先我們有：
public class LinkedList <E> implements List <E>{
/**
* 連結串列內部節點類
*/
private static class Node <T>{
/**
* 左邊關聯的節點引用
* */
Node<T> left;
/**
* 右邊關聯的節點引用
* */
Node<T> right;
/**
* 節點儲存的資料
* */
T data;
//===================================內部節點 建構函式==================================
private Node() {}
private Node(T data) {
this.data = data;
}
/**
* 將一個節點作為"當前節點"的"左節點" 插入連結串列
* @param node需要插入的節點
* */
private void linkAsLeft(Node<T> node){
//:::先設定新增節點的 左右節點
node.left = this.left;
node.right = this;
//:::將新增節點插入 當前節點和當前節點的左節點之間
this.left.right = node;
this.left = node;
}
/**
* 將一個節點作為"當前節點"的"右節點" 插入連結串列
* @param node需要插入的節點
* */
private void linkAsRight(Node<T> node){
//:::先設定新增節點的 左右節點
node.left = this;
node.right = this.right;
//:::將新增節點插入 當前節點和當前節點的左節點之間
node.right.left = node;
node.right = node;
}
/**
* 將"當前節點"移出連結串列
* */
private void unlinkSelf(){
//:::令當前連結串列的 左節點和右節點建立關聯
this.left.right = this.right;
//:::令當前連結串列的 右節點和左節點建立關聯
this.right.left = this.left;
//:::這樣,當前節點就從連結串列中被移除了(同時,作為私有的內部類,當前節點不會被其它物件引用,很快會被GC回收)
}
}
}
我們在內部節點類中提供了幾個常用的方法，為接下來的連結串列操作提供基礎。
linkAsLeft操作舉例說明：
已知連結串列中存在 【a，c】 兩個節點，現在 c 節點呼叫 linkAsLeft 方法，將 b 節點作為 c 的 左節點 插入連結串列(這時， c 節點就是 this )。( linkAsRight 原理類似 )
linkAsLeft操作示意圖：
unlinkSelf操作舉例說明：
已知連結串列中存在 【a，b，c】三 個節點，現在 b 節點呼叫 unlinkSelf 方法，將 b 節點自身移出連結串列(這時， b 節點就是 this )。
unlinkSelf操作示意圖：
可以看到 插入 和 移除 操作對於節點左右引用的改變是 互逆的 。
移除操作執行完成後，雖然 b 節點還持有 a ， c 兩節點的引用，但是 Node 作為封裝的私有內部類，可以確保 b 節點本身不會被其它物件引用， 很快會被GC回收 。
3.2 連結串列基本屬性
連結串列作為一個數據結構容器，擁有一些必備的屬性。
連結串列內部維護著 首、尾哨兵 兩個內部節點( 雙端 )，作為連結串列的第一個和最後一個節點，新插入的節點總是處於這兩個哨兵節點之間，使用者也無法感知哨兵節點的存在。哨兵節點並不用於儲存資料，其存在的主要目的是為了簡化邊界條件的邏輯。
舉個例子： 在節點插入時 ，必須判斷當前是否第一個節點，來決定是否需要建立和之前節點的聯絡； 在節點刪除時 ，也必須判斷自己的左右節點是否存在，避免空指標異常。首尾哨兵節點的引入使得任何情況下，節點插入，刪除時都可以確保其 左右節點一定存在 ，從而避免大量的異常判斷。
可以看到，哨兵節點的引入簡化了程式碼在邊界條件時的各種判斷邏輯。這提高了執行效率，更重要的是降低了複雜性，使程式碼變得更容易理解，也更可靠。
public class LinkedList <E> implements List <E>{
/**
* 連結串列 頭部哨兵節點
* */
private Node<E> first;
/**
* 連結串列 尾部哨兵節點
* */
private Node<E> last;
/**
* 連結串列 邏輯大小
* */
private int size;
public LinkedList() {
this.first = new Node<>();
this.last = new Node<>();
//:::將首尾哨兵節點 進行連線
this.first.right = this.last;
this.last.left = this.first;
//:::初始化size
this.size = 0;
}
}
3.3 較為簡單的size()，isEmpty()，indexOf()，contains()方法實現：
@Override
public int size() {
return this.size;
}
@Override
public boolean isEmpty() {
return (this.size == 0);
}
@Override
public int indexOf(E e) {
//:::當前節點 = 列表頭部哨兵
Node<E> currentNode = this.first;
if(e != null){
//:::如果不是查詢null元素
//:::遍歷列表
for(int i=0; i<this.size; i++){
//:::不斷切換當前節點 ==> "當前節點 = 當前節點的右節點"
currentNode = currentNode.right;
//:::如果滿足要求（注意: equals順序不能反,否則可能會有currentNode.data為空,出現空指標異常）
if(e.equals(currentNode.data)){
//:::返回下標
return i;
}
}
}else{
//:::如果是查詢null元素
//:::遍歷列表
for(int i=0; i<this.size; i++){
//:::不斷切換當前節點 ==> "當前節點 = 當前節點的右節點"
currentNode = currentNode.right;
//:::如果是null元素
if(currentNode.data == null){
//:::返回下標
return i;
}
}
}
//:::遍歷列表未找到相等的元素,返回特殊值"-1"代表未找到
return -1;
}
@Override
public boolean contains(E e) {
//:::複用indexOf方法,如果返回-1代表不存在;反之,則代表存在
return (indexOf(e) != -1);
}
連結串列 indexOf、contains方法的時間複雜度：
indexOf方法的實現和向量類似，是通過一次迴圈遍歷來進行查詢的，從頭部節點不停地跳轉到下一個節點，直到發現目標節點或者到達尾部哨兵節點。
因此 indexOf 方法、 contains 方法的 時間複雜度 都是 O(n) 。
3.4 連結串列增刪改查介面實現
3.4.1下標越界檢查
連結串列基於下標的增刪改查操作都需要進行下標的越界檢查。這裡優化了前面 "向量篇" 部落格中提到的缺陷，針對不同的錯誤，會丟擲不同型別的 自定義異常， 使客戶端可以進行更細緻的異常處理。
/**
* 插入時,下標越界檢查
* @param index 下標值
*/
private void rangeCheckForAdd(int index){
//:::如果大於size的值,丟擲異常
//:::注意：插入時,允許插入線性表的末尾,因此(index == size)是合法的
if(index > this.size){
throw new OutOfIndexBoundException("index errorindex=" + index + " size=" + this.size) ;
}
if(index < 0){
throw new NegativeOfIndexException("index errorindex=" + index + " size=" + this.size) ;
}
}
/**
* 下標越界檢查
* @param index 下標值
*/
private void rangeCheck(int index){
//:::如果大於等於size的值,丟擲異常
if(index >= this.size){
throw new OutOfIndexBoundException("index errorindex=" + index + " size=" + this.size) ;
}
if(index < 0){
throw new NegativeOfIndexException("index errorindex=" + index + " size=" + this.size) ;
}
}
同時，連結串列基於下標的操作都需要先查詢出下標對應的內部節點，通過操縱對應的內部節點來進行相關操作。因此需要抽象出一個通用的查詢方法。
/**
* 返回下標對應的 內部節點
* */
private Node<E> find(int index){
//:::要求呼叫該方法前,已經進行了下標越界校驗
//:::出於效率的考慮,不進行重複校驗
//:::判斷下標在當前列表的大概位置（前半段 or 後半段）儘量減少遍歷查詢的次數
if(index < this.size/2){
//:::下標位於前半段
//:::從頭部結點出發,進行遍歷(從左到右)
Node<E> currentNode = this.first.right;
//:::遍歷(index)次
for(int i=0; i<index; i++){
currentNode = currentNode.right;
}
return currentNode;
}else{
//:::下標位於後半段
//:::從尾部結點出發,進行遍歷(從右到左)
Node<E> currentNode = this.last.left;
//:::遍歷(size-index)次
for(int i=index; i<size; i++){
currentNode = currentNode.left;
}
return currentNode;
}
}
find方法的時間複雜度 :
可以看到，find方法會根據下標所處的大概位置決定開始遍歷的方向(儘量減少遍歷查詢的次數)， 下標越接近頭部或者尾部，查詢次數越少 。因此下標在靠近頭部、尾部時效率較高，而在居中位置效率較低。
從概率的角度上來看，下標訪問是隨機的，因此 find 方法的時間複雜度被認為是 O(n) 。
3.4.2 連結串列的插入方法實現
@Override
public boolean add(E e) {
//:::將新的資料 插入到列表末尾 ==> 作為last節點的前一個節點插入
this.last.linkAsLeft(new Node<>(e));
//:::size自增
this.size++;
return true;
}
@Override
public void add(int index, E e) {
//:::插入時,下標越界檢查
rangeCheckForAdd(index);
//:::查詢出下標對應的 目標節點
Node<E> targetNode = find(index);
//:::將新的資料節點 作為目標節點的前一個節點插入
targetNode.linkAsLeft(new Node<>(e));
//:::size自增
this.size++;
}
插入方法的時間複雜度:
尾部插入：
尾部插入方法中，由於我們維護了一個 last 哨兵節點，通過直接將新節點插入 last 哨兵的左邊，完成尾部資料的插入。
因此，尾部插入方法的 時間複雜度 為 O(1) 。
下標插入：
下標插入方法中，依賴 find 方法查詢出下標對應的節點，然後將新節點進行插入。
因此，下標插入方法的 時間複雜度 為 O(n) ；對於 頭部，尾部節點 的插入， 時間複雜度 為 O(1) 。
3.4.3 刪除方法的實現
@Override
public boolean remove(E e) {
//:::當前節點 = 列表頭部哨兵
Node<E> currentNode = this.first;
if(e != null){
//:::如果不是查詢空元素
//:::遍歷列表
for(int i=0; i<this.size; i++){
//:::不斷切換當前節點 ==> "當前節點 = 當前節點的右節點"
currentNode = currentNode.right;
//:::如果滿足要求（注意: equals順序不能反,否則可能出現currentNode.data為空,出現空指標異常）
if(e.equals(currentNode.data)){
//:::匹配成功,將當前節點從連結串列中刪除
currentNode.unlinkSelf();
//:::刪除成功,返回true
return true;
}
}
}else{
//:::如果是查詢null元素
//:::遍歷列表
for(int i=0; i<this.size; i++){
//:::不斷切換當前節點 ==> "當前節點 = 當前節點的右節點"
currentNode = currentNode.right;
//:::如果滿足要求
if(currentNode.data == null){
//:::匹配成功,將當前節點從連結串列中刪除
currentNode.unlinkSelf();
//:::刪除成功,返回true
return true;
}
}
}
//:::遍歷列表未找到相等的元素,未進行刪除 返回false
return false;
}
@Override
public E remove(int index) {
//:::下標越界檢查
rangeCheck(index);
//:::獲得下標對應的 Node
Node<E> targetNode = find(index);
//:::將目標節點從連結串列中移除
targetNode.unlinkSelf();
//:::size自減
this.size--;
//:::返回被移除的節點data值
return targetNode.data;
}
刪除方法的時間複雜度:
特定元素刪除：
連結串列特定元素的刪除和 find 方法類似，通過一次遍歷獲得目標節點，然後進行刪除。
因此，特定元素的刪除方法 時間複雜度 為 O(n) 。
下標刪除：
下標刪除方法中，依賴 find 方法查詢出下標對應的節點，然後將目標節點進行刪除。
因此，下標刪除方法的 時間複雜度 為 O(n) ；對於 頭部，尾部節點 的刪除， 時間複雜度 為 O(1) 。
3.4.4 修改/查詢方法實現
@Override
public E set(int index, E e) {
//:::下標越界檢查
rangeCheck(index);
//:::獲得下標對應的 Node
Node<E> targetNode = find(index);
//:::先暫存要被替換的"data"
E oldValue = targetNode.data;
//:::將當前下標對應的"data"替換為"e"
targetNode.data = e;
//:::返回被替換的data
return oldValue;
}
@Override
public E get(int index) {
//:::下標越界檢查
rangeCheck(index);
//:::獲得下標對應的 Node
Node<E> targetNode = find(index);
return targetNode.data;
}
修改/查詢方法的時間複雜度：
可以看到，連結串列基於下標的修改和查詢都依賴於 find 方法。
因此，修改/查詢方法的 時間複雜度 為 O(n) ；對於 頭部，尾部節點 的修改和查詢， 時間複雜度 為 O(1) 。
3.5 連結串列其它介面
3.5.1 clear方法
clear方法用於清空連結串列內的元素，初始化連結串列。
@Override
public void clear() {
//:::當頭部哨兵節點不和尾部哨兵節點直接相連時
while(this.first.right != this.last){
//:::刪除掉頭部哨兵節點後的節點
remove(0);
}
//:::執行完畢後,代表連結串列被初始化,重置size
this.size = 0;
}
3.5.2 toString方法
@Override
public String toString() {
Iterator<E> iterator = this.iterator();
//:::空列表
if(!iterator.hasNext()){
return "[]";
}
//:::列表起始使用"["
StringBuilder s = new StringBuilder("[");
//:::反覆迭代
while(true){
//:::獲得迭代的當前元素
E data = iterator.next();
//:::判斷當前元素是否是最後一個元素
if(!iterator.hasNext()){
//:::是最後一個元素，用"]"收尾
s.append(data).append("]");
//:::執行完畢 返回拼接完成的字串
return s.toString();
}else{
//:::不是最後一個元素
//:::使用", "分割，拼接到後面
s.append(data).append(", ");
}
}
}
連結串列的 toString 方法在之前 "向量篇" 的基礎上進行了優化。基於列表 List 的 Iterator 介面進行遍歷，實現了同樣的功能。事實上，改進之後的 toString 方法也同樣可以 適用於向量 。
在 jdk 的 Collection 框架中，框架設計者要求所有的資料結構容器都必須實現 Iterator 介面，因而將 toString 方法在 AbstractCollection 這一頂層抽象類中進行了實現，達到統一所有資料結構容器 toString 方法預設行為的目的，增強了程式碼的可重用性。
4.連結串列的Iterator(迭代器)
/**
* 連結串列迭代器實現
* */
private class Itr implements Iterator<E>{
/**
* 當前迭代器游標位置
* 初始化指向 頭部哨兵節點
* */
private Node<E> currentNode = LinkedList.this.first;
/**
* 最近一次迭代返回的資料
* */
private Node<E> lastReturned;
@Override
public boolean hasNext() {
//:::判斷當前節點的下一個節點 是否是 尾部哨兵節點
return (this.currentNode.right != LinkedList.this.last);
}
@Override
public E next() {
//:::指向當前節點的下一個節點
this.currentNode = this.currentNode.right;
//:::設定最近一次返回的節點
this.lastReturned = currentNode;
//:::返回當前節點的data
return this.currentNode.data;
}
@Override
public void remove() {
if(this.lastReturned == null){
throw new IteratorStateErrorException("迭代器狀態異常: 可能在一次迭代中進行了多次remove操作");
}
//:::當前游標指向的節點要被刪除,先暫存引用
Node<E> nodeWillRemove = this.currentNode;
//:::由於當前節點需要被刪除,因此游標前移,指向當前節點的上一個節點
this.currentNode = this.currentNode.left;
//:::移除操作需要將最近一次返回設定為null，防止多次remove
this.lastReturned = null;
//:::將節點從連結串列中移除
nodeWillRemove.unlinkSelf();
}
}
迭代器在實現時需要滿足介面的行為定義， remove 方法在一次 next 迭代中不能被重複呼叫，否則會產生古怪的異常。
5.連結串列效能
連結串列作為線性表的一種，一般被用來和同為線性表的向量進行比較。
空間效率：
比起向量，連結串列的 單位資料 是儲存在內部節點之中的。而內部節點除了含有 資料域 ，還包括了 左右節點的引用 ，因此連結串列的空間效率 比向量稍差 。
時間效率：
在有些書籍或者部落格中會籠統地介紹："比起向量，連結串列的 插入，刪除 操作時間複雜度較低(向量 O(n)， 連結串列 O(1) )； 查詢，修改 操作時間複雜度較高(向量 O(1)， 連結串列 O(n) )"。
連結串列插入，刪除操作的時間複雜度本身確實是 O(1) (僅需要修改節點引用)，因為不用和向量一樣批量的移動內部元素。
但是需要注意的是，由於我們對連結串列進行了封裝，客戶端無法感知到內部節點的存在，因此也就無法獲取到內部節點的引用。所以，連結串列的插入，刪除操作其實並 不純粹 ，而總是會伴隨著 基於下標的隨機訪問 或者 特定元素的查詢 ，這會把大量的時間消耗在遍歷查詢中。
總體來說：
1. 連結串列的 增加、刪除 操作在 頭部、 尾部 的執行由於避免了大量的查詢，因此效率非常高( 時間複雜度 為 O(1) )。但是在連結串列 較為居中位置 的執行效率卻不盡如人意( 時間複雜度 為 O(n) )。
2. 連結串列的 隨機修改、查詢 操作，其 時間複雜度 為 O(n)。 相比向量，連結串列隨機查詢、修改的效率較差。
針對連結串列的上述特性可以發現，許多隻在頭尾處頻繁操作的場合，連結串列的表現很好，可以考慮通過連結串列來實現(例如： 棧 ， 佇列 等)。
6.連結串列總結
到這裡，我們已經完成了一個很基礎的連結串列資料結構。雖然比較簡單，但已經有一個基本的框架，讀者完全可以在理解思路的基礎之上進行各個維度的優化。
連結串列作為基礎的資料結構之一，其原理是值得學習和了解的。因為，許多演算法和高階的資料結構都依賴於連結串列或者連結串列的其它變種實現( 跳躍表 等)；其次連結串列這種" 將資料存放在節點中，並且維護節點之間關係 "的設計思想也存在於很多高階資料結構之中( 樹、 圖 等)，對連結串列的掌握是理解一些更復雜資料結構的基礎。
程式碼在我的 github上： ofollow,noindex">https://github.com/1399852153/DataStructures ，這篇文章 還存在許多不足之處，請多指教。