အခန်း ၈ - Linked List

ယခင် အခန်းတွေမှာ Array အကြောင်းကို လေ့လာခဲ့ပါတယ်။ Array ဟာ Data တွေကို Memory ထဲမှာ တစ်ခုနဲ့တစ်ခု ကပ်လျက် စီထားတဲ့အတွက် Index နဲ့ ချက်ချင်း ရှာလို့ ရတယ် ( $O(1)$ )။ ဒါပေမယ့် အလယ်ထဲမှာ Data အသစ် ထည့်ချင်တာ၊ ဖျက်ချင်တာ ဆိုရင် နောက်က Data တွေ အကုန်လုံးကို တစ်နေရာစီ ရွှေ့ပေးရတဲ့အတွက် $O(n)$ ကုန်ကျပါတယ်။

Linked List ဆိုတာက Data တွေကို Memory ထဲမှာ ကပ်လျက် မစီတော့ဘဲ၊ နေရာ အနှံ့အပြားမှာ ထားပြီး တစ်ခုနဲ့တစ်ခုကို Pointer နဲ့ ချိတ်ဆက်ထားတဲ့ Data Structure တစ်မျိုး ဖြစ်ပါတယ်။

Treasure Hunt ဥပမာ
Treasure Hunt ကစားနည်း ကို စဉ်းစားကြည့်ပါ။ ပထမ စာရွက်မှာ "နောက်တစ်ခု အတွက် မီးဖိုချောင်ထဲ ကြည့်ပါ" လို့ ရေးထားတယ်။ မီးဖိုချောင်ရောက်တော့ နောက်စာရွက်မှာ "အိပ်ခန်းထဲ ကြည့်ပါ" လို့ ရေးထားတယ်။ စာရွက်တွေ (Data) က နေရာအနှံ့ ပြန့်ကျဲနေပေမယ့် တစ်ခုက နောက်တစ်ခုကို ညွှန်ပြ (Point) ပေးထားတဲ့အတွက် အစဉ်လိုက် လိုက်လို့ ရပါတယ်။ ဒါပေမယ့် တန်းပြီး "၅ ခုမြောက် စာရွက်" ဆို တန်းမသွားနိုင်ဘဲ ပထမ ကနေ တစ်ဆင့်ချင်း လိုက်ရှာရတာ Linked List နဲ့ တူပါတယ်။

Node Concept

Linked List ရဲ့ အခြေခံ အစိတ်အပိုင်းကို Node လို့ ခေါ်ပါတယ်။ Node တစ်ခုစီမှာ အပိုင်း ၂ ပိုင်း ပါပါတယ် —

Data (Value): သိမ်းချင်တဲ့ တန်ဖိုး။
Next (Pointer): နောက်လာမယ့် Node ရဲ့ Memory လိပ်စာ (Reference)။

အရှေ့ဆုံး Node ကို Head လို့ ခေါ်ပြီး၊ နောက်ဆုံး Node ကို Tail လို့ ခေါ်ပါတယ်။ Tail Node ရဲ့ Next က ဘာမှ မရှိတော့တဲ့အတွက် null ကို ညွှန်ထားပါတယ်။

graph LR
    Head[Head] --> A
    subgraph A["Node 1"]
    A1[Data: 10] --- A2[Next]
    end
    subgraph B["Node 2"]
    B1[Data: 20] --- B2[Next]
    end
    subgraph C["Node 3 - Tail"]
    C1[Data: 30] --- C2[Next: null]
    end
    A2 --> B
    B2 --> C

// Node တစ်ခု၏ ဖွဲ့စည်းပုံ
class ListNode {
    int val;        // Data သိမ်းရန်
    ListNode next;  // နောက် Node ကို ညွှန်ပြရန်

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

Singly Linked List

Node တစ်ခုက နောက်တစ်ခုကိုသာ (တစ်လမ်းသွား) ညွှန်ပြထားတဲ့ ပုံစံကို Singly Linked List လို့ ခေါ်ပါတယ်။ အရှေ့ကနေ အနောက်ကို သာ သွားလို့ ရပြီး၊ အနောက် ကို ပြန်သွား မရပါ။

public class LinkedListExample {
    public static void main(String[] args) {
        // Node တွေ တည်ဆောက်ခြင်း
        ListNode head = new ListNode(10);
        head.next = new ListNode(20);
        head.next.next = new ListNode(30);

        // အစကနေ အဆုံးထိ လှည့်ဖတ်ခြင်း (Traversal) - O(n)
        ListNode current = head;
        while (current != null) {
            System.out.println(current.val);
            current = current.next; // နောက် Node သို့ ရွှေ့သည်
        }
    }
}

Doubly Linked List

Doubly Linked List မှာတော့ Node တစ်ခုစီက နောက် Node (next) ကိုရော၊ ရှေ့ Node (prev) ကိုပါ ညွှန်ပြထားပါတယ်။ ဒါကြောင့် အရှေ့ကို ရော အနောက်ကို ရော (နှစ်လမ်းသွား) သွားလို့ ရပါတယ်။ Memory ပိုကုန်ပေမယ့် အနောက်ကို ပြန်လှည့်ဖို့ လွယ်ကူပါတယ်။

graph LR
    A[Node 1] <--> B[Node 2] <--> C[Node 3]

class DoublyNode {
    int val;
    DoublyNode prev;  // ရှေ့ Node
    DoublyNode next;  // နောက် Node

    DoublyNode(int val) {
        this.val = val;
    }
}

Doubly Linked List မှာ prev link ပါလာတဲ့အတွက် ထည့်/ဖျက်တဲ့အခါ pointer ၂ ဖက်စလုံး (ရှေ့ရော နောက်ရော) ကို ပြန်ချိတ်ပေးရပါတယ်။

// node အသစ်ကို existing node ရဲ့ နောက်မှာ ထည့်ခြင်း
newNode.prev = existing;
newNode.next = existing.next;
if (existing.next != null) {
    existing.next.prev = newNode; // နောက်က node ၏ prev ကို ပြန်ချိတ်
}
existing.next = newNode;

// node တစ်ခုကို ဖျက်ခြင်း (ရှေ့/နောက် ၂ ဖက်ကို တိုက်ရိုက် ဆက်ပေးနိုင်)
if (node.prev != null) node.prev.next = node.next;
if (node.next != null) node.next.prev = node.prev;

Singly Linked List နဲ့ မတူတာက — ဖျက်မယ့် node ရဲ့ ရှေ့က node ကို သီးခြား လိုက်ရှာစရာ မလိုဘဲ၊ node.prev ကနေ တန်းရတာပါ။ ဒါက LRU Cache လိုမျိုး node ကို မကြာခဏ ဖျက်/ရွှေ့ရတဲ့ နေရာတွေမှာ အသုံးဝင်ပါတယ်။

Insert / Delete by Pointer

Linked List ရဲ့ အကောင်းဆုံး အချက်ကတော့ Pointer ကို ပြောင်းရုံနဲ့ Node တစ်ခုကို ထည့်တာ၊ ဖျက်တာ လုပ်နိုင်တာပါ။ Array လို နောက်က Data တွေ ရွှေ့ပေးစရာ မလိုတော့ပါ။ (သိမ်းမယ့်နေရာကို သိပြီးသား ဆိုရင် $O(1)$ ဖြစ်ပါတယ်)။

graph LR
    A[Node A] --> C[Node C]
    A -. ၁။ A→New .-> N[New Node]
    N -. ၂။ New→C .-> C
    style N fill:#9f9,stroke:#333

// Node A နှင့် Node C ကြားထဲ Node အသစ်ထည့်ခြင်း
ListNode newNode = new ListNode(15);
newNode.next = nodeA.next; // အသစ်က C ကို ညွှန်စေသည်
nodeA.next = newNode;      // A က အသစ်ကို ညွှန်စေသည်

// Node တစ်ခုကို ဖျက်ခြင်း (A ၏ နောက်က Node ကို ဖျက်ရန်)
nodeA.next = nodeA.next.next; // A ကို ကျော်၍ နောက်တစ်ခုသို့ ညွှန်စေသည်

Array vs Linked List နှိုင်းယှဉ်ချက်

လုပ်ဆောင်ချက်	Array	Linked List
Index ဖြင့်ရှာခြင်း (Access)	$O(1)$	$O(n)$
ရှေ့ဆုံးတွင် ထည့်/ဖျက်	$O(n)$	$O(1)$
နောက်ဆုံးတွင် ထည့်	$O(1)$ *	$O(n)$ **
ရှာဖွေခြင်း (Search)	$O(n)$	$O(n)$
Memory	ကပ်လျက် (Contiguous)	ပြန့်ကျဲ (Pointer ပိုကုန်)

* Dynamic Array မှာ နေရာ ပြည့်သွားရင် အသစ် ချဲ့ရတဲ့အတွက် တစ်ခါတစ်ရံ $O(n)$ ဖြစ်နိုင်ပါတယ်။
** Tail Pointer သိမ်းထားရင် Linked List နောက်ဆုံးမှာ ထည့်တာ $O(1)$ ဖြစ်နိုင်ပါတယ်။

ဒီနှိုင်းယှဉ်ချက်ကို ကြည့်ရင် Index နဲ့ ရှာတာ များမယ်ဆိုရင် Array က ပိုသင့်တော်ပါတယ်။ ထည့်ဖျက်တာ များမယ်ဆိုရင် Linked List က ပိုကောင်းပေမယ့်၊ ဒါက ထည့်/ဖျက်ရမယ့် နေရာ (သို့) ရှေ့က node pointer ကို သိပြီးသား ဖြစ်မှသာ မှန်ပါတယ်။ နေရာကို အရင် လိုက်ရှာရဦးမယ်ဆိုရင်တော့ ရှာဖွေတာက $O(n)$ ကုန်တဲ့အတွက် Linked List ရဲ့ အားသာချက် ပျောက်သွားပါတယ်။

လက်တွေ့အသုံးချမှုများ

Music Playlist: သီချင်း တစ်ပုဒ်ပြီး တစ်ပုဒ် (Next) ဖွင့်တာ၊ ပြန်သွားတာ (Previous) တွေအတွက် Doubly Linked List က အသင့်တော်ဆုံးပါ။
Browser History: ရှေ့သွား/နောက်ပြန် လုပ်တဲ့အတွက်လည်း Doubly Linked List ကို သုံးနိုင်ပါတယ်။
LRU Cache: အကြာဆုံး မသုံးတော့တဲ့ (Least Recently Used) Data ကို ဖယ်ထုတ်တဲ့ Cache စနစ်မှာ Doubly Linked List နဲ့ Hash Table ကို ပေါင်းသုံးကြပါတယ်။ (Interview မှာ မကြာခဏ မေးတဲ့ "LRU Cache" ပုစ္ဆာက ဒီ DLL + HashMap ပေါင်းစပ်မှုနဲ့ get/put ၂ ခုလုံးကို $O(1)$ ရအောင် တည်ဆောက်ခိုင်းတာပါ။)
Undo/Redo: လုပ်ဆောင်ချက်တွေကို အစဉ်လိုက် ချိတ်ဆက် မှတ်သားရာမှာ သုံးပါတယ်။

မှတ်ချက်: နေ့စဉ် App ရေးတဲ့အခါ Linked List ကို တိုက်ရိုက် ကိုယ်တိုင် ရေးသုံးဖို့ နည်းပါတယ်။ ဒါပေမယ့် Pointer/Reference ဆိုတဲ့ စဉ်းစားနည်းဟာ Tree, Graph စတဲ့ နောက်ပိုင်း အခန်းတွေအတွက် အလွန် အရေးကြီးပါတယ်။

Questions

Linked List ကို နားလည်သွားပြီ ဆိုရင် လက်တွေ့ အသုံးချရမယ့် LeetCode ပုစ္ဆာ တချို့ကို ကြည့်ရအောင်။

Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

ဒီပုစ္ဆာက Linked List အတွက် အခြေခံ အကျဆုံး ပုစ္ဆာ ဖြစ်ပါတယ်။ Node တွေရဲ့ next Pointer တွေကို ပြောင်းပြန် လှည့်ပေးရမှာပါ။

အဓိက စဉ်းစားနည်းကတော့ Pointer ၃ ခု (prev, current, next) ကို သုံးပြီး၊ Node တစ်ခုစီရဲ့ next ကို သူ့ရဲ့ ရှေ့က Node (prev) ဆီ ပြန်လှည့်ညွှန်ပေးသွားတာပါ။

$O(n)$ time complexity, $O(1)$ space complexity ဖြစ်ရပါမယ်။

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;

        while (current != null) {
            ListNode next = current.next; // နောက် Node ကို ကြိုသိမ်းထားသည်
            current.next = prev;          // Pointer ကို ပြောင်းပြန် လှည့်သည်
            prev = current;               // prev ကို ရှေ့သို့ ရွှေ့သည်
            current = next;               // current ကို ရှေ့သို့ ရွှေ့သည်
        }

        return prev; // prev သည် နောက်ဆုံးတွင် Head အသစ် ဖြစ်သည်
    }
}

Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

စီပြီးသား (Sorted) Linked List နှစ်ခုကို ပေါင်းပြီး၊ စီပြီးသား List တစ်ခုတည်း ဖြစ်အောင် လုပ်ရမှာပါ။

Dummy Node ဆိုတဲ့ ခေါင်းစီး Node အတုတစ်ခုကို သုံးပြီး၊ List နှစ်ခုကို တစ်ပြိုင်တည်း လိုက်နှိုင်းကာ၊ တန်ဖိုး ငယ်တဲ့ Node ကို ရွေးပြီး ဆက်ချိတ်သွားတဲ့ နည်းက အရိုးရှင်းဆုံးပါ။

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // Dummy Node - ခေါင်းစီး အတု (ရှုပ်ထွေးမှု လျှော့ရန်)
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }

        // ကျန်နေသေးသော List ကို ဆက်ချိတ်သည်
        tail.next = (list1 != null) ? list1 : list2;

        return dummy.next; // Dummy ၏ နောက်က Node သည် တကယ့် Head ဖြစ်သည်
    }
}

Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if some node in the list can be reached again by continuously following the next pointer.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle, the tail connects to the 1st node (0-indexed).

Linked List ထဲမှာ စက်ဝိုင်း (Cycle) ရှိမရှိ စစ်ရမှာပါ။ Cycle ဆိုတာ Node တစ်ခုရဲ့ next က နောက်ပြန် တစ်ခုခုကို ညွှန်ပြီး အဆုံးမသတ် (Infinite Loop) ဖြစ်နေတာ မျိုးပါ။

ဒီပုစ္ဆာကို Floyd's Cycle Detection (Fast & Slow Pointers) နည်းနဲ့ ဖြေရှင်းပါတယ်။ နှေး (Slow) Pointer က တစ်လှမ်းစီ၊ မြန် (Fast) Pointer က နှစ်လှမ်းစီ သွားပါမယ်။ Cycle ရှိနေရင် မြန်တဲ့ Pointer က နှေးတဲ့ Pointer ကို တစ်နေရာရာမှာ ပြန်မီ (ထပ်) သွားပါလိမ့်မယ်။

ဒီနည်းကို "ပြေးခုန်ပစ်ကွင်း (Race Track)" မှာ မြန်တဲ့သူက နှေးတဲ့သူကို တစ်ပတ်ပြန်ကျော်ပြီး မီသွားသလို မြင်ယောင်နိုင်ပါတယ်။ $O(n)$ time, $O(1)$ space ဖြစ်ပါတယ်။

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;        // တစ်လှမ်းစီ
            fast = fast.next.next;   // နှစ်လှမ်းစီ

            if (slow == fast) {      // ပြန်ဆုံသွားလျှင် Cycle ရှိသည်
                return true;
            }
        }

        return false; // fast သည် null သို့ ရောက်လျှင် Cycle မရှိ
    }
}

Find Middle Node

Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.

Example 1:

Input: head = [1,2,3,4,5]
Output: [3,4,5]

Example 2:

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]

List ရဲ့ အလယ် Node ကို ရှာရမှာပါ။ ဒီနေရာမှာလည်း Fast & Slow Pointers နည်းကို သုံးနိုင်ပါတယ်။ Fast က နှစ်လှမ်းစီ၊ Slow က တစ်လှမ်းစီ သွားရင်၊ Fast က အဆုံးရောက်တဲ့အခါ Slow က အလယ်မှာ ရှိနေပါလိမ့်မယ်။

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        // Fast သည် အဆုံးရောက်သွားလျှင် Slow သည် အလယ်တွင် ရှိနေမည်
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }
}

Remove Nth Node From End of List

Given the head of a linked list, remove the $n^{th}$ node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

အဆုံးကနေ ရေတွက်လို့ n ခုမြောက် Node ကို ဖျက်ရမှာပါ။ List ကို တစ်ခေါက်ပဲ ဖတ်ပြီး (One Pass) ဖြေရှင်းဖို့ Pointer နှစ်ခုကြားမှာ n အကွာအဝေး ထားတဲ့ နည်း (Two Pointers) ကို သုံးပါမယ်။

ဒီ Solution မှာ Head ကိုယ်တိုင် ဖျက်ရတဲ့ ကိစ္စကို လွယ်ကူစေဖို့ dummy Node ကို head ရှေ့မှာ ထည့်ထားပြီး slow နဲ့ fast နှစ်ခုစလုံးကို dummy ကနေ စပါတယ်။ slow ကို ဖျက်မယ့် Node ရဲ့ ရှေ့ မှာ ရပ်စေချင်တဲ့အတွက်၊ fast ကို dummy ကနေ n + 1 လှမ်း ရှေ့သွားခိုင်းရပါမယ်။ ဒါမှ slow နဲ့ fast ကြားက အကွာအဝေးက n + 1 ဖြစ်ပြီး၊ fast က null ရောက်တဲ့အခါ slow က ဖျက်မယ့် Node ရဲ့ ရှေ့မှာ အတိအကျ ရှိနေမှာပါ။

မှတ်ချက်: dummy မသုံးဘဲ ဖြေချင်ရင် fast ကို head ကနေ n လှမ်းသာ ရှေ့သွားစေပြီး၊ Head ကိုယ်တိုင် ဖျက်ရတဲ့ အခြေအနေ (fast == null ဖြစ်သွားတာ) ကို သီးခြား စစ်ပေးရပါမယ်။ Dummy Node နည်းက ဒီ edge case ကို သပ်သပ်ရပ်ရပ် ဖြေရှင်းပေးတာ ဖြစ်ပါတယ်။

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // Head ကိုယ်တိုင် ဖျက်ရနိုင်သဖြင့် Dummy Node သုံးသည်
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode slow = dummy;
        ListNode fast = dummy;

        // fast ကို n+1 လှမ်း ရှေ့သွားစေသည်
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        // နှစ်ခုစလုံး အတူတူ ရွှေ့သည်၊ fast အဆုံးရောက်လျှင် ရပ်သည်
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // slow ၏ နောက်က Node ကို ကျော်၍ ဖျက်သည်
        slow.next = slow.next.next;

        return dummy.next;
    }
}