Ordered Linked Lists (တန်ဖိုးအလိုက် အစဉ်တကျ စီထားတဲ့ linked list များ)

B4.1.3 (HL): Construct and apply linked lists: singly linked (insertion, deletion, traversal, search). This page focuses on maintaining sorted order.
မြန်မာလို: linked list (node တွေ ချိတ်ဆက်ထားတဲ့ list) တွေကို ကိုယ်တိုင် တည်ဆောက်ပြီး အသုံးချနိုင်ရပါမယ်: singly linked list (တစ်ဘက်တည်း ချိတ်ဆက်ထားတဲ့ linked list) မှာ insertion (ထည့်ခြင်း)၊ deletion (ဖျက်ခြင်း)၊ traversal (node တိုင်းကို အစဉ်တကျ သွားကြည့်ခြင်း) နဲ့ search (ရှာခြင်း) တို့ပါ။ ဒီစာမျက်နှာက list ကို အစဉ်တကျ စီထားတဲ့ အတိုင်း ထိန်းထားခြင်းကို အဓိက လေ့လာပါတယ်။

ဒီစာမျက်နှာက HL အတွက်ပဲ ဖြစ်ပါတယ်။ SL (Standard Level) နဲ့ HL (Higher Level) ဆိုတာ IB Computer Science (နိုင်ငံတကာ ကျောင်းတွေမှာ သင်တဲ့ ကွန်ပျူတာသိပ္ပံ သင်ရိုး) သင်တန်းရဲ့ အဆင့်နှစ်ဆင့်ဖြစ်ပြီး HL အပိုင်းတွေက ပိုနက်နက်ရှိုင်းရှိုင်း လေ့လာရတဲ့ အပိုင်းတွေပါ။

---

အဓိက အယူအဆများ

Ordered linked list (sorted linked list လို့လည်း ခေါ်ပါတယ်) ဆိုတာ node (ဒေတာ သိမ်းထားတဲ့ အကွက်) တွေကို သူတို့ရဲ့ ဒေတာ တန်ဖိုးအလိုက် ascending order (ငယ်ရာကနေ ကြီးရာ) ဒါမှမဟုတ် descending order (ကြီးရာကနေ ငယ်ရာ) အတိုင်း အမြဲ စီထားတဲ့ singly linked list ပါ။ ပုံမှန် linked list မှာ item (အချက်) အသစ်တွေကို ရှေ့ဆုံး ဒါမှမဟုတ် အဆုံးမှာ ထည့်ပါတယ်။ Ordered linked list ကတော့ စီထားတဲ့ အစဉ် မပျက်အောင် item အသစ် တစ်ခုစီကို မှန်ကန်တဲ့ နေရာမှာ ထည့်ပါတယ်။

Ordered list ကို ဘာကြောင့် သုံးသလဲ

အချက်	Unordered list (အစဉ်တကျ မစီထားတဲ့ list)	Ordered list
ထည့်ခြင်း	ရှေ့ဆုံးမှာ ထည့်ရင် O(1)	O(n): မှန်ကန်တဲ့ နေရာကို ရှာရပါတယ်
ရှာခြင်း (item ရှိနေရင်)	O(n): node တိုင်းကို စစ်ရပါတယ်	Worst case (အဆိုးဆုံး အခြေအနေ) မှာ O(n)၊ ဒါပေမယ့် စောစော ရပ်နိုင်ပါတယ်
ရှာခြင်း (item မရှိရင်)	O(n): node တိုင်းကို စစ်ရပါတယ်	Worst case မှာ O(n)၊ ဒါပေမယ့် ပိုကြီးတဲ့ တန်ဖိုးကို ကျော်တာနဲ့ ရပ်ပါတယ်
Traverse လုပ်ပြီး ထုတ်တဲ့ output	ကြိုတင် သတ်မှတ်ထားတဲ့ အစဉ် မရှိပါ	စီပြီးသား ဖြစ်နေလို့ ထပ် sort လုပ်စရာ မလိုပါ
ဖျက်ခြင်း	ရှာဖို့ O(n)	ရှာဖို့ O(n)၊ ကျော်သွားရင် စောစော ရပ်နိုင်ပါတယ်

အဓိက အားသာချက်က early termination (စောစော ရပ်ခြင်း) ပါ။ မရှိတဲ့ တန်ဖိုး တစ်ခုကို ရှာတဲ့အခါ unordered list က node တိုင်းကို သွားကြည့်ရပါတယ်။ Ordered list ကတော့ ပိုကြီးတဲ့ တန်ဖိုးရှိတဲ့ node ကို ရောက်တာနဲ့ ရပ်နိုင်ပါတယ်၊ ဘာလို့လဲဆိုတော့ target value (ရှာနေတဲ့ တန်ဖိုး) က list ရဲ့ နောက်ပိုင်းမှာ ပေါ်လာစရာ မရှိတော့လို့ပါ။

Sorted Insertion Algorithm (စီထားတဲ့ အစဉ်အတိုင်း ထည့်တဲ့ နည်းလမ်း)

Ordered list ထဲကို တန်ဖိုး တစ်ခု ထည့်ဖို့ အခြေအနေ လေးမျိုးကို ကိုင်တွယ်ရပါတယ်:

1. Empty list (list အလွတ်): node အသစ်က head (list ရဲ့ ရှေ့ဆုံး node) ဖြစ်လာပါတယ်
2. Insert before head (head ရဲ့ ရှေ့မှာ ထည့်ခြင်း): တန်ဖိုးအသစ်က လက်ရှိ head ထက် ငယ်ပါတယ်
3. Insert in the middle (အလယ်မှာ ထည့်ခြင်း): တန်ဖိုးအသစ်ထက် ကြီးတဲ့ ပထမဆုံး node ကို တွေ့တဲ့အထိ traverse လုပ်ပြီး အဲဒီ node ရဲ့ ရှေ့မှာ ထည့်ပါ
4. Insert at the tail (tail မှာ ထည့်ခြင်း၊ tail ဆိုတာ list ရဲ့ နောက်ဆုံး node ပါ): တန်ဖိုးအသစ်က ရှိပြီးသား node တိုင်းထက် ကြီးပါတယ်

Pointer (reference ကို ခေါ်တဲ့ နောက်နာမည်တစ်ခု) တွေကို ပြောင်းတဲ့ အစဉ်က အရေးကြီးပါတယ်။ အလယ်မှာ ထည့်တဲ့အခါ predecessor (ရှေ့မှာ ရှိတဲ့ node) ရဲ့ next ကို update မလုပ်ခင် newNode.next ကို successor (နောက်မှာ ရှိတဲ့ node) ဆီ အမြဲ အရင် ညွှန်းထားပါ။ ဒီအစဉ်ကို ပြောင်းပြန် လုပ်မိရင် list ရဲ့ ကျန်တဲ့ အပိုင်းကို ညွှန်းထားတဲ့ reference (object ရှိရာ memory နေရာကို ညွှန်းတဲ့ တန်ဖိုး) ပျောက်သွားပါတယ်။

Node class ကို ပြန်သုံးခြင်း

ဒီစာမျက်နှာက Linked Lists စာမျက်နှာက Node class (object တွေ ဖန်တီးဖို့ ပုံစံခွက်) အတိုင်းပဲ သုံးပါတယ်:

public class Node {
    String data;
    Node next;

    public Node(String data) {
        this.data = data;
        this.next = null;
    }
}

class Node():
    def __init__(self, data):
        self.data = data    # value stored in the node
        self.next = None    # no next node yet (None is Python's null)

---

အဆင့်ဆင့် ရှင်းပြထားတဲ့ ဥပမာများ

ဥပမာ 1: အစဉ်တကျ နေရာမှာ ထည့်ခြင်း

public class OrderedLinkedList {
    private Node head;

    public OrderedLinkedList() {
        head = null;
    }

    // Insert in sorted (ascending) order
    public void insertInOrder(String data) {
        Node newNode = new Node(data);

        // Case 1 & 2: empty list or insert before head
        if (head == null || data.compareTo(head.data) < 0) {
            newNode.next = head;
            head = newNode;
            return;
        }

        // Case 3 & 4: find the correct position
        Node current = head;
        while (current.next != null && current.next.data.compareTo(data) < 0) {
            current = current.next;
        }

        // Insert after current
        newNode.next = current.next;
        current.next = newNode;
    }

    public void printAll() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public int size() {
        int count = 0;
        Node current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }

    public static void main(String[] args) {
        OrderedLinkedList roster = new OrderedLinkedList();
        roster.insertInOrder("Diana");
        roster.insertInOrder("Ben");
        roster.insertInOrder("Eve");
        roster.insertInOrder("Aiko");
        roster.insertInOrder("Carlos");

        roster.printAll();
        System.out.println("Size: " + roster.size());
    }
}

class OrderedLinkedList():
    def __init__(self):
        self._head = None

    # Insert in sorted (ascending) order
    def insert_in_order(self, data):
        new_node = Node(data)

        # Case 1 & 2: empty list or insert before head
        # Python compares strings alphabetically with < and > (no compareTo needed)
        if self._head == None or data < self._head.data:
            new_node.next = self._head
            self._head = new_node
            return

        # Case 3 & 4: find the correct position
        temp = self._head
        while temp.next != None and temp.next.data < data:
            temp = temp.next

        # Insert after temp
        new_node.next = temp.next
        temp.next = new_node

    def print_all(self):
        temp = self._head
        while temp != None:
            print(temp.data + " -> ", end="")
            temp = temp.next
        print("null")

    def size(self):
        count = 0
        temp = self._head
        while temp != None:
            count = count + 1
            temp = temp.next
        return count

roster = OrderedLinkedList()
roster.insert_in_order("Diana")
roster.insert_in_order("Ben")
roster.insert_in_order("Eve")
roster.insert_in_order("Aiko")
roster.insert_in_order("Carlos")

roster.print_all()
print("Size:", roster.size())

Output (program က ထုတ်ပြတဲ့ ရလဒ်):

Aiko -> Ben -> Carlos -> Diana -> Eve -> null
Size: 5

နာမည်တွေကို ကျပန်း အစဉ်နဲ့ ထည့်ခဲ့ပေမယ့် insertInOrder က နာမည် တစ်ခုစီကို အက္ခရာစဉ်အရ မှန်ကန်တဲ့ နေရာမှာ ထည့်ပေးလို့ စီပြီးသား ပုံစံနဲ့ ပေါ်လာပါတယ်။ compareTo method (သီးခြား အလုပ်တစ်ခု လုပ်ပေးတဲ့ code အပိုင်း) က ဘယ်ဘက် string (စာသား) က ညာဘက် string ထက် အက္ခရာစဉ်အရ အရင်လာရင် negative တန်ဖိုး (အနုတ်ကိန်း) ကို၊ နှစ်ခု တူရင် သုည ကို၊ နောက်မှ လာရင် positive တန်ဖိုး (အပေါင်းကိန်း) ကို ပြန်ပေးပါတယ်။

ထည့်မှု တစ်ခုစီ အလုပ်လုပ်ပုံ:

ထည့်တဲ့ တန်ဖိုး	ထည့်ခင် list	နေရာ	ထည့်ပြီးနောက် list
Diana	(အလွတ်)	Head (အခြေအနေ 1)	Diana
Ben	Diana	Head ရဲ့ ရှေ့ (အခြေအနေ 2)	Ben -> Diana
Eve	Ben -> Diana	Diana ရဲ့ နောက် (အခြေအနေ 4)	Ben -> Diana -> Eve
Aiko	Ben -> Diana -> Eve	Head ရဲ့ ရှေ့ (အခြေအနေ 2)	Aiko -> Ben -> Diana -> Eve
Carlos	Aiko -> Ben -> Diana -> Eve	Ben နဲ့ Diana ကြား (အခြေအနေ 3)	Aiko -> Ben -> Carlos -> Diana -> Eve

ဇယားရဲ့ နောက်ဆုံး အတန်းကို အဆင့်ဆင့် ပြထားတာပါ: နောက်က နာမည် Diana က Carlos ရဲ့ နောက်မှာ လာလို့ currenttemp က Ben မှာ ရပ်ပါတယ်။ ပုံထဲက Walk to the last name before Carlos ဆိုတာ Carlos ရဲ့ ရှေ့မှာ ရှိရမယ့် နောက်ဆုံး နာမည်အထိ လျှောက်သွားပါ၊ comes after Carlos: stop ဆိုတာ Carlos ရဲ့ နောက်မှာ လာလို့ ရပ်ပါ လို့ ဆိုလိုပါတယ်။

ဥပမာ 2: စောစော ရပ်နိုင်တဲ့ ရှာဖွေမှု

// Search that stops early when the target cannot exist
public boolean contains(String target) {
    Node current = head;
    while (current != null) {
        int comparison = current.data.compareTo(target);
        if (comparison == 0) {
            return true;     // found it
        }
        if (comparison > 0) {
            return false;    // passed where it would be: not in list
        }
        current = current.next;
    }
    return false;            // reached end of list
}

# Search that stops early when the target cannot exist
def contains(self, target):
    found = False
    passed = False
    temp = self._head
    while temp != None and found == False and passed == False:   # no break: flags end the loop
        if temp.data == target:
            found = True      # found it
        elif temp.data > target:
            passed = True     # passed where it would be: not in list
        temp = temp.next
    return found

Unordered list မှာဆိုရင် contains("Carl") က node တိုင်းကို တစ်ခုမကျန် စစ်ရပါလိမ့်မယ်။ Ordered list မှာတော့ “Carlos” ကို ရောက်တာနဲ့ method က ရပ်ပါတယ်: “Carlos” က အက္ခရာစဉ်အရ “Carl” ရဲ့ နောက်မှာ လာလို့ “Carl” က list ရဲ့ နောက်ပိုင်းမှာ ပေါ်လာစရာ မရှိတော့ပါဘူး။

ပုံထဲက stop: Carlos comes after Carl ဆိုတာ Carlos က Carl ရဲ့ နောက်မှာ လာလို့ ရပ်ပါ၊ not checked ဆိုတာ မစစ်ရတဲ့ node၊ returns false ဆိုတာ false ကို ပြန်ပေးတယ် (Python မှာ False) လို့ ဆိုလိုပါတယ်။

ဥပမာ 3: Ordered list ထဲကနေ ဖယ်ထုတ်ခြင်း

// Remove first occurrence, maintaining order
public boolean remove(String target) {
    if (head == null) {
        return false;
    }
    if (head.data.equals(target)) {
        head = head.next;
        return true;
    }
    Node current = head;
    while (current.next != null) {
        int comparison = current.next.data.compareTo(target);
        if (comparison == 0) {
            current.next = current.next.next;  // skip target node
            return true;
        }
        if (comparison > 0) {
            return false;    // passed where it would be
        }
        current = current.next;
    }
    return false;
}

# Remove first occurrence, maintaining order
def remove(self, target):
    if self._head == None:
        return False
    if self._head.data == target:
        self._head = self._head.next
        return True
    temp = self._head
    while temp.next != None:
        if temp.next.data == target:
            temp.next = temp.next.next    # skip target node
            return True
        if temp.next.data > target:
            return False    # passed where it would be
        temp = temp.next
    return False

public static void main(String[] args) {
    OrderedLinkedList list = new OrderedLinkedList();
    list.insertInOrder("Mango");
    list.insertInOrder("Apple");
    list.insertInOrder("Cherry");
    list.insertInOrder("Banana");

    System.out.println("Before:");
    list.printAll();

    list.remove("Cherry");
    System.out.println("After removing Cherry:");
    list.printAll();

    System.out.println("Contains Banana? " + list.contains("Banana"));
    System.out.println("Contains Cherry? " + list.contains("Cherry"));
}

items = OrderedLinkedList()    # "list" is a built-in name in Python
items.insert_in_order("Mango")
items.insert_in_order("Apple")
items.insert_in_order("Cherry")
items.insert_in_order("Banana")

print("Before:")
items.print_all()

items.remove("Cherry")
print("After removing Cherry:")
items.print_all()

print("Contains Banana?", items.contains("Banana"))    # Python prints True/False with a capital letter
print("Contains Cherry?", items.contains("Cherry"))

Output:

Before:
Apple -> Banana -> Cherry -> Mango -> null
After removing Cherry:
Apple -> Banana -> Mango -> null
Contains Banana? true
Contains Cherry? false

---

Quick Check (အမြန် စစ်ဆေးမေးခွန်း)

Q1. Ordered linked list နဲ့ unordered linked list ရဲ့ အဓိက ကွာခြားချက်က ဘာလဲ။

Q2. "Apple".compareTo("Cherry") က ဘာကို ပြန်ပေးသလဲ။

Q3. Ordered list ထဲကို ထည့်တဲ့အခါ တန်ဖိုးအသစ်က head ထက် ငယ်နေရင် ဘာဖြစ်သလဲ။

Q4. Target ကို ရှာမတွေ့တဲ့အခါ ordered linked list ရဲ့ ရှာဖွေမှုက ဘာကြောင့် စောစော ရပ်နိုင်သလဲ။

Q5. Ordered linked list ထဲကို ထည့်တာရဲ့ time complexity (input ကြီးလာရင် ကြာချိန် တိုးပုံ) က ဘာလဲ။

---

Trace Exercise (code ကို တစ်ဆင့်ချင်း လိုက်ကြည့်ခြင်း)

insertInOrder ကို ခေါ်ပြီးတိုင်း ordered linked list ရဲ့ အခြေအနေကို trace (တစ်ဆင့်ချင်း လိုက်ကြည့်ပြီး မှတ်) လုပ်ပါ။

OrderedLinkedList list = new OrderedLinkedList();
list.insertInOrder("Mango");
list.insertInOrder("Apple");
list.insertInOrder("Cherry");
list.insertInOrder("Banana");
list.insertInOrder("Peach");

items = OrderedLinkedList()    # "list" is a built-in name in Python
items.insert_in_order("Mango")
items.insert_in_order("Apple")
items.insert_in_order("Cherry")
items.insert_in_order("Banana")
items.insert_in_order("Peach")

အဖြေတွေကို English လို ရိုက်ထည့်ပါ။ Insertion case ကော်လံမှာ အပေါ်က အခြေအနေ လေးမျိုးရဲ့ နာမည်တိုတွေထဲက တစ်ခုကို ရိုက်ပါ: empty list (list အလွတ်)၊ before head (head ရဲ့ ရှေ့မှာ)၊ middle (အလယ်မှာ) ဒါမှမဟုတ် tail (list ရဲ့ အဆုံးမှာ)။ List ကော်လံမှာ code ထုတ်ပေးတဲ့ ပုံစံအတိုင်း (ဥပမာ Mango -> null) ရိုက်ပါ။

ထည့်လိုက်တဲ့ တန်ဖိုး	Insertion case (ထည့်တဲ့ အခြေအနေ)	List တစ်ခုလုံး (head ကနေ tail အထိ)
Mango		Mango -> null
Apple
Cherry
Banana
Peach

---

Code Completion (code ကွက်လပ် ဖြည့်ခြင်း)

တန်ဖိုး တစ်ခုကို စီထားတဲ့ အစဉ်ထဲက မှန်ကန်တဲ့ နေရာမှာ ထည့်ပေးမယ့် insertInOrder method ကို ဖြည့်ပါ။

ထည့်ရမယ့် နေရာကို ရှာပြီး ထည့်ဖို့ ကွက်လပ်တွေကို ဖြည့်ပါ:

public void insertInOrder(String data) {
    Node newNode = new Node(data);
    if (head == null || data.(head.data) < 0) {
        newNode.next = head;
        head = ;
        return;
    }
    Node current = head;
    while (current. != null && current.next.data.compareTo(data) < 0) {
        current = current.next;
    }
    newNode.next = current.next;
    current. = newNode;
}

---

စောစော ရပ်နိုင်တဲ့ search method ကို ဖြည့်ပါ။

Target ရှိရမယ့် နေရာကို ကျော်သွားတာနဲ့ ရပ်တဲ့ ရှာဖွေမှုအတွက် ကွက်လပ်တွေကို ဖြည့်ပါ:

public boolean contains(String target) {
    Node current = head;
    while (current != null) {
        int comparison = current.data.compareTo();
        if (comparison == ) {
            return true;
        }
        if (comparison > 0) {
            return ;
        }
        current = current.next;
    }
    return false;
}

---

Spot the Error (အမှား ရှာခြင်း)

ဒီ insertInOrder method က "Apple" ကို "Mango" ရဲ့ ရှေ့မှာ ထည့်ရမယ့်အစား နောက်မှာ ထည့်နေပါတယ်:

1public void insertInOrder(String data) { 2 Node newNode = new Node(data); 3 if (head == null || data.compareTo(head.data) > 0) { 4 newNode.next = head; 5 head = newNode; 6 return; 7 }

Line 3 အတွက် မှန်ကန်တဲ့ ပြင်နည်းကို ရွေးပါ:

---

ဒီ insertion loop (ထည့်ဖို့ နေရာရှာတဲ့ loop) က တန်ဖိုးတွေကို နေရာမှား ထည့်နေပါတယ်: "Cherry" က "Apple" ရဲ့ ရှေ့ ရောက်သွားပါတယ်။ Line 1 က head ကို စစ်တာ ပြီးသွားပြီလို့ ပြတဲ့ comment ပါ:

1// After head check passed: 2Node current = head; 3while (current.next != null && 4 current.next.data.compareTo(data) > 0) { 5 current = current.next; 6}

Line 4 အတွက် မှန်ကန်တဲ့ ပြင်နည်းကို ရွေးပါ:

---

Predict the Output (output ကို ကြိုခန့်မှန်းခြင်း)

ဒီ code က ဘာကို print ထုတ်မလဲ။

OrderedLinkedList nums = new OrderedLinkedList();
nums.insertInOrder("50");
nums.insertInOrder("20");
nums.insertInOrder("40");
nums.insertInOrder("10");
nums.insertInOrder("30");
nums.printAll();

Output ကို အတိအကျ ရိုက်ထည့်ပါ:

---

ဒီ code က ဘာကို print ထုတ်မလဲ။

OrderedLinkedList fruits = new OrderedLinkedList();
fruits.insertInOrder("Cherry");
fruits.insertInOrder("Apple");
fruits.insertInOrder("Date");
fruits.insertInOrder("Banana");

System.out.println(fruits.contains("Coconut"));
System.out.println(fruits.contains("Cherry"));

Output ကို အတိအကျ ရိုက်ထည့်ပါ:

---

Practice Exercises (လေ့ကျင့်ခန်းများ)

Core (အခြေခံ အဆင့်)

1. စီထားတဲ့ ကျောင်းသား စာရင်း တည်ဆောက်ပါ: OrderedLinkedList တစ်ခု ဖန်တီးပြီး ကျောင်းသား နာမည် 7 ခုကို ကျပန်း အစဉ်နဲ့ ထည့်ပါ။ List ကို print ထုတ်ပြီး နာမည်အားလုံး အက္ခရာစဉ်အတိုင်း ပေါ်လာကြောင်း စစ်ကြည့်ပါ။
2. စောစော ရပ်တာကို ရေတွက်ကြည့်ပါ: contains method က return မပြန်ခင် node ဘယ်နှစ်ခု သွားကြည့်ခဲ့လဲ ဆိုတာကိုပါ print ထုတ်အောင် ပြင်ပါ။ List ရဲ့ အစနားက တန်ဖိုး တစ်ခု၊ အဆုံးနားက တန်ဖိုး တစ်ခုနဲ့ list ထဲမှာ မရှိတဲ့ တန်ဖိုး တစ်ခုကို ရှာပြီး စမ်းသပ်ပါ။ ရေတွက်ထားတဲ့ အရေအတွက်တွေကို နှိုင်းယှဉ်ပါ။
3. ဖယ်ထုတ်ပြီး စစ်ကြည့်ပါ: တန်ဖိုး 5 ခုကို ကျပန်း အစဉ်နဲ့ ထည့်ပါ။ စီပြီးသား list ကို print ထုတ်ပါ။ အလယ်က တန်ဖိုးကို ဖယ်ထုတ်ပြီး ထပ် print ထုတ်ပါ။ Head ကို ဖယ်ထုတ်ပြီး ထပ် print ထုတ်ပါ။ ဖယ်ထုတ်ပြီးတိုင်း list က အစဉ်တကျ ရှိနေဆဲ ဖြစ်ကြောင်း စစ်ကြည့်ပါ။

Extension (တိုးချဲ့ အဆင့်)

4. ထပ်နေတဲ့ တန်ဖိုးတွေ ထည့်ခြင်း: ထပ်နေတဲ့ တန်ဖိုး (duplicate) ကို အဲဒီ တန်ဖိုး ပထမဆုံး ပေါ်တဲ့ နေရာရဲ့ နောက်မှာ ချက်ချင်း ထည့်အောင် insertInOrder ကို ပြင်ပါ။ “Banana” ကို နှစ်ခါ ထည့်ပြီး နှစ်ခုလုံး ဆက်တိုက် ပေါ်လာကြောင်း စစ်ကြည့်ပါ။
5. Ordered list နှစ်ခုကို merge (ပေါင်းစပ်) လုပ်ပါ: List နှစ်ခုလုံးက element (အစုထဲက အချက်) အားလုံး ပါတဲ့ ordered list အသစ် တစ်ခုကို ဖန်တီးပေးတဲ့ public static OrderedLinkedList merge(OrderedLinkedList a, OrderedLinkedList b) method ကို ရေးပါ။ ရလဒ်က စီပြီးသား ဖြစ်ရပါမယ်။ Merge လုပ်ဖို့ insertInOrder ကို မသုံးပါနဲ့: အဲဒီအစား list နှစ်ခုလုံးကို တစ်ပြိုင်နက် လျှောက်သွားပြီး head တန်ဖိုး နှစ်ခုထဲက ပိုငယ်တဲ့ တစ်ခုကို အမြဲ ရွေးယူပါ။

Challenge (စိန်ခေါ်မှု အဆင့်)

6. စွမ်းဆောင်ရည် နှိုင်းယှဉ်ခြင်း: ကျပန်း string 1000 ကို unordered SinglyLinkedList (addToFront ကို သုံးပြီး) ထဲရော OrderedLinkedList ထဲပါ ထည့်တဲ့ program တစ်ခု ရေးပါ။ ပြီးရင် list နှစ်ခုလုံးထဲမှာ မရှိတဲ့ string 100 ကို ရှာပါ။ List တစ်ခုစီအတွက် node comparison (တန်ဖိုး နှစ်ခုကို နှိုင်းယှဉ်ခြင်း) စုစုပေါင်း အရေအတွက်ကို ရေတွက်ပါ။ မရှိတဲ့ တန်ဖိုးတွေကို ရှာတဲ့အခါ ဘယ် list က comparison ပိုနည်းနည်း လုပ်ရသလဲ။
7. Integer (ကိန်းပြည့်) key တွေ သုံးတဲ့ ordered list: OrderedLinkedList ကို String အစား int တန်ဖိုးတွေ သိမ်းအောင် ပြန်ရေးပါ။ insertInOrder၊ contains နဲ့ remove ကို compareTo အစား integer နှိုင်းယှဉ်ချက် (<, >, ==) တွေ သုံးအောင် ပြင်ပါ။ 50, 20, 40, 10, 30 ကိန်းတွေကို ထည့်ပြီး output က စီပြီးသား ဖြစ်ကြောင်း စစ်ကြည့်ပါ။

---

ဆက်စပ် ခေါင်းစဉ်များ

• အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: Linked Lists (node တွေ ချိတ်ဆက်ထားတဲ့ list များ): Node class၊ အခြေခံ insertion၊ deletion နဲ့ traversal
• ဆက်စပ် ခေါင်းစဉ်: Sorting Algorithms (ဒေတာကို အစဉ်လိုက် စီတဲ့ အယ်လ်ဂိုရီသမ်များ): အစဉ်တကျ နေရာမှာ ထည့်တာက ဘေးထွက် ရလဒ် အနေနဲ့ sorting (အစဉ်တကျ စီခြင်း) ကိုပါ ရစေပါတယ်
• ဆက်စပ် ခေါင်းစဉ်: Binary Search Trees (ဘယ်ဘက် ငယ်၊ ညာဘက် ကြီးတဲ့ binary tree များ): BST တွေက စီထားတဲ့ ဒေတာပေါ်မှာ O(log n) နဲ့ ရှာနိုင်လို့ ordered list ရဲ့ O(n) ထက် ပိုကောင်းပါတယ်
• နောက်ထပ် လေ့လာမယ့် ခေါင်းစဉ်: Doubly Linked Lists (နှစ်ဘက်လုံး ချိတ်ဆက်ထားတဲ့ linked list များ): ရှေ့ဆက်ရော နောက်ပြန်ပါ traverse လုပ်နိုင်ဖို့ prev pointer ထည့်ခြင်း