Implementing an Ordered List: Linked Lists

Unordered List ကို ဖန္တီးထားၿပီးၿပီ ဆိုေတာ့ ကၽြန္ေတာ္တို႔ေတြ အတြက္ Ordered List ဖန္တီးဖို႔ မခက္ခဲေတာ့ပါဘူး။ Ordered List ကေတာ့ နံပတ္ေတြကို အစီအစဥ္လိုက္ စီထားသည့္ list ပါ။ Unordered List မွာကေတာ့ နံပတ္စဥ္ေတြ အတိုင္း list ထဲမွာ ရွိေနတာ မဟုတ္ပါဘူး။ ဒါေၾကာင့္ မတူညီတာကေတာ့ list ထဲကို item ထည့္ေတာ့မယ္ဆိုရင္ ထည့္မယ့္ value ထက္ ႀကီးတာကို သြားရွာရမယ္။ သူ႔ရဲ႕ အေရွ႕မွာ သြားထည့္ရမယ္။ Unordered List လိုမ်ဳိး ထည့္ခ်င္သလို ထည့္လို႔ရတာ မဟုတ္ပါဘူး။

Ordered List ပံုစံကို ၾကည့္ရေအာင္

Ordered

Unordered List နဲ႔ ဆင္သေယာက္ပါပဲ။ ကြာတာကေတာ့ သူက ႀကီးစဥ္ငယ္လိုက္ အစီအစဥ္လိုက္ စီထားတာပါ။

အခု Class တစ္ခု ကို ဖန္တီးၾကည့္ရေအာင္

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

ဒါကေတာ့ အရင္အတိုင္းပဲ။ ပံုမွန္ class တစ္ခု ဖန္တီးထားတာပါ။

Unordered List အေၾကာင္းသိၿပီးၿပီ ျဖစ္သည့္ အတြက္ ကၽြန္ေတာ္တို႔ေတြ add ကို ေနာက္မွ ေရးမယ္။ အခု search ေလးက စလိုက္ရေအာင္။

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

code ဖတ္လိုက္တာနဲ႔ အခုဆို နားလည္ေလာက္ၿပီလို႔ ထင္ပါတယ္။ Search လုပ္တယ္ ၊ ရွာတယ္ ဆိုသည့္ သေဘာကေတာ့ ရွင္းရွင္းေလးပါ။ တစ္ခန္းျခင္းစီမွာ ဒီ value ဟုတ္လား ၊ မဟုတ္ခဲ့ရင္ value က အခု လက္ရွိ အခန္းထက္ ႀကီးေနလားဆိုၿပီး စစ္ပါတယ္။ ဘာလို႔ စစ္ရလဲ ဆိုေတာ့ ဂဏန္းေတြက ႀကီးစဥ္ငယ္လိုက္ ရွိေနေတာ့ ႀကီးသြားရင္ေတာ့ ေသခ်ာၿပီ ေနာက္ဘက္အခန္းေတြမွာ လည္း မရွိေတာ့ဘူး။ အကယ္၍ မရွိခဲ့ဘူး ဆိုရင္ေတာ့ ေနာက္အခန္းကို ဆက္သြားၿပီး ရွာဖို႔ လိုပါလိမ့္မယ္။

ဘာေၾကာင့္ Search ကို အဓိက ထားၿပီး အရင္ေျပာရသလဲ ဆိုေတာ့ Search ပိုင္းနားလည္ သေဘာေပါက္မွ Ordered List မွာ Add အပိုင္း ထည့္လို႔ ရပါလိမ့္မယ္။ Ordered List က ထည္မယ္ဆိုရင္ ထည့္မယ္ value ထက္ ႀကီးထက္တာကို ရွာရမယ္။ ၿပီးရင္ အဲဒီ အေရွ႕မွာ ထည့္ဖို႔ လိုပါတယ္။

def add(self, item):
   current = self.head
   previous = None
   stop = False
   while current != None and not stop:
      if current.get_data() > item:
         stop = True
      else:
         previous = current
         current = current.get_next()
   temp = Node(item)
   if previous == None:
      temp.set_next(self.head)
      self.head = temp
   else:
      temp.set_next(current)
      previous.set_next(temp)

အခု add function ကို ေရးၿပီးပါၿပီ။ code ေလး တခ်က္ေလာက္ ၾကည့္ရေအာင္။ Search မွာကေတာ့ found ဆိုၿပီး အသံုးျပဳထားၿပီးေတာ့ add မွာကေတာ့ previous ကို အသံုးျပဳထားပါတယ္။ အခု လက္ရွိ အခန္းမတိုင္ခင္က အခန္းေပါ့။ ဒါမွသာ ကၽြန္ေတာ္တို႔ေတြဟာ လက္ရွိ အခန္းနဲ႔ သူ႔ရဲ႕ ၿပီးခဲ့တဲ့ အခန္းၾကားမွာ value ကို ထည့္လိုက္ရင္ ရပါၿပီ။

Search အတိုင္းပါပဲ။ ကၽြန္ေတာ္တို႔ေတြဟာ Loop ပတ္ၿပီးေတာ့ ထည့္မယ္ item ထက္ႀကီးတာကို ရွာတယ္။ ေနာက္ဆံုး အခန္း မေရာက္မျခင္း ရွာပါတယ္။ ဒါမွမဟုတ္ current item က လက္ရွိ item ထက္ႀကီးသြားမလားဆိုၿပီးေတာ့လည္း ရွာပါတယ္။ မႀကီးဘူးဆိုရင္ေတာ့ previous ထဲမွာ current ကို ထည့္တယ္။ current ကိုေတာ့ current ရဲ႕ next ကို ထည့္ပါတယ္။

ၿပီးသြားၿပီဆိုရင္ ေနာက္ဆံုး အခန္းေရာက္သြားလား သိရင္ေအာင္

if previous == None:

ဆိုၿပီးရွာပါတယ္။ ေနာက္ဆုံုး အခန္းဆိုရင္ေတာ့ ေနာက္ဆံုး အခန္းမွာ ထည့္လိုက္ရံုပဲေပါ့။

မဟုတ္ခဲ့ဘူးဆိုရင္ေတာ့ item ရဲ႕ next ကို current ထည့္မယ္။ previous ရဲ႕ next ကိုေတာ့ item ရဲ႕ Node ေလး ခ်ိတ္ေပးလိုက္ရံုပါပဲ။ Code က လြယ္လြယ္ နဲ႔ ႐ိုး႐ိုး ရွင္းရွင္းပါပဲ။ ကၽြန္ေတာ္ အဓိက Search ရဲ႕ Add ပဲ ေျပာသြားတယ္။ က်န္တာေတြကို Unordered List နဲ႔ ေပါင္းလို႔ ရတယ္။

Unordered List မွာ exercise လုပ္ျဖစ္သည့္သူေတြ အေနနဲ႔ pop အပိုင္းကို စဥ္းစားဖူးပါလိမ့္မယ္။

pop ကို ေရးသားဖို႔အတြက္ စဥ္းစားၾကည့္ရေအာင္။

  • ပထမဆံုး စဥ္းစားရမွာက ေနာက္ဆံုး အခန္းကို ဘယ္လိုသြားမလဲ ?
  • ေနာက္ဆံုး အခန္းကို ဘယ္လို ဖ်က္မလဲ

ကၽြန္ေတာ္တို႔ အရင္က ေရးထားသလိုပါပဲ။ ေနာက္ဆံုး အခန္းက None ျဖစ္တယ္။ ဒါဆိုရင္ေတာ့ လက္ရွိ Node ရဲ႕ next value ကသာ None ျဖစ္သြားခဲ့ရင္ အဲဒါက ေနာက္ဆံုး အခန္းပဲ။ ဒီေတာ့ current ရဲ႕ next က None မျဖစ္မျခင္း Loop ပတ္ဖို႔ လိုတယ္။

while current.get_next() != None :

ေနာက္တစ္ခုက ေနာက္ဆံုးခန္း ဘယ္လိုဖ်က္မလဲ ဆိုတာက လြယ္သြားၿပီ။ လက္ရွိ current ရဲ႕ ေရွ႕ အခန္းမွာ next ကို None ေပးလိုက္ရံုပါပဲ။

Code အျပည့္အစံုကို ၾကည့္ရေအာင္

def pop(self) :
        current = self.head
        previous = None
        while current.get_next() != None :
            previous = current
            current = current.get_next()

        previous.set_next(None)
        return current.get_data()

ကဲ အခု ကၽြန္ေတာ္တို႔ Ordered List class တစ္ခု လံုး စမ္းၾကည့္ရေအာင္။

from node import Node class OrderedList: def __init__(self): self.head = None def is_empty(self): return self.head == None def add(self, item): current = self.head previous = None stop = False while current != None and not stop: if current.get_data() > item: stop = True else: previous = current current = current.get_next() temp = Node(item) if previous == None: temp.set_next(self.head) self.head = temp else: temp.set_next(current) previous.set_next(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 stop = False while current != None and not found and not stop: if current.get_data() == item: found = True else: if current.get_data() > item: stop = 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()) def pop(self) : current = self.head previous = None while current.get_next() != None : previous = current current = current.get_next() previous.set_next(None) return current.get_data() mylist = OrderedList() 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()) print(mylist.pop()) print(mylist.size())

results matching ""

    No results matching ""