鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)，鏈表是由一連串的結(jié)點組成，這個節(jié)點就是鏈結(jié)點，每個鏈結(jié)點都由數(shù)據(jù)域和指針域兩部分組成。

[[337325]]

使用鏈表結(jié)構(gòu)可以克服數(shù)組結(jié)構(gòu)需要預(yù)先知道數(shù)據(jù)大小的缺點，鏈表結(jié)構(gòu)可以充分利用計算機內(nèi)存空間，實現(xiàn)靈活的內(nèi)存動態(tài)管理。但是鏈表失去了數(shù)組隨機讀取的優(yōu)點，同時鏈表由于增加了結(jié)點的指針域，空間開銷比較大。

鏈表比較好的一種理解是：將鏈表看成一個火車，每個車廂之間都是相互連接的，只要找到火車頭，就可以找到具體的車身。鏈表也是，我們只關(guān)心它的頭。

一 單向鏈表

1.1 單向鏈表原理圖

單向鏈表的一個鏈結(jié)點包含數(shù)據(jù)域和下一個鏈結(jié)點的指針。頭結(jié)點也包含數(shù)據(jù)域和指針域，但是一般為了方便查找，頭節(jié)點不寫數(shù)據(jù)，最后一個結(jié)點的指針指向空。

1.2 實現(xiàn)單向鏈表的存儲等操作

創(chuàng)建一個鏈結(jié)點的實體類

public class Node { 
 
    // 數(shù)據(jù)域 
    public long data; 
    // 指針域 
    public Node next; 
 
    public Node(long value){ 
        this.data = value; 
    } 
} 

1.2.1 插入一個節(jié)點

在頭節(jié)點后插入一個結(jié)點，第一步需要將新插入的結(jié)點指向頭結(jié)點指向的結(jié)點，第二步將頭結(jié)點指向新插入的結(jié)點。插入結(jié)點只需要改變一個引用，所以復(fù)雜度為O(1)。

public class LinkList { 
 
    private Node head; 
    /** 
     * 在頭節(jié)點之后插入一個節(jié)點 
     */ 
    public void insertFirst(long value){ 
        Node node = new Node(value); 
        node.next = head; 
        head = node; 
    } 
} 

1.2.2 頭結(jié)點后刪除一個結(jié)點

在頭結(jié)點后刪除一個結(jié)點，就是讓頭結(jié)點指向這個結(jié)點的下一個結(jié)點。復(fù)雜度也是O(1)。

public Node deleteFirst(){ 
    Node tmp = head; 
    head = tmp.next; 
    return tmp; 
} 

1.2.3 根據(jù)數(shù)據(jù)域查找結(jié)點

查找需要比對每個結(jié)點的數(shù)據(jù)，理論上查找一個結(jié)點平均需要N/2次，所以復(fù)雜度為O(N)。

public Node find(long value){ 
 
    Node current = head; 
    while (current.data != value){ 
        if(current.next == null){ 
            return null; 
        } 
        current = current.next; 
    } 
    return current; 
} 

1.2.4 根據(jù)數(shù)據(jù)與刪除結(jié)點

查找需要比對每個結(jié)點的數(shù)據(jù)，理論上刪除一個結(jié)點平均需要N/2次，所以復(fù)雜度為O(N)。

public Node delete(int value){ 
    Node current = head; 
    // 當前結(jié)點的前一個結(jié)點 
    Node pre = head; 
    while (current.data != value){ 
        if(current.next == null){ 
            return null; 
        } 
        pre = current; 
        current = current.next; 
    } 
    if(current == head){ 
        head = head.next; 
    }else{ 
        pre.next = current.next; 
    } 
    return current; 
} 

二 雙端鏈表

2.1 雙端鏈表原理圖

雙端鏈表是在單向鏈表的基礎(chǔ)上，頭結(jié)點增加了一個尾結(jié)點的引用。

2.2 實現(xiàn)雙端鏈表的存儲等操作

2.2.1 從頭部插入結(jié)點

如果鏈表為空，則設(shè)置尾結(jié)點就是新添加的結(jié)點。復(fù)雜度為O(1)。

public class FirstLastLinkList { 
 
    private Node first; 
    private Node last; 
    /** 
     * 在頭結(jié)點之后插入一個節(jié)點 
     */ 
    public void insertFirst(long value){ 
        Node node = new Node(value); 
        if(first == null){ 
            last = node; 
        } 
        node.next = first; 
        first = node; 
    } 
} 

2.2.2 從尾部插入結(jié)點

如果鏈表為空，則設(shè)置頭結(jié)點為新添加的結(jié)點，否則設(shè)置尾結(jié)點的后一個結(jié)點為新添加的結(jié)點。復(fù)雜度為O(1)。

public void insertLast(long value){ 
    Node node = new Node(value); 
    if(first == null){ 
        first = node; 
    }else{ 
        last.next = node; 
    } 
    last = node; 
} 

2.2.3 從頭部進行刪除

判斷頭結(jié)點是否有下一個結(jié)點，如果沒有則設(shè)置尾結(jié)點為null，復(fù)雜度為O(1)。

public Node deleteFirst(){ 
 
    Node tmp = first; 
    if(first.next == null){ 
        last = null; 
    } 
    first = tmp.next; 
    return tmp; 
} 

三 雙向鏈表

3.1 雙向鏈表原理圖

每個結(jié)點除了保存對后一個結(jié)點的引用外，還保存著對前一個結(jié)點的引用。

3.2 實現(xiàn)雙向鏈表的存儲等操作鏈結(jié)點實體類

public class Node { 
 
    // 數(shù)據(jù)域 
    public long data; 
    // 后一個結(jié)點指針域 
    public Node next; 
    // 前一個結(jié)點指針域 
    public Node prev; 
 
    public Node(long value){ 
        this.data = value; 
    } 
} 

3.2.1 從頭部插入結(jié)點

如果鏈表為空，則設(shè)置尾結(jié)點為新添加的結(jié)點，如果不為空，還需要設(shè)置頭結(jié)點的前一個結(jié)點為新添加的結(jié)點。插入結(jié)點只需要改變兩個結(jié)點的引用，所以復(fù)雜度為O(1)。

public class DoubleLinkList { 
 
    private Node first; 
    private Node last; 
 
    /** 
     * 在頭結(jié)點之后插入一個節(jié)點 
     */ 
    public void insertFirst(long value){ 
        Node node = new Node(value); 
        if(first == null){ 
            last = node; 
        } else{ 
            first.prev = node; 
        } 
        node.next = first; 
        first = node; 
    } 
} 

3.2.2 從尾部插入結(jié)點

如果鏈表為空，則設(shè)置頭結(jié)點為新添加的結(jié)點，否則設(shè)置尾結(jié)點的后一個結(jié)點為新添加的結(jié)點。同時設(shè)置新添加的結(jié)點的前一個結(jié)點為尾結(jié)點。插入結(jié)點只需要改變1個結(jié)點的引用，所以復(fù)雜度為O(1)。

public void insertLast(long value){ 
    Node node = new Node(value); 
    if(first == null){ 
        first = node; 
    }else{ 
        last.next = node; 
        node.prev = last; 
    } 
    last = node; 
} 

3.2.3 從頭部刪除結(jié)點

判斷頭結(jié)點是否有下一個結(jié)點，如果沒有則設(shè)置尾結(jié)點為null，否則設(shè)置頭結(jié)點的下一個結(jié)點的prev為null。復(fù)雜度也為O(1)。

public Node deleteFirst(){ 
 
    Node tmp = first; 
    if(first.next == null){ 
        last = null; 
    }else{ 
        first.next.prev = null; 
    } 
    first = tmp.next; 
    return tmp; 
} 

3.2.4 從尾部刪除結(jié)點

如果頭結(jié)點后沒有其他結(jié)點，則設(shè)置頭結(jié)點為null，否則設(shè)置尾結(jié)點的前一個結(jié)點的next為null，設(shè)置尾結(jié)點為前一個結(jié)點。復(fù)雜度為O(1)。

public Node deleteLast(){ 
 
    Node tmp = last;  
    if(first.next == null){ 
        first = null; 
    }else{ 
        last.prev.next = null;   
    } 
    last = last.prev; 
    return last; 
} 

四 總結(jié)

鏈表包含一個頭結(jié)點和多個結(jié)點，頭結(jié)點包含一個引用，這個引用通常叫做first，它指向鏈表的第一個鏈結(jié)點。結(jié)點的next為null，則意味著這個結(jié)點是尾結(jié)點。與數(shù)組相比，鏈表更適合做插入、刪除操作，而查找操作的復(fù)雜度更高。還有一個優(yōu)勢就是鏈表不需要初始化內(nèi)存大小，不會造成內(nèi)存溢出(數(shù)組中插入元素個數(shù)超過數(shù)組長度)或內(nèi)存浪費(聲明的數(shù)組長度比實際放的元素長)。

本文轉(zhuǎn)載自微信公眾號「Java旅途」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系Java旅途公眾號。