什么是單向鏈表？單向鏈表基礎(chǔ)操作

在計(jì)算機(jī)科學(xué)中，鏈表是數(shù)據(jù)元素的線性集合，其每個元素都指向下一個元素，元素存儲上并不連續(xù)。鏈表可以分為單向鏈表和雙向鏈表。

單向鏈表，每個元素只知道其下一個元素是誰。

雙向鏈表，每個元素知道其上一個元素和下一個元素。

循環(huán)鏈表，通常的鏈表尾節(jié)點(diǎn) tail 指向的都是 null，而循環(huán)鏈表的 tail 指向的是頭節(jié)點(diǎn) head。鏈表內(nèi)還有一種特殊的節(jié)點(diǎn)稱為哨兵(Sentinel)節(jié)點(diǎn)，也叫做啞元( Dummy)節(jié)點(diǎn)，它不存儲數(shù)據(jù)，通常用作頭尾，用來簡化邊界判斷。

單向鏈表

根據(jù)單向鏈表的定義，首先定義一個存儲 value 和 next 指針的類 Node，和一個描述頭部節(jié)點(diǎn)的引用。

public class SinglyLinkedList {
    
    private Node head; // 頭部節(jié)點(diǎn)
    
    private static class Node { // 節(jié)點(diǎn)類
        int value;
        Node next;

        public Node(int value, Node next) {            this.value = value;
            this.next = next;
        }
    }
}

在上述代碼中Node 定義為內(nèi)部類，是為了對外隱藏實(shí)現(xiàn)細(xì)節(jié)，沒必要讓類的使用者關(guān)心 Node 結(jié)構(gòu)定義為 static 內(nèi)部類，是因?yàn)?Node 不需要與 SinglyLinkedList 實(shí)例相關(guān)，多個 SinglyLinkedList實(shí)例能共用 Node 類定義。下面演示單向鏈表的創(chuàng)建方法

頭部添加（頭插法）

public class SinglyLinkedList {
    // ...
    public void addFirst(int value) {
        this.head = new Node(value, this.head);
    }
}

如果 this.head == null，新增節(jié)點(diǎn)指向 null，并作為新的 this.head。如果 this.head != null，新增節(jié)點(diǎn)指向原來的 this.head，并作為新的 this.head。注意賦值操作執(zhí)行順序是從右到左

尾部添加

public class SinglyLinkedList {
    // ...
    private Node findLast() {
        if (this.head == null) {
            return null;
        }
        Node curr;
        for (curr = this.head; curr.next != null; ) {
            curr = curr.next;
        }
        return curr;
    }
    
    public void addLast(int value) {
        Node last = findLast();
        if (last == null) {
            addFirst(value);
            return;
        }
        last.next = new Node(value, null);
    }
}

注意，找最后一個節(jié)點(diǎn)，終止條件是 curr.next == null ，分成兩個方法是為了代碼清晰，而且 findLast() 之后還能復(fù)用。

尾部添加多個

public class SinglyLinkedList {
    // ...
    public void addLast(int first, int... rest) {
        
        Node sublist = new Node(first, null);
        Node curr = sublist;
        for (int value : rest) {
            curr.next = new Node(value, null);
            curr = curr.next;
        }
        
        Node last = findLast();
        if (last == null) {
            this.head = sublist;
            return;
        }
        last.next = sublist;
    }
}

先串成一串 sublist，再作為一個整體添加。
根據(jù)索引獲取

public class SinglyLinkedList {
    // ...
    private Node findNode(int index) {
        int i = 0;
        for (Node curr = this.head; curr != null; curr = curr.next, i++) {
            if (index == i) {
                return curr;
            }
        }
        return null;
    }
    
    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
    }
    
    public int get(int index) {
        Node node = findNode(index);
        if (node != null) {
            return node.value;
        }
        throw illegalIndex(index);
    }
}

同樣，分方法可以實(shí)現(xiàn)復(fù)用

插入

public class SinglyLinkedList {
    // ...
    public void insert(int index, int value) {
        if (index == 0) {
            addFirst(value);
            return;
        }
        Node prev = findNode(index - 1); // 找到上一個節(jié)點(diǎn)
        if (prev == null) { // 找不到
            throw illegalIndex(index);
        }
        prev.next = new Node(value, prev.next);
    }
}

注意：插入包括下面的刪除，都必須找到上一個節(jié)點(diǎn)。

刪除

public class SinglyLinkedList {
    // ...
    public void remove(int index) {
        if (index == 0) {
            if (this.head != null) {
                this.head = this.head.next;
                return;
            } else {
                throw illegalIndex(index);
            }
        }
        Node prev = findNode(index - 1);
        Node curr;
        if (prev != null && (curr = prev.next) != null) {
            prev.next = curr.next;
        } else {
            throw illegalIndex(index);
        }
    }
}

第一個 if 塊對應(yīng)著 removeFirst 情況，最后一個 if 塊對應(yīng)著至少得兩個節(jié)點(diǎn)的情況，不僅僅判斷上一個節(jié)點(diǎn)非空，還要保證當(dāng)前節(jié)點(diǎn)非空。