Implementing an Unordered List: Linked Lists

Unordered List ကို ပံုမွန္အားျဖင့္ linked list လို႔ ေခၚၾကပါတယ္။ Value ေတြ ဟာ ေနရာ အတည္အက်မဟုတ္ပဲ ေနရာစံုေတြမွာ ရွိေနပါတယ္။ item တစ္ခုက ေနာက္ထပ္ iteam တစ္ခုကို ထပ္ၿပီး ၫႊန္းထားပါတယ္။ ဥပမာ ေအာက္က ပံုကို ၾကည့္လိုက္ပါ။

img

linked

နံပတ္ေတြဟာ အစီအစဥ္အတိုင္း မဟုတ္ပဲ ခ်ိတ္ဆက္ထားတာကို ေတြ႕ႏိုင္တယ္။ ဒါဆိုရင္ class တစ္ခုမွာ လက္ရွိ value နဲ႔ ေနာက္ထပ္ value တစ္ခု ကို တြဲၿပီး သိမ္းဖို႔ လိုတယ္။ ေနာက္ထပ္ value ကလည္း value နဲ႔ next ကို သိမ္းဖို႔ လိုတယ္။ တနည္းေျပာရင္ node ေလးေတြ ဆက္ထားတာပဲ။

အဲဒီ အတြက္ ကၽြန္ေတာ္တို႔ေတြ Node class တစ္ခု တည္ေဆာက္ဖို႔ လိုလာၿပီ။

class Node: def __init__(self,init_data) : self.data = init_data self.next = None def get_data(self): return self.data def get_next(self): return self.next def set_data(self,new_data) : self.data = new_data def set_next(self, new_next) : self.next = new_next

Class ေလးကေတာ့ ရွင္းရွင္းေလးပါပဲ။ လက္ရွိ ရွိေနသည့္ data ကို store လုပ္ထားမယ္။ next data ကို မွတ္ထားမယ္။

code ေလးကို အရင္ဆံုး အလုပ္လုပ္လား စမ္းၾကည့္ရေအာင္။

from node import Node temp = Node(93) print(temp.get_data())

အခု Node တစ္ခု ရၿပီ။ အဲဒီေတာ့ Unordered List Class ကို ေဆာက္ၾကမယ္။ Node ထဲမွာ value သိမ္းမယ္။ Node ရဲ႕ next value က ေနာက္ထပ္ node တစ္ခုကို ခ်ိတ္ထားမယ္။ ဒါဆိုရင္ ကၽြန္ေတာ္တို႔ေတြ Linked List တစ္ခု ဖန္တီးႏိုင္ၿပီ။

Unordered List Class

Unordered List ကို Node နဲ႔ ဖန္တီးၿပီးေတာ့ တစ္ခုျခင္းစီကို ခ်ိတ္ဆက္သြားရံုပဲ။ ပံုေလးနဲ႔ စဥ္းစားၾကည့္ရင္ ေအာက္ကလို ပံုေလးပဲ။

img

List ကသာ empty ျဖစ္ေနရင္ head က end ႏွင့္ ခ်ိတ္ထားပါလိမ့္မယ္။

img

မဟုတ္ဘူးဆိုရင္ေတာ့ head က လက္ရွိ ေရွ႕ဆံုး node ကို ၫႊန္ထားမယ္။ ေရွ႕ node ရဲ႕ value က 1 ျဖစ္ၿပီးေတာ့ next ကိုေတာ့ ေနာက္ ထပ္ node တစ္ခု နဲ႔ ထပ္ၿပီးေတာ့ ၫႊန္ထားတယ္။ ဒီပံုကို ျမင့္ေတာ့ ကၽြန္ေတာ္တို႔ေတြ ဘာျဖစ္လို႔ node class ကို ေဆာက္ခဲ့သလည္းဆိုတာကို သေဘာေပါက္ေလာက္ပါၿပီ။ အခု unorder list ဖန္တီးၾကည့္ရေအာင္။

from node import Node class UnorderedList: def __init__(self): self.head = None mylist = UnorderedList()

ဒါကေတာ့ အ႐ိုးအရွင္းဆံုး ဦးစြာ class တစ္ခု ဖန္တီးလိုက္တာေပါ့။ head ထဲမွာ None ကိုထည့္ထားတယ္။ ဘာျဖစ္လို႔လည္းဆိုေတာ့ object ကို ေဆာက္လိုက္တာနဲ႔ empty list တစ္ခုကို ဖန္တီးျခင္လို႔ပါ။

Empty

ကၽြန္ေတာ္တို႔ေတြ List ကို empty ျဖစ္မျဖစ္ စစ္ဖို႔ အတြက္ function တစ္ခု ဖန္တီး ရေအာင္။ function ကလည္း လြယ္ပါတယ္။ head ကသာ None ျဖစ္ေနရင္ List က empty ျဖစ္ေနတယ္ဆိုတဲ့ အဓိပၸာယ္ပါပဲ။

def is_empty(self):
    return self.head == None

from node import Node class UnorderedList: def __init__(self): self.head = None def is_empty(self): return self.head == None mylist = UnorderedList() print(mylist.is_empty())

႐ိုး႐ိုးေလးပါပဲ။ အခု ေနာက္တစ္ဆင့္ သြားရေအာင္။

Add

အခု အဆင့္မွာေတာ့ add function ကို ဖန္တီးၾကမယ္။

mylist. = UnorderedList()
mylist.add(3)
mylist.add(31)
mylist.add(71)
mylist.add(10)
mylist.add(5)
mylist.add(1)

ဆိုရင္ list က ေအာက္က ပံုလို ေပၚဖို႔လိုပါတယ္။

img

အသစ္ထပ္ျဖည့္လိုက္တိုင္း အေနာက္ကို ေရာက္ေရာက္သြားမယ္။

ပထမဆံုး အႀကိမ္မွာ 3 ပဲ ရွိတယ္။ 31 ထပ္ျဖည့္ေတာ့ 31,3 ျဖစ္သြားတယ္။ 71 ထပ္ျဖည့္ေတာ့ 71,3,1,3 ျဖစ္သြားတယ္။ အဲဒီ အတြက္ ကၽြန္ေတာ္တို႔ေတြ function တစ္ခု ေရးဖို႔ စဥ္းစားရေအာင္။

ဘယ္လို ေရးရင္ ရမလဲ။ မေရးခင္ အရင္ ဆံုး စဥ္းစားၾကည့္ဖို႔ လိုပါတယ္။

variable တစ္ခု ထည့္လိုက္မယ္။

ကၽြန္ေတာ္တို႔ Node object တစ္ခု ေဆာက္ရမယ္။ အဲဒီ ထဲကို ေပးလိုက္သည့္ variable ထည့္မယ္။

လက္ရွိ ရွိေနသည့္ head ကို ထည့္မယ္ Node ရဲ႕ next ထဲမွာ ထည့္လိုက္မယ္။

list ရဲ႕ head ကို temp မွာထည့္မယ္။ အဲဒါဆိုရင္ ရၿပီ။

code မေရးခင္မွာ တစ္ဆင့္ျခင္းဆီ စဥ္းစားၿပီး ေရးသည့္ အခါမွာ အမွားျပန္ျပင္ရတာ ပိုၿပီး လြယ္သလို အမွားလည္း နည္းလာႏိုင္သည့္ အတြက္ programming စေလ့လာကာစ လူေတြ အေနနဲ႔ အဆင့္တိုင္း စဥ္းစားသြားဖို႔ လိုပါတယ္။

ကဲ အခု ကၽြန္ေတာ္တို႔ေတြ add function ေရးၾကည့္ရေအာင္။

def add(self,item):
    temp = Node(item)
    temp.set_next(self.head)
    self.head = temp

from node import Node class UnorderedList: def __init__(self): self.head = None def is_empty(self): return self.head == None def add(self,item): temp = Node(item) temp.set_next(self.head) self.head = temp mylist = UnorderedList() mylist.add(3) mylist.add(31) mylist.add(71) mylist.add(10) mylist.add(5) mylist.add(1)

code ကို မရွင္းဖူး ဆိုရင္ ေအာက္က အဆင့္ေလးေတြကို ၾကည့္ၾကည့္ပါ။

၁။ အရင္ဆံုး list head မွာ None ရွိတယ္။

၂။ 3 ကို ထည့္လိုက္ေတာ့ , temp = Node(3) ဆိုၿပီး temp object ကို ေဆာက္လိုက္တယ္။ အဲဒီ အခ်ိန္မွာ temp ရဲ႕ data က 3 ျဖစ္ၿပီးေတာ့ next ကေတာ့ None ျဖစ္ေနမယ္။

၃။ temp.set_next(self.head) လို႔ ဆိုသည့္အတြက္ temp ရဲ႕ next ထဲမွာ လက္ရွိ head ကို ဝင္သြားၿပီ။ head က None ျဖစ္သည့္အတြက္ next ကလည္း None ျဖစ္ေနမွာပဲ။

၄။ self.head ကို temp ထည့္လိုက္သည့္အတြက္ေၾကာင့္ self.head က Node(3) ျဖစ္သြားၿပီ။

၅။ 31 ကို ထပ္ျဖည့္ေတာ့လည္း ဒီအတိုင္းပဲ။ သို႔ေပမယ့္ temp.set_next(self.head) ေၾကာင့္ Node(31) ရဲ႕ next က ၿပီးခဲ့ Node(3) ျဖစ္သြားတယ္။

၆။ self.head က Node(31) ျဖစ္သြားတာေၾကာင့္ self.head ထဲမွာ Node(31)->Node(3) ဆိုၿပီး ျဖစ္သြားပါၿပီ။

ဒါဆိုရင္ေတာ့ Add လုပ္သည့္ ကိစၥကို နားလည္ေလာက္ၿပီ။ အခု size (အေရအတြက္) ဘယ္ေလာက္ရွိလဲ ဆိုတာကို သိရေအာင္ function ေရးၾကည့္ရေအာင္။

Size

အခု self.head ထဲမွာ Node ေတြ အမ်ားႀကီးရွိေနၿပီ။ Size ကို သိဖို႔ကေတာ့ Node အေရအတြက္ ဘယ္ေလာက္ ရွိလဲ ဆိုတာ သိဖို႔လိုတယ္။ Node ေတြက တစ္ခုနဲ႔ တစ္ခုခ်ိတ္ထားၿပီးေတာ့ ေနာက္ဆံုး next က None ျဖစ္သြားသည့္ အထိပဲ။

Pseudo code ေလးနဲ႔ စဥ္းစားၾကည့္ရေအာင္။

Set current is head
Set count is zero
Loop Until current is None
    Increase count
    current = current.get_next()
Return count

Pseudo code အရ ဆိုရင္ current ထဲမွာ head ကို ထည့္မယ္။ ၿပီးရင္ count ကို သုညကေန စမွတ္မယ္။ current ကို None မျဖစ္မျခင္း loop ပတ္မယ္။ loop ထဲေရာက္တိုင္း count ကို ၁ တိုးသြားမယ္။ ၿပီးရင္ current ကို လက္ရွိ current ရဲ႕ next ကို ထည့္္မယ္။ loop က ထြက္သြားရင္ count ကို return ျပန္ေပးမယ္။ code ေလးက ရွင္းရွင္းေလးပါ။ အဲဒါကို python နဲ႔ ေျပာင္းေရးၾကည့္ရေအာင္။

def size(self):
    current = self.head
    count = 0
    while current != None:
        count = count + 1
        current = current.get_next()
    return count

from node import Node class UnorderedList: def __init__(self): self.head = None def is_empty(self): return self.head == None def add(self,item): temp = Node(item) temp.set_next(self.head) self.head = temp def size(self): current = self.head count = 0 while current != None: count = count + 1 current = current.get_next() return count mylist = UnorderedList() print(mylist.size()) mylist.add(3) mylist.add(31) mylist.add(71) mylist.add(10) mylist.add(5) mylist.add(1) print(mylist.size())

တကယ့္ကို လြယ္လြယ္ေလးပါ။ အခု ကၽြန္ေတာ္တို႔ေတြ ရွိသမွ် node ေတြ ကုန္ေအာင္ loop ပတ္လို႔ ရသြားၿပီ။ ဒါဆိုရင္ search လုပ္လို႔ ရၿပီေပါ့။

Search လုပ္မယ္ဆိုရင္ ၿပီးခဲ့တဲ့ size အတိုင္း loop ပတ္ဖို႔ လိုတယ္။ ေတြ႕ခဲ့ရင္ loop ထဲက ထြက္မယ္။ ဒါပဲ ကြာလိမ့္မယ္။

def search(self,item):
    current = self.head
    found = False
    while current != None and not found:
        if current.get_data() == item:
            found = True
        else:
            current = current.get_next()
    return found

from node import Node class UnorderedList: def __init__(self): self.head = None def is_empty(self): return self.head == None def add(self,item): temp = Node(item) temp.set_next(self.head) self.head = temp def size(self): current = self.head count = 0 while current != None: count = count + 1 current = current.get_next() return count def search(self,item): current = self.head found = False while current != None and not found: if current.get_data() == item: found = True else: current = current.get_next() return found mylist = UnorderedList() mylist.add(3) mylist.add(31) mylist.add(71) mylist.add(10) mylist.add(5) mylist.add(1) print(mylist.search(10)) print(mylist.search(12))

size ကို နားလည္တယ္ဆိုရင္ search code ကလည္း ႐ိုးရွင္းပါတယ္။ current က None ေရာက္သည့္အထိ loop ပတ္တယ္။ loop ထဲက ဘယ္အခ်ိန္ထြက္မလဲဆိုေတာ့ current က None ျဖစ္သြားခ်ိန္ ဒါမွမဟုတ္ found က true ျဖစ္သြားခ်ိန္ေပါ့။

while current != None and not found:

ဒီ code မွာ and ကို အသံုးျပဳထားတာ ေတြ႕ႏိုင္ပါတယ္။ and ရဲ႕ သေဘာက တစ္ခု False ျဖစ္ရင္ အကုန္ false ပဲ။ ၂ ခု လံုး true ျဖစ္မွ true ျဖစ္သည့္ သေဘာကို သိၾကပါလိမ့္မယ္။ code အရ current != None ကလည္း True ျဖစ္ရမယ္။ not found ဆိုသည့္ အတြက္ found ကလည္း false ျဖစ္ရမယ္။ found က false ျဖစ္မွသာ not false ဆိုၿပီး true ကို ရမွာပါ။ ၂ ခုလံုး true ျဖစ္ေနသ၍ looping က အလုပ္လုပ္ေနပါမယ္။

ကိုယ္ရွာေနသည့္ item ကိုသာ ေတြ႕ရင္ found က true ျဖစ္သြားၿပီးေတာ့ looping ထဲကေန ထြက္သြားပါလိမ့္မယ္။

Remove

အခု remove အပိုင္းကို စဥ္းစားၾကရေအာင္။ item တစ္ခုေပးလိုက္မယ္။ အဲဒီ item ကို ဖ်က္ဖို႔ လိုတယ္။ သူ႔ရဲ႕ အေရွ႕က သူ႔ကို ခ်ိတ္ထားသည့္ Node နဲ႔ သူ႔ရဲ႕ အေနာက္က သူ႔ကို ခ်ိတ္ထားသည့္ Node ၂ ခုကို ခ်ိတ္ေပးဖို႔လိုတယ္။ သူကေတာ့ နည္းနည္း ရႈပ္သြားၿပီ။

ကၽြန္ေတာ္တို႔မွာ

head -> 31 -> 10 -> 8 -> 4 -> 3 -> None

ဆိုၿပီးရွိရင္ 8 ကို remove လုပ္လိုက္ရင္ ေအာက္ကလို ျဖစ္သြားမယ္။

head -> 31 -> 10 -> 4 -> 3 -> None

အဲဒီေတာ့ ကၽြန္ေတာ္တို႔ 8 ကို ဖ်က္ဖို႔ အတြက္ 8 ေရွ႕ ရဲ႕က Node ကို မွတ္ထားမယ္။ အေပၚက ပံုအတိုင္း ဆိုရင္ေတာ့ 10 ေပါ့။ Node(10) ရဲ႕ next ကို Node(8) အစား Node(4) ခ်ိတ္ေပးလိုက္ရံုပဲ။ Node(4) ဆိုတာကေတာ့ Node(8) ရဲ႕ next ပါ။

ဒီေတာ့ Pseudo code ေလး ေရးၾကည့္ရေအာင္။

SET current = head
SET previous = None
SET found = false
Loop Until found OR current is None
    IF current.data == item THEN
        found = true
    ELSE
        previous = current
        current = current.next
IF found == true THEN
    IF previous == None THEN
        head = current.next
    ELSE
        previous.next = current.next

ကၽြန္ေတာ္တို႔ေတြဟာ အရင္ အတိုင္း loop ကို current ဟာ None ျဖစ္ေနသည့္ အခ်ိန္ သို႔မဟုတ္ not found ျဖစ္သြားသည့္အခ်ိန္ ထိ loop ပတ္ဖို႔ လိုပါတယ္။ အကယ္၍ ရွာေတြ႕ခဲ့ရင္ ျဖစ္ႏိုင္ေျခ ၂ ခု ရွိတယ္။ ပထမ အခန္းျဖစ္ႏိုင္တာ ရယ္ သို႔မဟုတ္ ပထမ အခန္း မဟုတ္တာရင္။ ပထမ အခန္းဆိုရင္ေတာ့ previous က None ျဖစ္ေနမွာပါ။ အဲဒီ အခါမွာ head ကို next နဲ႔ ခ်ိတ္ေပးလိုက္ရံုပဲ မဟုတ္ရင္ေတာ့ previous ရဲ႕ next ကို current ရဲ႕ next နဲ႔ ခ်ိတ္ေပးဖို႔ လိုပါတယ္။

python နဲ႔ ေရးၾကည့္ရေအာင္။

def remove(self,item) :
    current = self.head
    previous = None
    found = False
    while current != None and not found:
        if current.get_data() == item:
            found = True``````````````````
        else:
            previous = current
            current = current.get_next()
    if found :
        if previous == None:
            self.head = current.get_next()
        else:
            previous.set_next(current.get_next())

from node import Node class UnorderedList: def __init__(self): self.head = None def is_empty(self): return self.head == None def add(self,item): temp = Node(item) temp.set_next(self.head) self.head = temp def size(self): current = self.head count = 0 while current != None: count = count + 1 current = current.get_next() return count def search(self,item): current = self.head found = False while current != None and not found: if current.get_data() == item: found = True else: current = current.get_next() return found def remove(self,item) : current = self.head previous = None found = False while current != None and not found: if current.get_data() == item: found = True else: previous = current current = current.get_next() if found : if previous == None: self.head = current.get_next() else: previous.set_next(current.get_next()) mylist = UnorderedList() mylist.add(3) mylist.add(31) mylist.add(71) mylist.add(10) mylist.add(5) mylist.add(1) print(mylist.size()) mylist.remove(5) print(mylist.size()) mylist.remove(100) print(mylist.size())

python code ေလးကလည္း ႐ိုးရွင္းပါတယ္။ အခုဆိုရင္ေတာ့ ကၽြန္ေတာ္တို႔ေတြ remove အပိုင္း ၿပီးသြားပါၿပီ။

က်န္တဲ့ append,insert,index,pop စတာေတြကိုေတာ့ ေလ့က်င့္ခန္း အေနနဲ႔ ကိုယ္တိုင္ ေရးဖို႔ လိုအပ္ပါတယ္။

results matching ""

    No results matching ""