思路
- 初始化 node 並配置當前 node value 和 next node
- 配置開始 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:
- add: O(1)
- search: O(n)
- remove: O(n)