思路

  1. 初始化 node 並配置當前 node value 和 next node
  2. 配置開始 node 和 結束 node

實作

初始化

public class LinkImpl {
    // 內部類
    static class Node {
        Integer val;
        Node next;

        // constructor
        public Node(int val) {
            this.val = val;
        }
    }

    private Node start;
    private Node end;

    public LinkImpl() {}
}

測試情境

public static void main(String[] args) {
    /** initialize **/
    LinkImpl mylist = new LinkImpl();

    /** add O(1) - start **/
    mylist.add(9);

    /** add O(1) **/
    mylist.add(11);
    mylist.add(2);
    mylist.add(98);
    mylist.add(35);

    /** search O(n) **/
    int val = mylist.search(98);

    /** remove O(n) **/
    mylist.remove(2);
    mylist.remove(9); // remove start
    mylist.remove(35); // remove end

    System.out.println();
}

新增 O(1)

public void add(int val) {
    if (start == null) { // 第一個
        start = new Node(val); // new Node
        end = start; // end = start
    } else {
        end.next = new Node(val); // 不是第一個
        end = end.next; // 接續在後面
    }
}

查詢 O(n)

public Integer search(int val) {
    if (start == null) return null; // 如為空返回null

    Node node = start; // 從第一個開始跑
    while (true) {
        if (node == null) break; // 跑到最後一個了 break

        if (node.val == val) { // 找到目標
            return node.val;
        }

        node = node.next; // 沒有符合繼續找
    }

    return null; //都沒有
}

刪除 O(n)

public void remove(int val) { //用 remove(2), remove(9<first>), remove(35)

    /** step01: search **/
    Node node = start; //9,11,2,98,35
    Node node_target = null;
    Node node_prev = null;

    while(true) {
        if (node == null) break; // 為空 break

        if (node.val == val) { // 9!=2,11!= 2, 2=2
            node_target = node; // node_target =2
            break; // 跳出
        }

        node_prev = node; // 記錄前node(用於下面) node_prev=9,11,2,98
        node = node.next; // 若無繼續  node=9>11, 11>2, 2>98
    }

    /** step02: delete **/
    if (node_target == null) return; // 無找到無法刪除 跳出
    if (node_target == start) { //目標=開頭, 2!=9, 2!=11
        start = start.next; //start=9
    } else if (node_target == end) { //目標=結尾 2!=35, 35=35
        node_prev.next = null; //98的下一個清空
        end = node_prev; //update 98為最後一個
    } else {
        // prev -> X -> latter
        node_prev.next = node_target.next; //  9>11 -> 2>98跳過目標連到下一個
    }
}

TC:

  1. add: O(1)
  2. search: O(n)
  3. remove: O(n)