Doubly Linked List နဲ့ Python ရဲ့ deque

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

Singly linked list မှာ node တစ်ခုစီက next ကိုပဲ ညွှန်ပြတယ်၊ ဒါကြောင့် list ရဲ့ အဆုံးက element ကို ဖြုတ်ချင်ရင်တောင် head ကနေ traverse လုပ်ပြီး ရှေ့ node ကို ရှာနေရတယ် — O(n)။ Doubly linked list ကတော့ node တစ်ခုစီမှာ next အပြင် prev ကိုပါ ထည့်ညွှန်ပြထားလို့၊ node ဘယ်နေရာမှာရှိရှိ ဘေးက node ကို O(1) နဲ့ တိုက်ရိုက် ရောက်နိုင်တယ်၊ ဒါကြောင့် list ရဲ့ ရှေ့ဘက်ကနေရော နောက်ဘက်ကနေရော ဖြုတ်/ထည့် တာ O(1) ဖြစ်တယ်။ Python မှာ ဒီဖွဲ့စည်းပုံကို ကိုယ်တိုင် implement လုပ်ဖို့ မလိုပါဘူး — `collections.deque` (double-ended queue) ဟာ doubly linked list ကို base ခံပြီး ရေးထားတာဖြစ်လို့ `append`, `appendleft`, `pop`, `popleft` အားလုံးကို O(1) နဲ့ လုပ်ပေးတယ်။ ဒါကြောင့် ဘေးနှစ်ဖက်စလုံးက ဖြည့်/ဖြုတ်ဖို့ လိုအပ်တဲ့ queue, stack, sliding-window, recent-history ကဲ့သို့ use case တွေမှာ plain list ထက် deque က theoretically ပိုမှန်ကန်တဲ့ ရွေးချယ်မှုဖြစ်တယ်။

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

Tutorial Platform ရဲ့ 'Recently Viewed Lessons' panel ကို `deque` နဲ့ တည်ဆောက်နိုင်တယ် — user က lesson အသစ် ဖွင့်တိုင်း `appendleft()` နဲ့ ရှေ့ဆုံးမှာ ထည့်ပြီး၊ `maxlen` သတ်မှတ်ထားလို့ အဟောင်းဆုံး entry က အလိုအလျောက် ဘေးက ကျသွားတယ်၊ ဒါအားလုံး O(1)။

• Node တစ်ခုစီမှာ next အပြင် prev ပါ၀င်လို့ ဘယ်ဘက်/ညာဘက် နှစ်ဖက်စလုံး O(1) navigate လုပ်နိုင်တယ်
• Python ရဲ့ `deque` ဟာ doubly linked list ကို base ခံထားတာဖြစ်ပြီး နှစ်ဖက်စလုံးက append/pop က O(1)
• Plain list ရဲ့ `pop(0)` က element အားလုံး shift လုပ်ရလို့ O(n) ဖြစ်တယ်

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

from collections import deque

# deque is a doubly linked list under the hood, so both ends are O(1)
recent_lessons = deque(maxlen=3)

recent_lessons.append("intro")        # add to right end - O(1)
recent_lessons.append("variables")
recent_lessons.appendleft("welcome")  # add to left end - O(1), no shifting
print(list(recent_lessons))

recent_lessons.pop()      # remove from right end - O(1)
recent_lessons.popleft()  # remove from left end - O(1)
print(list(recent_lessons))

# Contrast: a plain list's pop(0) is O(n) because every remaining
# element must shift left by one to fill the gap.

ပထမဆုံး print က `['welcome', 'intro', 'variables']` ကို ပြပြီး၊ pop() နဲ့ popleft() နှစ်ခု ခေါ်ပြီးနောက် ဒုတိယ print က `['intro']` ကို ပြတယ်။

Python Docs — collections.deque — Data Structures & Algorithms