Java

Data Structure

Author: Edison Chue 2022-01-27 15 mins read

單向鏈結串列 Singly Linked List

基本介紹

Linked List 是以 Node 節點的方式來存儲，是鍊式存儲
每個節點包含 data 屬性：存放資料， next 屬性：指向下一個 Node
通過指標指向另一個地址形成 Linked List
Linked List 的各個節點不一定是連續存儲
鏈結串列分帶頭節點的鏈結串列和沒有頭節點的鏈結串列，根據實際的需求來使用
Linked List 是學 Tree (樹) 和 Graph (圖) 這些資料結構的基礎

Singly Linked List (帶頭節點) 的邏輯結構

Untitled 1.png

程式碼實現串列的節點

package com.xiran.singly_linked_list;

public class ListNode
{
    private final int id;
    private final String name;
    private final String description;
    public ListNode next; // next node

    public ListNode()
    {
        this.id = 0;
        this.name = this.description = "";
    }

    public ListNode(int id, String name, String description)
    {
        this.id = id;
        this.name = name;
        this.description = description;
    }

    public int getId()
    {
        return id;
    }

    public String getName()
    {
        return name;
    }

    public String getDescription()
    {
        return description;
    }

    @Override
    public String toString()
    {
        return "id:" + this.id + ", name: " + this.name + ", description: " + this.description;
    }
}

實現串列的思路和程式碼

Untitled 2.png

package com.xiran.singly_linked_list;

public class SinglyLinkedList
{
    // 創建頭節點（不帶資料）
    private final ListNode head = new ListNode(); // default constructor

    // 添加節點到串列
    // 當不考慮編號順序時
    // 1. 找到當前串列的最後節點
    // 2. 將最後節點的 next 指向新的節點
    public void pushBack(ListNode node)
    {
        ListNode temp = head; // 臨時指標指向頭

        // iterate till end
        while (temp.next != null)
        {
            temp = temp.next; // 後移
        }

        // temp -> end，temp 已指向串列的最後一個節點
        // 將最後節點的 next 指向新的節點
        temp.next = node;
    }

    public void printAll()
    {
        // 先判斷串列是否爲空
        if (isEmpty())
        {
            System.out.println("The list is empty.");
            return;
        }

        ListNode temp = this.head; // 臨時指標指向頭的 next（第一個有效帶資料的節點）

        // iterate till end
        while (temp.next != null)
        {
            temp = temp.next; // 後移
            System.out.println(temp); // temp.toString()
        }
    }
}

測試串列行爲

package com.xiran.singly_linked_list;

public class Main
{

    public static void main(String[] args)
    {
        // test
        var character1 = new ListNode(1, "Edison", "123123");
        var character2 = new ListNode(2, "Momiji", "456456");
        var character3 = new ListNode(3, "香菜", "是隻白癡兔");
        var character4 = new ListNode(4, "花園鰻魚", "咻咻的生日禮物");

        var myList = new SinglyLinkedList();

        myList.pushBack(character1);
        myList.pushBack(character4);
        myList.pushBack(character3);
        myList.pushBack(character2);

        myList.printAll();
    }
}

運行結果

Screen_Shot_2022-01-19_at_14.52.10.png

實現按 id 順序插入節點

具體思路如下圖：

Screen_Shot_2022-01-19_at_15.17.59.png

public class SinglyLinkedList
{
    // ...

    public void insertOrdered(ListNode node)
    {
            ListNode temp = head;
            
            // iterate till found or end
            while (temp.next != null)
            {
                if (temp.next.id == node.id)
                {
                    System.out.println("This id already exists in the list, return without insert.");
                    return; // 重複 id 直接返回
                }
                else if (temp.next.id > node.id)
                {
                    break; // temp 指到插入的位置
                }
    
                temp = temp.next; // 後移
            }
            
            // 找到要插入的位置，或是沒有找到（新增到串列尾巴）
            // 新節點的next先指到temp的next
            //      node
            //           ↘
            // temp  ->  next
            node.next = temp.next;
            
            // temp的next指到新的節點
            //      node
            //     ↗    ↘
            // temp      next
            temp.next = node;
    }

    // ...
}

測試修改後的串列行爲

package com.xiran.singly_linked_list;

public class Main
{

    public static void main(String[] args)
    {
        // test
        var character1 = new ListNode(1, "Edison", "123123");
        var character2 = new ListNode(2, "Momiji", "456456");
        var character3 = new ListNode(3, "香菜", "是隻白癡兔");
        var character4 = new ListNode(4, "花園鰻", "咻咻的生日禮物");

        var myList = new SinglyLinkedList();

        myList.insertOrdered(character1);
        myList.insertOrdered(character4);
        myList.insertOrdered(character3);
        myList.insertOrdered(character2);

        myList.printAll();
    }
}

Screen_Shot_2022-01-19_at_16.07.30.png

實現更新節點

首先爲 ListNode 新增 Getter 與 Setter。

思路：

通過 iterate 找到需要修改的節點
直接更改節點資料即可

package com.xiran.singly_linked_list;

public class ListNode
{
    // ...

    public String getName(){return name;}

    public String getDescription() {return description;}
    
    public void setName(String name) {this.name = name;}
    
    public void setDescription(String description) {this.description = description;}

    // ...
}

package com.xiran.singly_linked_list;

public class SinglyLinkedList
{
    // ...

    // 修改節點資料，根據 id 判斷修改哪個節點，node.id != id 則不修改
    public void updateNode(ListNode newNode)
    {
        if (isEmpty())
        {
            System.out.println("The list is empty.");
            return;
        }

        ListNode temp = this.head; // 臨時指標指向頭

        // iterate till found or end
        while (temp.next != null)
        {
            temp = temp.next; // 後移
            if (temp.id == newNode.id)
            {
                temp.setName(newNode.getName());
                temp.setDescription(newNode.getDescription());
                return;
            }
        }

        System.out.printf("Cannot find node. id: %d\n", newNode.id);
    }

    // ...
}

運行結果

Screen_Shot_2022-01-19_at_17.07.11.png

實現刪除節點

具體思路如下圖：

Untitled 3.png

public void deleteNode(int id)
    {
        ListNode temp = this.head; // 臨時指標指向頭

        while(temp.next != null)
        {
            if (temp.next.id == id)
            {
                // 原先：temp -> temp.next -> temp.next.next

                //           temp.next (將會被 GC 回收)
                //                    ↘
                // 刪除後：temp ------> temp.next.next
                temp.next = temp.next.next;
                return;
            }
            temp = temp.next; // 後移
        }

        System.out.printf("Cannot find node. id: %d\n", id);
    }

運行結果

Screen_Shot_2022-01-19_at_17.35.17.png

所有程式碼

節點 ListNode

package com.xiran.singly_linked_list;

public class ListNode
{
    public final int id;
    private String name;
    private String description;
    public ListNode next; // next node

    public ListNode()
    {
        this.id = 0;
        this.name = this.description = "";
    }

    public ListNode(int id, String name, String description)
    {
        this.id = id;
        this.name = name;
        this.description = description;
    }

    public String getName(){return name;}

    public String getDescription() {return description;}

    public void setName(String name) {this.name = name;}

    public void setDescription(String description) {this.description = description;}

    @Override
    public String toString()
    {
        return "id:" + this.id + ", name: " + this.name + ", description: " + this.description;
    }
}

單向鏈結串列 Singly Linked List

package com.xiran.singly_linked_list;

public class SinglyLinkedList
{
    // 創建頭節點（不帶資料）
    private final ListNode head = new ListNode(); // default constructor

    public boolean isEmpty()
    {
        return this.head.next == null;
    }

    // 添加節點到串列
    // 當不考慮編號順序時
    // 1. 找到當前串列的最後節點
    // 2. 將最後節點的 next 指向新的節點
    public void pushBack(ListNode node)
    {
        ListNode temp = this.head; // 臨時指標指向頭

        // iterate till end
        while (temp.next != null)
        {
            temp = temp.next; // 後移
        }

        // temp -> end，temp 已指向串列的最後一個節點
        // 將最後節點的 next 指向新的節點
        temp.next = node;
    }

    // 根據 id 順序插入節點
    public void insertOrdered(ListNode node)
    {
        ListNode temp = this.head; // 臨時指標指向頭

        // iterate till found or end
        while (temp.next != null)
        {
            if (temp.next.id == node.id)
            {
                System.out.printf("This id already exists in the list, return without insert. id: %d\n", node.id);
                return; // 重複 id 直接返回
            }
            else if (temp.next.id > node.id)
            {
                break; // 找到要插入的位置（在temp後，temp.next前）
            }

            temp = temp.next; // 沒有找到或是沒有找到重複，後移
        }

        // 找到要插入的位置，或是沒有找到（新增到串列尾巴）
        // 新節點的next先指到temp的next
        //      node
        //           ↘
        // temp  ->  next
        node.next = temp.next;

        // temp的next指到新的節點
        //      node
        //     ↗    ↘
        // temp      next
        temp.next = node;
    }

    // 修改節點資料，根據 id 判斷修改哪個節點，node.id != id 則不修改
    public void updateNode(ListNode newNode)
    {
        if (isEmpty())
        {
            System.out.println("The list is empty.");
            return;
        }

        ListNode temp = this.head; // 臨時指標指向頭

        // iterate till found or end
        while (temp.next != null)
        {
            temp = temp.next; // 後移
            if (temp.id == newNode.id)
            {
                temp.setName(newNode.getName());
                temp.setDescription(newNode.getDescription());
                return;
            }
        }

        System.out.printf("Cannot find node. id: %d\n", newNode.id);
    }

    public void deleteNode(int id)
    {
        ListNode temp = this.head; // 臨時指標指向頭

        while(temp.next != null)
        {
            if (temp.next.id == id)
            {
                // 原先：temp -> temp.next -> temp.next.next

                //           temp.next (將會被 GC 回收)
                //                    ↘
                // 刪除後：temp ------> temp.next.next
                temp.next = temp.next.next;
                return;
            }
            temp = temp.next; // 後移
        }

        System.out.printf("Cannot find node. id: %d\n", id);
    }

    public void printAll()
    {
        // 先判斷串列是否爲空
        if (isEmpty())
        {
            System.out.println("The list is empty.");
            return;
        }

        ListNode temp = this.head; // 臨時指標指向頭的 next（第一個有效帶資料的節點）

        // iterate till end
        while (temp.next != null)
        {
            temp = temp.next; // 後移
            System.out.println(temp); // temp.toString()
        }
    }

}

測試主程式 Main

package com.xiran.singly_linked_list;

public class Main
{

    public static void main(String[] args)
    {
        // test
        var character1 = new ListNode(1, "Edison", "123123");
        var character2 = new ListNode(2, "Momiji", "456456");
        var character3 = new ListNode(3, "香菜", "是隻白癡兔");
        var character4 = new ListNode(4, "花園鰻", "咻咻的生日禮物");

        var myList = new SinglyLinkedList();

        myList.insertOrdered(character1);
        myList.insertOrdered(character4);
        myList.insertOrdered(character3);
        myList.insertOrdered(character2);
        myList.printAll();

        System.out.println("\n修改: ");
        myList.updateNode(new ListNode(4, "咖波", "我買給自己的"));
        myList.printAll();

        System.out.println("\n修改（找不到id）: ");
        myList.updateNode(new ListNode(5, "小花園鰻魚", "滑鼠護腕"));
        myList.printAll();

        System.out.println("\n刪除 id = 4 的節點: ");
        myList.deleteNode(4);
        myList.printAll();

        System.out.println("\n再次刪除 id = 4 的節點（找不到id）: ");
        myList.deleteNode(4);
        myList.printAll();
    }
}

常見面試題

求 Singly Linked List 中有效節點的個數

獲取有效個數，太簡單不作解釋🥱


public int count()
{
    int count = 0;
    ListNode temp = this.head;

    while(temp.next != null)
    {
        temp = temp.next;
        count++;
    }

    return count;
}

求 Linked List 中倒數第 K 個節點的資料（新浪面試題）

思路如下：

編寫一個接收 head 節點與 k (倒數第K位) 的方法
先把 Linked List 從頭到尾歷遍一次，得到 List 的 length 後再計算從頭到倒數K位的個數 (length - k) ，P.S. 可以利用上一題寫好的方法獲得 length
再從 Linked List 的頭歷遍到剛剛計算的 (length - k) 位置，輸出資料
如果找到節點則返回該節點，否則則返回 null

// 查找 Singly Linked List 中第 K 個元素
public static ListNode getLastKthElement(ListNode head, int k) {
    // 若List爲空或K等於小於0， 返回null
    if (head.next == null || k <= 0) {
        return null;
    }

    // 歷遍List獲取有效個數size
    ListNode temp = head;
    int size = 0;
    while (temp.next != null) {
        temp = temp.next;
        size++;
    }

    if (k > size) return null; // 若K被List的大小還大，查找無效返回null

    // 歷遍List直到倒數K位（size - k）
    temp = head.next;
    for (int i = 0; i < size - k; i++)
    {
        temp = temp.next;
    }

    return temp;
}

Singly Linked List 反轉（騰訊面試題）

實作思路如下圖：

首先創建一個新的 head node (reverseHead)
兩個指標，current (cur: 表示當前節點，初始指到原串列的 head.next ) 跟 current next(curNext: 表示當前節點的下一個節點)
重複 4～7 步驟直到 cur 指到 null（完成迭代原串列）
暫時保存當前節點的下一個節點 (curNext = cur.next)
將 cur 的下一個節點，指到新串列的的第一個有效節點 (cur.next = reverseHead.next)
新串列 head 的下一個節點指到 cur (reverseHead.next = cur)
後移 cur (cur = curNext)

Screen_Shot_2022-01-27_at_14.43.40.png

Screen_Shot_2022-01-27_at_14.43.56.png

Screen_Shot_2022-01-27_at_14.45.25.png

重複直至 cur == null

Screen_Shot_2022-01-27_at_14.46.09.png

// 反轉 Linked List
public static void reverse(ListNode head)
{
    // 空串列或串列長度爲1
    if (head.next == null || head.next.next == null)
    {
        return;
    }

    var reversedHead = new ListNode();
    var cur = head.next; // iterator，當前節點
    var curNext = null; 

    while (cur != null)
    {
        curNext = cur.next; // 暫時保存當前節點的下一個節點
        cur.next = reversedHead.next; // 指到新串列的的第一個有效節點
        reversedHead.next = cur;
        cur = curNext; // 後移
    }

    head.next = reversedHead.next;
}

逆序列印（百度面試題）

實作思路：

方法1: 先將 List 反轉（於上述方法）然後再列印，會破壞原來串列的結構（不建議！！）

方法2: 利用 Stack（堆疊）FILO 先進後出的特性，迭代 List 並將其元素 push 到 Stack 中，其後再從 Stack 續一 pop 出列印

// 方法2
// 逆序列印 Linked List
public static void printReverse(ListNode head)
{
    if (head.next == null)
    {
        System.out.println("The List is empty!");
    }

    var stack = new Stack<ListNode>();
    // 迭代串列並將其元素push到Stack中
    var cur = head.next;
    while (cur != null) {
        stack.push(cur);
        cur = cur.next;
    }

    while(stack.size() > 0) {
        var node = stack.pop()
        System.out.println(node);
    }
}

單向鏈結串列 Singly Linked List

基本介紹

Singly Linked List (帶頭節點) 的邏輯結構

程式碼實現串列的節點

實現串列的思路和程式碼

測試串列行爲

運行結果

實現按 id 順序插入節點

測試修改後的串列行爲

實現更新節點

運行結果

實現刪除節點

運行結果

所有程式碼

常見面試題

求 Singly Linked List 中有效節點的個數

求 Linked List 中倒數第 K 個節點的資料 （新浪面試題）

Singly Linked List 反轉（騰訊面試題）

逆序列印（百度面試題）

求 Linked List 中倒數第 K 個節點的資料（新浪面試題）