Linked List — Node များချိတ်ဆက်ထားသော ဒေတာဖွဲ့စည်းပုံ

နားလည်ထားရမယ့် အချက်

Array တစ်ခုက value တွေကို memory ထဲမှာ ဆက်တိုက် (contiguous) သိမ်းထားပြီး index ကနေ တန်ဖိုးကို တိုက်ရိုက် O(1) မှာ ရှာနိုင်ပေမယ့်၊ အလယ်က element တစ်ခုကို ဖြုတ်ချင်ရင် နောက်က element အားလုံးကို shift ချရတာကြောင့် O(n) ဖြစ်တယ်။ Linked list ကတော့ ဒီပြဿနာကို ဖြေရှင်းတယ် — data တစ်ခုစီကို node အနေနဲ့ သီးခြားစီ allocate လုပ်ပြီး၊ node တစ်ခုစီမှာ value နဲ့ next node ကို ညွှန်ပြတဲ့ pointer ပါတယ်။ Head ရဲ့ ရှေ့ကို node အသစ်တစ်ခု ထည့်ချင်ရင် pointer နှစ်ခုကို ပြင်လိုက်ရုံပဲ (O(1)) — shift လုပ်စရာမလိုဘူး။ ဒါပေမယ့် ဒီ flexibility ကို ရဖို့ ဈေးနှုန်းတစ်ခု ပေးရတယ်။ n ခြမ်းမြောက် node ကို ရှာချင်ရင် index ကနေ တိုက်ရိုက် ခုန်လို့မရဘူး၊ head ကနေ pointer တစ်ခုချင်းစီ လိုက်လျှောက်ရမှာဖြစ်လို့ O(n) ဖြစ်တယ်။ ဒါကြောင့် linked list ရွေးမလား array ရွေးမလားဆိုတာ access pattern ပေါ်မူတည်တယ် — random access များရင် array၊ head ကပဲ အမြဲ ဖြည့်/ဖြုတ် လုပ်ရင် linked list ပိုသင့်တော်တယ်။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

Tutorial Platform ရဲ့ lesson navigation ဟာ linked list ပုံစံနဲ့ ကိုက်ညီတယ် — course တစ်ခုအတွင်းက lesson တစ်ခုစီမှာ 'နောက်လက်ခန်း' ကို ညွှန်ပြတဲ့ pointer ပါတယ်၊ user က 'Next Lesson' နှိပ်တိုင်း O(1) နဲ့ ရွှေ့နိုင်တယ်။ Course editor က lesson အသစ်တစ်ခုကို အစောပိုင်းမှာ ထည့်ချင်ရင်လည်း lesson list တစ်ခုလုံး re-index လုပ်စရာမလိုဘဲ pointer နှစ်ခုပဲ ပြင်ရုံနဲ့ ပြီးတယ်။

• Node တစ်ခုစီမှာ value နဲ့ next pointer ပါ၀င်တယ်
• Head မှာ insert/delete လုပ်တာ O(1) — shift မလိုဘူး
• N ခြမ်းမြောက် node ကို ရောက်ဖို့ head ကနေ လိုက်လျှောက်ရလို့ O(n)

အတူတူ စမ်းရေးကြည့်မယ်

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_head(self, value):
        # O(1): just relink the head pointer, no shifting needed
        self.head = Node(value, self.head)

    def print_list(self):
        # O(n): must walk pointer by pointer from the head
        current = self.head
        items = []
        while current:
            items.append(str(current.value))
            current = current.next
        print(" -> ".join(items))

ll = LinkedList()
for lesson in ["intro", "variables", "loops"]:
    ll.insert_at_head(lesson)
ll.print_list()

'loops -> variables -> intro' ဟု print ထုတ်ပေးတယ်၊ head မှာ insert လုပ်တိုင်း အနောက်ဆုံးထည့်ခဲ့တဲ့ lesson က အရင်ဆုံး ပေါ်လာလို့ဖြစ်တယ်။

Wikipedia — Linked list — Data Structures & Algorithms