Linked Lists (node တွေ ချိတ်ဆက်ထားတဲ့ list များ)

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

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

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

Linked list ဆိုတာ node (ဒေတာ သိမ်းထားတဲ့ အကွက်) လို့ ခေါ်တဲ့ element (အစုထဲက အချက်) တွေကို တစ်ကြောင်းတည်း အစဉ်လိုက် စုထားတဲ့ collection (ဒေတာအစု) ပါ။ Node တစ်ခုစီမှာ ဒေတာနဲ့ အစဉ်ထဲက နောက် node ကို ညွှန်းတဲ့ reference (object ရှိရာ memory နေရာကို ညွှန်းတဲ့ တန်ဖိုး၊ pointer လို့လည်း ခေါ်ပါတယ်) ကို သိမ်းထားပါတယ်။ Array (အရွယ်အစား ပုံသေ၊ အမျိုးအစားတူ ဒေတာစု) နဲ့ မတူတာက element တွေကို contiguous memory (memory ထဲမှာ ဆက်တိုက် ကပ်လျက် ရှိတဲ့ နေရာ) ထဲမှာ မသိမ်းပါဘူး: node တစ်ခုစီက heap (object တွေ သိမ်းတဲ့ memory အပိုင်း) ထဲက ဘယ်နေရာမှာမဆို ရှိနိုင်ပြီး reference တွေနဲ့ပဲ ချိတ်ဆက်ထားပါတယ်။

Node (ဒေတာ သိမ်းထားတဲ့ အကွက်)

Singly linked list ထဲက node တိုင်းမှာ အပိုင်း နှစ်ပိုင်း ရှိပါတယ်:

  • Data: node ထဲမှာ သိမ်းထားတဲ့ တန်ဖိုး
  • Next: နောက် node ကို ညွှန်းတဲ့ reference။ နောက်ဆုံး node ဖြစ်ရင် next က null (ဘာ object ကိုမှ မညွှန်းတဲ့ တန်ဖိုး) ဖြစ်ပါတယ်။ Python မှာတော့ ဒီအယူအဆအတွက် None ကို သုံးပါတယ်။
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)

Node class (object တွေ ဖန်တီးဖို့ ပုံစံခွက်) က self-referential (ကိုယ့် class အမျိုးအစားကိုယ် ပြန်ညွှန်းတဲ့) class ပါ: field (object ထဲက အချက်အလက် အကွက်) next ရဲ့ type က Node ဖြစ်တာကြောင့် node တစ်ခုစီက type တူတဲ့ နောက် node တစ်ခုကို ညွှန်းပါတယ်။

Head (list ရဲ့ ရှေ့ဆုံး node) နဲ့ Tail (list ရဲ့ နောက်ဆုံး node)

  • Head ဆိုတာ list ထဲက ပထမဆုံး node ကို ညွှန်းတဲ့ reference ပါ။ List ကို head ကနေ တစ်ဆင့် ယူသုံးပါတယ်။
  • Tail ဆိုတာ list ထဲက နောက်ဆုံး node ပါ။ သူ့ရဲ့ next field က null ဖြစ်ပါတယ်။
  • Empty list (ဘာ node မှ မရှိတဲ့ list) မှာ head == null ဖြစ်ပါတယ်။
head က ပထမဆုံး node ဖြစ်တဲ့ Apple ကို ညွှန်းပါတယ်။ Node တစ်ခုစီက အပိုင်း နှစ်ပိုင်းပါတဲ့ အကွက်ပါ: data က တန်ဖိုးကို သိမ်းပြီး next က နောက် node ကို ညွှန်းတဲ့ reference ကို သိမ်းပါတယ်။ အဲဒီ reference ကို မြှားနဲ့ ဆွဲပြထားပါတယ်။ Apple က Banana ကို ညွှန်းပြီး Banana က Cherry ကို ညွှန်းပါတယ်။ Cherry က နောက်ဆုံး node (tail) ပါ: သူ့ next က null ဖြစ်လို့ list က အဲဒီမှာ ဆုံးပါတယ်။ Apple Banana Cherry head null None one node data next last node (tail)

Node တစ်ခုစီက data နဲ့ next ဆိုတဲ့ အပိုင်း နှစ်ပိုင်းပါတဲ့ အကွက်ပါ။ မြှားတစ်ခုစီက next field ထဲက အစက်ကနေ စပြီး အဲဒီ field ညွှန်းထားတဲ့ node မှာ ဆုံးပါတယ်။

ပုံထဲက English စာတွေရဲ့ အဓိပ္ပာယ်: “one node” က node တစ်ခု၊ “last node (tail)” က နောက်ဆုံး node (tail) လို့ အဓိပ္ပာယ်ရပါတယ်။

အဓိက ဝေါဟာရများ

ဝေါဟာရ အဓိပ္ပာယ်
Node ဒေတာနဲ့ pointer ပါတဲ့ element တစ်ခု
Head ပထမဆုံး node ကို ညွှန်းတဲ့ reference
Tail နောက်ဆုံး node (next က null ဖြစ်ပါတယ်)
Successor Node တစ်ခုရဲ့ နောက်မှာ ရှိတဲ့ node
Predecessor Node တစ်ခုရဲ့ ရှေ့မှာ ရှိတဲ့ node
Null pointer ဘာကိုမှ မညွှန်းတဲ့ reference: list ရဲ့ အဆုံးကို ပြပါတယ်
Traversal next reference တွေကို လိုက်ပြီး head ကနေ tail အထိ node တိုင်းကို သွားကြည့်ခြင်း

Linked List နဲ့ Array နှိုင်းယှဉ်ချက်

ဂုဏ်သတ္တိ Array Singly Linked List
အရွယ်အစား ဖန်တီးချိန်မှာ ပုံသေ Program run နေစဉ် ကြီးလာ၊ သေးသွားနိုင်
Memory ထဲမှာ နေရာချပုံ ဆက်တိုက် ကပ်လျက် အပိုင်း တစ်ခု Reference တွေနဲ့ ချိတ်ထားပြီး ဟိုဒီ ပြန့်ကျဲနေတဲ့ node တွေ
Index (နေရာအမှတ်) နဲ့ ယူသုံးခြင်း O(1): တိုက်ရိုက် O(n): head ကနေ traverse လုပ်ရပါတယ်
ရှေ့ဆုံးမှာ ထည့်ခြင်း O(n): element အားလုံးကို နေရာ ရွှေ့ရပါတယ် O(1): head reference ကို ပြင်ရုံပါပဲ
အဆုံးမှာ ထည့်ခြင်း နေရာ ရှိရင် O(1) O(n): tail အထိ traverse လုပ်ရပါတယ် (tail reference ရှိရင် O(1))
ရှေ့ဆုံးကနေ ဖျက်ခြင်း O(n): element အားလုံးကို နေရာ ရွှေ့ရပါတယ် O(1): head reference ကို ပြင်ရုံပါပဲ
Element တစ်ခုစီအတွက် memory ဒေတာ သက်သက်ပဲ ဒေတာ + reference တစ်ခု (အပို ကုန်ကျမှု ဖြစ်တဲ့ overhead)

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

ဥပမာ 1: Linked List ကို အစကနေ တည်ဆောက်ခြင်း 

public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        head = null;
    }

    // Add a new node to the front of the list
    public void addToFront(String data) {
        Node newNode = new Node(data);
        newNode.next = head;   // point new node to current head
        head = newNode;        // update head to new node
    }

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

    // Return the number of nodes
    public int size() {
        int count = 0;
        Node current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }

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

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

class SinglyLinkedList():
    def __init__(self):
        self._head = None    # leading underscore = private, like Java's private modifier

    # Add a new node to the front of the list
    def add_to_front(self, data):
        new_node = Node(data)
        new_node.next = self._head   # point new node to current head
        self._head = new_node        # update head to new node

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

    # Return the number of nodes
    def size(self):
        count = 0
        temp = self._head
        while temp != None:
            count = count + 1
            temp = temp.next
        return count

# "list" is a built-in name in Python, so the driver uses a different variable name
fruits = SinglyLinkedList()
fruits.add_to_front("Cherry")
fruits.add_to_front("Banana")
fruits.add_to_front("Apple")

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

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

Apple -> Banana -> Cherry -> null
Size: 3

addToFront က ထည့်တဲ့ အစဉ်ကို ပြောင်းပြန် ဖြစ်စေတာကို သတိထားကြည့်ပါ: “Cherry” ကို အရင်ဆုံး ထည့်ခဲ့ပေမယ့် node အသစ် တစ်ခုစီကို လက်ရှိ head ရဲ့ ရှေ့မှာ ထားတာကြောင့် Cherry က tail မှာ ရောက်သွားပါတယ်။

Apple ကို သိမ်းထားတဲ့ node အသစ် တစ်ခု ဖန်တီးလိုက်ပါတယ်။ သူ့ next က null ပါ။ head ကတော့ Banana၊ ပြီးရင် Cherry ဆိုတဲ့ list ရဲ့ ပထမဆုံး node ဖြစ်တဲ့ Banana ကို ညွှန်းနေတုန်းပါ။ Apple Banana Cherry null None newNode new_node head null None 1 Node newNode = new Node("Apple"); new_node = Node("Apple") အခု Apple ရဲ့ next က head ညွှန်းထားတဲ့ node ဖြစ်တဲ့ Banana ကို ညွှန်းပါတယ်။ head ကတော့ မပြောင်းရသေးပါဘူး။ Apple Banana Cherry null None newNode new_node head 2 newNode.next = head; new_node.next = self._head အခု head က Apple ကို ညွှန်းတာကြောင့် list က Apple, Banana, Cherry ဖြစ်သွားပါတယ်။ Apple Banana Cherry null None newNode new_node head 3 head = newNode; self._head = new_node

Banana, Cherry ဆိုတဲ့ list ပေါ်မှာ addToFront("Apple")add_to_front("Apple") ကို ခေါ်ပုံပါ။ အဆင့်တိုင်းရဲ့ ခေါင်းစဉ်က အဲဒီ အဆင့်ရဲ့ code line ဖြစ်ပြီး အရောင် ထင်ရှားတဲ့ မြှားက အဲဒီ line ပြောင်းလိုက်တဲ့ reference ပါ။

လုပ်တဲ့ အစဉ်က အရေးကြီးပါတယ်။ addToFront ထဲမှာ head = newNode လို့ head ကို မပြောင်းခင် newNode.next = head ကို အရင် သတ်မှတ်ပါ။ ဒီအဆင့်တွေကို ပြောင်းပြန် လုပ်မိရင် head အဟောင်းကို ညွှန်းတဲ့ reference ပျောက်သွားပြီး သူနဲ့အတူ ကျန်တဲ့ list တစ်ခုလုံးကိုလည်း ပြန်ရောက်လို့ မရတော့ပါဘူး။

ဥပမာ 2: အဆုံးမှာ ထည့်ခြင်း၊ ရှာခြင်းနဲ့ ဖယ်ထုတ်ခြင်း 

public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        head = null;
    }

    public void addToFront(String data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // Add a new node to the end of the list
    public void addToEnd(String data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;    // empty list: new node becomes head
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;  // traverse to last node
        }
        current.next = newNode;      // link last node to new node
    }

    // Search for a value: return true if found
    public boolean contains(String target) {
        Node current = head;
        while (current != null) {
            if (current.data.equals(target)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    // Remove the first occurrence of a value
    public boolean remove(String target) {
        if (head == null) {
            return false;              // empty list
        }
        if (head.data.equals(target)) {
            head = head.next;          // remove head node
            return true;
        }
        Node current = head;
        while (current.next != null) {
            if (current.next.data.equals(target)) {
                current.next = current.next.next;  // skip the target node
                return true;
            }
            current = current.next;
        }
        return false;                  // not found
    }

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

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

        System.out.println("Initial list:");
        roster.printAll();

        System.out.println("Contains Ben? " + roster.contains("Ben"));
        System.out.println("Contains Eve? " + roster.contains("Eve"));

        roster.remove("Ben");
        System.out.println("After removing Ben:");
        roster.printAll();

        roster.remove("Aiko");
        System.out.println("After removing Aiko (head):");
        roster.printAll();
    }
}

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

    def add_to_front(self, data):
        new_node = Node(data)
        new_node.next = self._head
        self._head = new_node

    # Add a new node to the end of the list
    def add_to_end(self, data):
        new_node = Node(data)
        if self._head == None:
            self._head = new_node    # empty list: new node becomes head
            return
        temp = self._head
        while temp.next != None:
            temp = temp.next         # traverse to last node
        temp.next = new_node         # link last node to new node

    # Search for a value: return True if found
    def contains(self, target):
        found = False
        temp = self._head
        while temp != None and found == False:   # no break: the flag ends the loop
            if temp.data == target:              # == compares string content in Python
                found = True
            temp = temp.next
        return found

    # Remove the first occurrence of a value
    def remove(self, target):
        if self._head == None:
            return False                     # empty list
        if self._head.data == target:
            self._head = self._head.next    # remove head node
            return True
        temp = self._head
        while temp.next != None:
            if temp.next.data == target:
                temp.next = temp.next.next  # skip the target node
                return True
            temp = temp.next
        return False                        # not found

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

roster = SinglyLinkedList()
roster.add_to_end("Aiko")
roster.add_to_end("Ben")
roster.add_to_end("Carlos")
roster.add_to_end("Diana")

print("Initial list:")
roster.print_all()

print("Contains Ben?", roster.contains("Ben"))    # Python prints True/False with a capital letter
print("Contains Eve?", roster.contains("Eve"))

roster.remove("Ben")
print("After removing Ben:")
roster.print_all()

roster.remove("Aiko")
print("After removing Aiko (head):")
roster.print_all()

Output:

Initial list:
Aiko -> Ben -> Carlos -> Diana -> null
Contains Ben? true
Contains Eve? false
After removing Ben:
Aiko -> Carlos -> Diana -> null
After removing Aiko (head):
Carlos -> Diana -> null
current က head ဖြစ်တဲ့ Aiko ကနေ စပြီး node တစ်ခုချင်း ရှေ့ဆက်သွားပါတယ်: Aiko, Ben, Carlos, Diana။ ဘယ် node မှာမှ Eve မရှိပါဘူး။ Diana ပြီးနောက် current က null ဖြစ်သွားလို့ loop ရပ်ပြီး method က false ကို ပြန်ပေးပါတယ်။ contains("Ben") ဆိုရင်တော့ ဒုတိယ node မှာ ရပ်ပြီး true ကို ပြန်ပေးပါလိမ့်မယ်။ Aiko Ben Carlos Diana head null None 1 2 3 4 5 current temp contains("Eve") current က head ဖြစ်တဲ့ Aiko ကနေ စပြီး node တစ်ခုချင်း ရှေ့ဆက်သွားပါတယ်: Aiko, Ben, Carlos, Diana။ ဘယ် node မှာမှ Eve မရှိပါဘူး။ Diana ပြီးနောက် current က null ဖြစ်သွားလို့ loop ရပ်ပြီး method က false ကို ပြန်ပေးပါတယ်။ contains("Ben") ဆိုရင်တော့ ဒုတိယ node မှာ ရပ်ပြီး true ကို ပြန်ပေးပါလိမ့်မယ်။ Aiko Ben Carlos Diana head null None 1 2 3 4 5 current temp current temp contains("Eve")

contains("Eve") က currenttemp ကို list တစ်လျှောက် node တစ်ခုချင်း ရွှေ့သွားပါတယ်။ Diana ပြီးနောက် currenttemp က nullNone ဖြစ်သွားလို့ loop (ထပ်ခါထပ်ခါ run တဲ့ code အပိုင်း) ပြီးဆုံးပြီး method (သီးခြား အလုပ်တစ်ခု လုပ်ပေးတဲ့ code အပိုင်း) က falseFalse ကို ပြန်ပေးပါတယ်။

remove အလုပ်လုပ်ပုံ:

  • Head ကို ဖယ်ထုတ်ခြင်း: target (ရှာပြီး ဖယ်ထုတ်ချင်တဲ့ တန်ဖိုး) က head node ဖြစ်ရင် head = head.next လို့ သတ်မှတ်လိုက်ရုံပါပဲ: head အဟောင်းကို ကျော်သွားပါတယ်။
  • အလယ် ဒါမှမဟုတ် အဆုံးက node ကို ဖယ်ထုတ်ခြင်း: current.next မှာ target ရောက်တဲ့အထိ traverse လုပ်ပါ။ ပြီးရင် target node ကို ကျော်ဖို့ current.next = current.next.next လို့ သတ်မှတ်ပါ။ ကျော်ခံရတဲ့ node ကို ဘယ်ကနေမှ ပြန်ရောက်လို့ မရတော့လို့ garbage collection (မသုံးတော့တဲ့ object ရဲ့ memory ကို အလိုအလျောက် ပြန်ယူခြင်း) လုပ်ခံရပါလိမ့်မယ်။
current က Ben ရဲ့ ရှေ့က node ဖြစ်တဲ့ Aiko ကို ညွှန်းပါတယ်။ Aiko ရဲ့ next ကို Ben ကို ကျော်ပြီး Carlos ကို ညွှန်းအောင် ပြောင်းလိုက်ပါတယ် (အစိမ်းရောင် မျဉ်းကွေး)။ Ben ကို ဘာကမှ မညွှန်းတော့လို့ (မျဉ်းပြတ်) သူက list ရဲ့ အစိတ်အပိုင်း မဟုတ်တော့ပါဘူး: list က Aiko, Carlos, Diana ဖြစ်ပါတယ်။ Aiko Ben Carlos Diana head null None current temp nothing refers to Ben now 1 current.next = current.next.next; temp.next = temp.next.next current က Ben ရဲ့ ရှေ့က node ဖြစ်တဲ့ Aiko ကို ညွှန်းပါတယ်။ Aiko ရဲ့ next ကို Ben ကို ကျော်ပြီး Carlos ကို ညွှန်းအောင် ပြောင်းလိုက်ပါတယ် (အစိမ်းရောင် မျဉ်းကွေး)။ Ben ကို ဘာကမှ မညွှန်းတော့လို့ (မျဉ်းပြတ်) သူက list ရဲ့ အစိတ်အပိုင်း မဟုတ်တော့ပါဘူး: list က Aiko, Carlos, Diana ဖြစ်ပါတယ်။ Aiko Ben Carlos Diana head null None current temp nothing refers to Ben now 1 current.next = current.next.next; temp.next = temp.next.next head ကို Aiko ရဲ့ နောက် node ဖြစ်တဲ့ Carlos ကို ညွှန်းအောင် ပြောင်းလိုက်ပါတယ် (အစိမ်းရောင်)။ Aiko ကို ဘာကမှ မညွှန်းတော့လို့ (မျဉ်းပြတ်) list က Carlos, Diana ဖြစ်ပါတယ်။ Aiko Carlos Diana null None head 2 head = head.next; self._head = self._head.next head ကို Aiko ရဲ့ နောက် node ဖြစ်တဲ့ Carlos ကို ညွှန်းအောင် ပြောင်းလိုက်ပါတယ် (အစိမ်းရောင်)။ Aiko ကို ဘာကမှ မညွှန်းတော့လို့ (မျဉ်းပြတ်) list က Carlos, Diana ဖြစ်ပါတယ်။ Aiko Carlos Diana null None head 2 head = head.next; self._head = self._head.next

Ben ကို ဖယ်ထုတ်ပြီးနောက် head ဖြစ်တဲ့ Aiko ကို ဖယ်ထုတ်ပုံပါ။ မျဉ်းပြတ်နဲ့ ဆွဲထားတဲ့ node ကို head ကနေ ပြန်ရောက်လို့ မရတော့လို့ list ရဲ့ အစိတ်အပိုင်း မဟုတ်တော့ပါဘူး။

ပုံထဲက “nothing refers to Ben now” က Ben ကို အခု ဘာကမှ မညွှန်းတော့ဘူးလို့ အဓိပ္ပာယ်ရပါတယ်။

ဥပမာ 3: သတ်မှတ်ထားတဲ့ နေရာမှာ ထည့်ခြင်း 

// Insert at a given index (0-based)
public void insertAt(int index, String data) {
    if (index == 0) {
        addToFront(data);
        return;
    }
    Node newNode = new Node(data);
    Node current = head;
    for (int i = 0; i < index - 1; i++) {
        if (current == null) {
            return;  // index out of bounds
        }
        current = current.next;
    }
    if (current == null) {
        return;  // index out of bounds
    }
    newNode.next = current.next;   // new node points to successor
    current.next = newNode;        // predecessor points to new node
}

# Insert at a given index (0-based)
def insert_at(self, index, data):
    if index == 0:
        self.add_to_front(data)
        return
    new_node = Node(data)
    temp = self._head
    for i in range(index - 1):
        if temp == None:
            return    # index out of bounds
        temp = temp.next
    if temp == None:
        return    # index out of bounds
    new_node.next = temp.next    # new node points to successor
    temp.next = new_node         # predecessor points to new node

အလယ်မှာ ထည့်ဖို့ predecessor node (index - 1 နေရာက node) ကို အရင် ရှာပြီး reference တွေကို လမ်းကြောင်း ပြောင်းပေးရပါတယ်:

  1. newNode.next က predecessor ရဲ့ လက်ရှိ successor ကို ညွှန်းအောင် သတ်မှတ်ပါ
  2. Predecessor ရဲ့ next က node အသစ်ကို ညွှန်းအောင် သတ်မှတ်ပါ

Element တွေကို နေရာ ရွှေ့ဖို့ မလိုပါဘူး၊ reference နှစ်ခုကို ပြင်ရုံပါပဲ။

List က Aiko, Carlos, Diana ပါ။ current က index 1 ရဲ့ ရှေ့က node ဖြစ်တဲ့ Aiko ကို ညွှန်းပါတယ်။ Ben ကို သိမ်းထားတဲ့ node အသစ် တစ်ခု ဖန်တီးထားပြီး သူ့ next က null ပါ။ Aiko Carlos Diana Ben null None head current temp newNode new_node null None 1 Find the node before index 1 အခု Ben ရဲ့ next က current ရဲ့ နောက်က node ဖြစ်တဲ့ Carlos ကို ညွှန်းပါတယ်။ Aiko ကလည်း Carlos ကို ညွှန်းနေတုန်းပါ။ Aiko Carlos Diana Ben null None head current temp newNode new_node 2 newNode.next = current.next; new_node.next = temp.next အခု Aiko ရဲ့ next က Ben ကို ညွှန်းတာကြောင့် list က Aiko, Ben, Carlos, Diana ဖြစ်သွားပါတယ်။ Aiko Carlos Diana Ben null None head current temp newNode new_node 3 current.next = newNode; temp.next = new_node အမှား: Ben ရဲ့ next ကို မသတ်မှတ်ခင် Aiko ရဲ့ next ကို Ben အဖြစ် ပြောင်းလိုက်ရင် Ben ရဲ့ next က null ဖြစ်နေတုန်းပြီး Carlos ကို ဘာကမှ မညွှန်းတော့ပါဘူး။ Carlos နဲ့ Diana က list ထဲကနေ ပျောက်သွားပါတယ်။ Aiko Carlos Diana Ben null None head current temp newNode new_node null None lost: nothing refers to Carlos If step 3 runs first

Aiko, Carlos, Diana ဆိုတဲ့ list ပေါ်မှာ insertAt(1, "Ben")insert_at(1, "Ben") ကို ခေါ်ပုံပါ။ နောက်ဆုံး ပုံက အစဉ် ဘာကြောင့် အရေးကြီးလဲ ဆိုတာ ပြပါတယ်: predecessor ရဲ့ next ကို အရင် ပြောင်းလိုက်ရင် Carlos ကို ဘာကမှ မညွှန်းတော့ဘဲ ကျန်တဲ့ list တစ်ခုလုံး ပျောက်သွားပါတယ်။

ပုံထဲက English စာတွေရဲ့ အဓိပ္ပာယ်: “Find the node before index 1” က index 1 ရဲ့ ရှေ့က node ကို ရှာပါ၊ “If step 3 runs first” က အဆင့် 3 ကို အရင် run မိရင်၊ “lost: nothing refers to Carlos” က ပျောက်သွားပြီ၊ Carlos ကို ဘာကမှ မညွှန်းတော့ဘူးလို့ အဓိပ္ပာယ်ရပါတယ်။

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

Q1. Singly linked list ထဲက node တစ်ခုမှာ ဘာ နှစ်ခု ပါသလဲ။

Q2. Singly linked list ရဲ့ အဆုံးကို ဘယ်လို သိနိုင်သလဲ။

Q3. Singly linked list ရဲ့ ရှေ့ဆုံးမှာ node တစ်ခု ထည့်တဲ့ time complexity (input ကြီးလာရင် ကြာချိန် တိုးပုံ) က ဘာလဲ။

Q4. addToFront method ထဲမှာ newNode.next = head က head = newNode ရဲ့ ရှေ့မှာ ဘာကြောင့် ရှိရမလဲ။

Q5. Singly linked list ရဲ့ အလယ်က node တစ်ခုကို ဖယ်ထုတ်ဖို့ ဘာလုပ်ရမလဲ။

Q6. Node n ခု ပါတဲ့ singly linked list မှာ ပေးထားတဲ့ index က element ကို ယူသုံးတဲ့ worst-case (အဆိုးဆုံး အခြေအနေ) time complexity က ဘာလဲ။

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

အောက်က code ကို trace (တစ်ဆင့်ချင်း လိုက်ပြီး မှတ်) လုပ်ပြီး operation (ဒေတာပေါ်မှာ လုပ်တဲ့ လုပ်ဆောင်ချက်) တစ်ခုစီ ပြီးနောက် list ရဲ့ အခြေအနေကို ဖြည့်ပါ။ List ကို code ရဲ့ output ပုံစံအတိုင်း English နဲ့ ရိုက်ထည့်ပါ (ဥပမာ C -> null)။

SinglyLinkedList list = new SinglyLinkedList();
list.addToFront("C");
list.addToFront("B");
list.addToFront("A");
list.addToEnd("D");
list.remove("B");

items = SinglyLinkedList()    # "list" is a built-in name in Python
items.add_to_front("C")
items.add_to_front("B")
items.add_to_front("A")
items.add_to_end("D")
items.remove("B")
ဒီ operation ပြီးနောက်Head nodeList တစ်ခုလုံး (head ကနေ tail အထိ)size()
addToFront("C") C -> null
addToFront("B") 2
addToFront("A") A -> B -> C -> null
addToEnd("D") A
remove("B") 3

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

Linked list ထဲမှာ target value ကို ရှာပေးတဲ့ contains method ကို ဖြည့်ပါ။

List ကို traverse လုပ်ပြီး target ကို ရှာဖို့ ကွက်လပ်တွေကို ဖြည့်ပါ:

public boolean contains(String target) {
    Node current = ;
    while (current != ) {
        if (current.data.(target)) {
            return true;
        }
        current = current.;
    }
    return false;
}

နောက်ဆုံး node ရဲ့ နောက်မှာ node တစ်ခု ထည့်ပေးတဲ့ addToEnd method ကို ဖြည့်ပါ။

ကွက်လပ်တွေကို ဖြည့်ပါ:

public void addToEnd(String data) {
    Node newNode = new (data);
    if (head == null) {
        head = newNode;
        return;
    }
    Node current = head;
    while (current. != null) {
        current = current.next;
    }
    current. = newNode;
}

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

ဒီ addToFront method က node အသစ် ထည့်တဲ့အခါ ရှိပြီးသား node အားလုံးကို ပျောက်သွားစေပါတယ်:

1public void addToFront(String data) { 2 Node newNode = new Node(data); 3 head = newNode; 4 newNode.next = head; 5}

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

ဒီ addToEnd method က NullPointerException ဖြစ်စေပါတယ်:

1public void addToEnd(String data) { 2 Node newNode = new Node(data); 3 Node current = head; 4 while (current != null) { 5 current = current.next; 6 } 7 current.next = newNode; 8}

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

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

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

SinglyLinkedList nums = new SinglyLinkedList();
nums.addToFront("20");
nums.addToFront("30");
nums.addToFront("10");
nums.printAll();
System.out.println(nums.size());

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

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

SinglyLinkedList colors = new SinglyLinkedList();
colors.addToEnd("Red");
colors.addToEnd("Green");
colors.addToEnd("Blue");
colors.remove("Green");
colors.printAll();
System.out.println(colors.contains("Green"));

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

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

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

  1. တည်ဆောက်ပြီး print ထုတ်ပါ။ SinglyLinkedList တစ်ခု ဖန်တီးပြီး addToEnd နဲ့ မြို့နာမည် ငါးခု ထည့်ပါ။ ပြီးရင် list ကို ပြဖို့ printAll ကို ခေါ်ပါ။ Output ရဲ့ အစဉ်က ထည့်ခဲ့တဲ့ အစဉ်နဲ့ တူမတူ စစ်ကြည့်ပါ။
  2. Node တွေကို ရေတွက်ပါ။ အပေါ်က size() method ကို မကြည့်ဘဲ list ကို traverse လုပ်ပြီး node တွေကို ရေတွက်တဲ့ ကိုယ်ပိုင် version ကို ရေးပါ။ Element 0 ခု၊ 1 ခု နဲ့ 5 ခု ပါတဲ့ list တွေနဲ့ စမ်းသပ်ပါ။
  3. Head ကို ဖယ်ထုတ်ပါ။ Element သုံးခု ပါတဲ့ list တစ်ခု ဖန်တီးပါ။ Head element ကို ဖယ်ထုတ်ပြီး list ကို print ထုတ်ပါ။ ပြီးရင် head ကို နောက်တစ်ခါ ဖယ်ထုတ်ပြီး list ကို print ထုတ်ပါ။ အဆင့်တိုင်းမှာ output ကို စစ်ကြည့်ပါ။

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

  1. Index နဲ့ ယူပါ။ ပေးထားတဲ့ index (0 ကနေ စရေတွက်) က data ကို return (ရလဒ်အဖြစ် ပြန်ပေး) လုပ်တဲ့ public String get(int index) method ကို ရေးပါ။ Head ကနေ စပြီး list ကို index ကြိမ် traverse လုပ်ပါ။ Index က list ရဲ့ အပိုင်းအခြား ပြင်ပ ရောက်နေရင် null ကို return လုပ်ပါ။
  2. ရှေ့ဆုံးကို ရွှေ့ပါ။ target ပါတဲ့ ပထမဆုံး node ကို ရှာပြီး အဲဒီ node ကိုယ်တိုင်ကို လက်ရှိ နေရာကနေ ဖြုတ်ကာ head အသစ် အဖြစ် ပြန်ချိတ်ပေးတဲ့ public boolean moveToFront(String target) method ကို ရေးပါ (node အသစ် မဖန်တီးပါနဲ့)။ target ကို တွေ့ရင် true ကို return လုပ်ပါ (head ဖြစ်ပြီးသား ဆိုရင်လည်း true ပါပဲ)။ List ထဲမှာ မရှိရင် false ကို return လုပ်ပါ။ အလယ်က node၊ tail၊ head၊ list ထဲမှာ မရှိတဲ့ တန်ဖိုးနဲ့ empty list တို့နဲ့ စမ်းသပ်ပါ။

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

  1. List ကို ပြောင်းပြန် လှန်ပါ။ next reference အားလုံးကို လမ်းကြောင်း ပြောင်းပြီး linked list ကို in place (မူလ list ထဲမှာပဲ) ပြောင်းပြန် လှန်ပေးတဲ့ public void reverse() method ကို ရေးပါ။ prev, current နဲ့ nextNode ဆိုတဲ့ pointer သုံးခုကို သုံးပါ။ ပြောင်းပြန် လှန်ပြီးနောက် tail အဟောင်းက head အသစ် ဖြစ်ရပါမယ်။
  2. အမှားကို ရှာပြီး ဖော်ပြပါ။ သူငယ်ချင်း တစ်ယောက်က “Insertion က O(1) ဖြစ်လို့ linked list တွေက array တွေထက် အမြဲ ပိုကောင်းတယ်” လို့ ပြောပါတယ်။ ဒီပြောဆိုချက်က ဘာကြောင့် လွဲမှားစေနိုင်လဲ ဆိုတာကို ရှင်းပြတဲ့ စာပိုဒ် တစ်ပိုဒ် ရေးပါ။ Array က ပိုကောင်းတဲ့ ရွေးချယ်မှု ဖြစ်မယ့် အခြေအနေ အနည်းဆုံး နှစ်ခုကို time complexity ကို ကိုးကားပြီး ထည့်ရေးပါ။

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

  • အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: What Are ADTs? (ADT ဆိုတာ ဘာလဲ): interface (class တစ်ခု implement လုပ်ရမယ့် method စာရင်း) နဲ့ implementation (တကယ် အလုပ်လုပ်အောင် ရေးထားတဲ့ code) ကွာခြားချက်ကို နားလည်ခြင်း
  • အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: Object References (object reference များ): null၊ aliasing (variable နှစ်ခုက object တစ်ခုတည်းကို ညွှန်းနေခြင်း) နဲ့ reference semantics (object တွေကို reference နဲ့ ကိုင်တွယ်ပုံ)
  • ဆက်စပ် ခေါင်းစဉ်: 1D Arrays (တန်းတစ်တန်းတည်းမှာ စီထားတဲ့ ဒေတာအစု): အစဉ်လိုက် ဒေတာအတွက် static အစားထိုး ရွေးချယ်စရာ
  • နောက်ထပ် လေ့လာမယ့် ခေါင်းစဉ်: Ordered Linked Lists (တန်ဖိုးအလိုက် အစဉ်တကျ စီထားတဲ့ linked list များ): ထည့်တဲ့အခါ sorted (တန်ဖိုးအလိုက် အစဉ်တကျ စီပြီးသား) အစဉ်ကို ထိန်းထားခြင်း