Doubly Linked Lists (နှစ်ဘက်လုံး ချိတ်ဆက်ထားတဲ့ linked list များ)
B4.1.2, B4.1.3 (HL): Evaluate linked lists: singly, doubly, circular. Construct and apply linked lists.
မြန်မာလို: linked list (node တွေ ချိတ်ဆက်ထားတဲ့ list) အမျိုးအစား သုံးမျိုး ဖြစ်တဲ့ singly linked list (တစ်ဘက်တည်း ချိတ်ဆက်ထားတဲ့ linked list)၊ doubly linked list (နှစ်ဘက်လုံး ချိတ်ဆက်ထားတဲ့ linked list) နဲ့ circular linked list (အဆုံးကနေ အစကို ပြန်ချိတ်ထားတဲ့ linked list) တွေကို အားသာချက်နဲ့ အားနည်းချက်တွေ ချိန်ဆပြီး အကဲဖြတ်နိုင်ရပါမယ်။ Linked list တွေကို ကိုယ်တိုင် တည်ဆောက်ပြီး အသုံးချနိုင်ရပါမယ်။
ဒီစာမျက်နှာက HL အတွက်ပဲ ဖြစ်ပါတယ်။ SL (Standard Level) နဲ့ HL (Higher Level) ဆိုတာ IB Computer Science (နိုင်ငံတကာ ကျောင်းတွေမှာ သင်တဲ့ ကွန်ပျူတာသိပ္ပံ သင်ရိုး) သင်တန်းရဲ့ အဆင့်နှစ်ဆင့်ဖြစ်ပြီး HL အပိုင်းတွေက ပိုနက်နက်ရှိုင်းရှိုင်း လေ့လာရတဲ့ အပိုင်းတွေပါ။
အဓိက အယူအဆများ
Doubly linked list ဆိုတာ node (ဒေတာ သိမ်းထားတဲ့ အကွက်) တစ်ခုစီမှာ reference (object ရှိရာ memory နေရာကို ညွှန်းတဲ့ တန်ဖိုး) နှစ်ခု ပါတဲ့ linked list ပါ: တစ်ခုက next node (နောက်မှာ ရှိတဲ့ node) ကို ညွှန်းပြီး နောက်တစ်ခုက previous node (ရှေ့မှာ ရှိတဲ့ node) ကို ညွှန်းပါတယ်။ ဒါကြောင့် traversal (node တိုင်းကို အစဉ်တကျ သွားကြည့်ခြင်း) ကို ဦးတည်ချက် နှစ်ဘက်လုံး လုပ်လို့ရပါတယ်: forward (ရှေ့ဆက်၊ ပထမ node ကနေ နောက်ဆုံး node ဆီ) ရော backward (နောက်ပြန်၊ နောက်ဆုံး node ကနေ ပထမ node ဆီ) ပါ။
Doubly Linked Node (နှစ်ဘက်လုံး ချိတ်ထားတဲ့ node)
public class DNode {
String data;
DNode next;
DNode prev;
public DNode(String data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
class DNode():
def __init__(self, data):
self.data = data # value stored in the node
self.next = None # no next node yet (None is Python's null)
self.prev = None # no previous node yet
အခု node တစ်ခုစီမှာ အရာ သုံးခု သိမ်းပါတယ်: ဒေတာ၊ နောက်က node ကို ညွှန်းတဲ့ forward reference (next) နဲ့ ရှေ့က node ကို ညွှန်းတဲ့ backward reference (prev) တို့ပါ။
Head and Tail (list ရဲ့ ရှေ့ဆုံး node နဲ့ နောက်ဆုံး node)
Doubly linked list တစ်ခုမှာ များသောအားဖြင့် head (list ရဲ့ ရှေ့ဆုံး node) reference ရော tail (list ရဲ့ နောက်ဆုံး node) reference ပါ နှစ်ခုလုံးကို သိမ်းထားပါတယ်:
head.prevက အမြဲnull(ဘာ object ကိုမှ မညွှန်းတဲ့ တန်ဖိုး) ဖြစ်ပါတယ် (ပထမ node ရဲ့ ရှေ့မှာ ဘာမှ မရှိလို့ပါ)tail.nextက အမြဲnullဖြစ်ပါတယ် (နောက်ဆုံး node ရဲ့ နောက်မှာ ဘာမှ မရှိလို့ပါ)- List အလွတ်မှာ
headရောtailပါnullဖြစ်ပါတယ်
Node တစ်ခုစီက prev၊ data နဲ့ next ဆိုတဲ့ အပိုင်း သုံးပိုင်းပါတဲ့ အကွက်ပါ။ ဘေးချင်းကပ် node တွေကြားမှာ မြှားတွေက နှစ်ဘက်လုံး ညွှန်းထားပါတယ်။
Singly Linked နဲ့ Doubly Linked List နှိုင်းယှဉ်ချက်
| အချက် | Singly linked | Doubly linked |
|---|---|---|
| Node တစ်ခုစီမှာ ပါတဲ့ reference | 1 (next) | 2 (next + prev) |
| Node တစ်ခုစီ သုံးတဲ့ memory | နည်းတယ် (reference တစ်ခု) | ပိုများတယ် (reference နှစ်ခု) |
| ရှေ့ဆက် traverse လုပ်ခြင်း | ရတယ် | ရတယ် |
| နောက်ပြန် traverse လုပ်ခြင်း | မရဘူး | ရတယ် |
| ပေးထားတဲ့ node တစ်ခုကို ဖျက်ခြင်း | Predecessor (ရှေ့မှာ ရှိတဲ့ node) လိုတယ်: ရှာဖို့ O(n) | prev ကနေ predecessor ကို ရတယ်: O(1) |
| ပေးထားတဲ့ node ရဲ့ ရှေ့မှာ ထည့်ခြင်း | Predecessor လိုတယ်: ရှာဖို့ O(n) | prev ကနေ predecessor ကို ရတယ်: O(1) |
| အဆုံးမှာ ထည့်ခြင်း | Tail reference မရှိရင် O(n) | Tail reference ရှိရင် O(1) |
| Implementation (code ရေးပုံ) ရဲ့ ရှုပ်ထွေးမှု | ပိုရိုးရှင်းတယ် | Operation တစ်ခုစီမှာ update လုပ်ရမယ့် pointer (reference ကို ခေါ်တဲ့ နောက်နာမည်တစ်ခု) ပိုများတယ် |
အဓိက အားသာချက်က bidirectional traversal (ရှေ့ဆက်ရော နောက်ပြန်ပါ သွားကြည့်နိုင်ခြင်း) နဲ့ node ကို ညွှန်းထားတဲ့ reference ရှိပြီးသားဆိုရင် ရနိုင်တဲ့ O(1) deletion (list ဘယ်လောက် ရှည်ရှည် အချိန် ပုံသေနဲ့ ဖျက်နိုင်ခြင်း) ပါ။ Trade-off (တစ်ခု ရဖို့ တစ်ခု အလျှော့ပေးရတာ) ကတော့ node တစ်ခုစီမှာ memory ပိုသုံးရတာနဲ့ insertion (ထည့်ခြင်း) နဲ့ deletion (ဖျက်ခြင်း) လုပ်တဲ့အခါ update လုပ်ရမယ့် pointer ပိုများတာပါ။
Circular Linked Lists (အဆုံးကနေ အစကို ပြန်ချိတ်ထားတဲ့ linked list များ)
Circular linked list ဆိုတာ tail ရဲ့ next က null အစား head ကို ပြန်ညွှန်းထားတဲ့ linked list ပုံစံ တစ်မျိုးပါ။ Circular doubly linked list မှာဆိုရင် head ရဲ့ prev ကလည်း tail ကို ညွှန်းပါတယ်။ Circular list တွေက round-robin scheduling (အလှည့်ကျ အချိန်ပေးတဲ့ scheduling) နဲ့ playlist ကို အဆုံးကနေ အစ ပြန်ပတ်ဖွင့်တာမျိုးတွေအတွက် အသုံးဝင်ပါတယ်။
ပုံထဲက Circular, singly linked ဆိုတာ singly linked ဖြစ်တဲ့ circular list၊ Circular, doubly linked ဆိုတာ doubly linked ဖြစ်တဲ့ circular list လို့ ဆိုလိုပါတယ်။
ဒီစာမျက်နှာက circular မဟုတ်တဲ့ doubly linked list တွေကို အဓိက လေ့လာပါတယ်။ Circular ပုံစံမှာ node ဖွဲ့စည်းပုံ အတူတူပဲ သုံးပေမယ့် list အဆုံးကို စစ်တဲ့ condition (မှန်လား မှားလား စစ်တဲ့ အခြေအနေ) တွေ အလုပ်လုပ်ပုံ ပြောင်းသွားပါတယ်။
အဆင့်ဆင့် ရှင်းပြထားတဲ့ ဥပမာများ
ဥပမာ 1: Doubly linked list တစ်ခု တည်ဆောက်ခြင်း
public class DoublyLinkedList {
private DNode head;
private DNode tail;
public DoublyLinkedList() {
head = null;
tail = null;
}
// Add to the front
public void addToFront(String data) {
DNode newNode = new DNode(data);
if (head == null) {
head = newNode;
tail = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
}
// Add to the end
public void addToEnd(String data) {
DNode newNode = new DNode(data);
if (tail == null) {
head = newNode;
tail = newNode;
} else {
newNode.prev = tail;
tail.next = newNode;
tail = newNode;
}
}
// Print forward: head to tail
public void printForward() {
DNode current = head;
while (current != null) {
System.out.print(current.data + " <-> ");
current = current.next;
}
System.out.println("null");
}
// Print backward: tail to head
public void printBackward() {
DNode current = tail;
while (current != null) {
System.out.print(current.data + " <-> ");
current = current.prev;
}
System.out.println("null");
}
public int size() {
int count = 0;
DNode current = head;
while (current != null) {
count++;
current = current.next;
}
return count;
}
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
list.addToEnd("Apple");
list.addToEnd("Banana");
list.addToEnd("Cherry");
System.out.println("Forward:");
list.printForward();
System.out.println("Backward:");
list.printBackward();
System.out.println("Size: " + list.size());
}
}
class DoublyLinkedList():
def __init__(self):
self._head = None # leading underscore = private, like Java's private modifier
self._tail = None
# Add to the front
def add_to_front(self, data):
new_node = DNode(data)
if self._head == None:
self._head = new_node
self._tail = new_node
else:
new_node.next = self._head
self._head.prev = new_node
self._head = new_node
# Add to the end
def add_to_end(self, data):
new_node = DNode(data)
if self._tail == None:
self._head = new_node
self._tail = new_node
else:
new_node.prev = self._tail
self._tail.next = new_node
self._tail = new_node
# Print forward: head to tail
def print_forward(self):
temp = self._head
while temp != None:
print(temp.data + " <-> ", end="")
temp = temp.next
print("null")
# Print backward: tail to head
def print_backward(self):
temp = self._tail
while temp != None:
print(temp.data + " <-> ", end="")
temp = temp.prev
print("null")
def size(self):
count = 0
temp = self._head
while temp != None:
count = count + 1
temp = temp.next
return count
items = DoublyLinkedList() # "list" is a built-in name in Python
items.add_to_end("Apple")
items.add_to_end("Banana")
items.add_to_end("Cherry")
print("Forward:")
items.print_forward()
print("Backward:")
items.print_backward()
print("Size:", items.size())
Output (program က ထုတ်ပြတဲ့ ရလဒ်):
Forward:
Apple <-> Banana <-> Cherry <-> null
Backward:
Cherry <-> Banana <-> Apple <-> null
Size: 3
tail reference ကို သိမ်းထားလို့ addToEnd က O(1) ဖြစ်တာကို သတိပြုပါ: traverse လုပ်စရာ မလိုပါဘူး။
ဥပမာ 2: Doubly linked list ထဲက node ကို ဖျက်ခြင်း
Doubly linked list ရဲ့ အဓိက အားသာချက်က node တစ်ခုကို ညွှန်းထားတဲ့ reference ရှိရင် ဘေးက node တွေရဲ့ pointer တွေကို update လုပ်ရုံနဲ့ အဲဒီ node ကို O(1) နဲ့ ဖယ်ထုတ်နိုင်တာပါ။
// Remove a specific node (given a reference to it)
private void removeNode(DNode node) {
if (node == head && node == tail) {
// Only node in the list
head = null;
tail = null;
} else if (node == head) {
head = head.next;
head.prev = null;
} else if (node == tail) {
tail = tail.prev;
tail.next = null;
} else {
// Middle node: bypass it
node.prev.next = node.next;
node.next.prev = node.prev;
}
}
// Remove first occurrence by value
public boolean remove(String target) {
DNode current = head;
while (current != null) {
if (current.data.equals(target)) {
removeNode(current);
return true;
}
current = current.next;
}
return false;
}
# Remove a specific node (given a reference to it)
# == between two nodes checks "same object", just like Java's reference comparison
def _remove_node(self, node):
if node == self._head and node == self._tail:
# Only node in the list
self._head = None
self._tail = None
elif node == self._head:
self._head = self._head.next
self._head.prev = None
elif node == self._tail:
self._tail = self._tail.prev
self._tail.next = None
else:
# Middle node: bypass it
node.prev.next = node.next
node.next.prev = node.prev
# Remove first occurrence by value
def remove(self, target):
temp = self._head
while temp != None:
if temp.data == target:
self._remove_node(temp)
return True
temp = temp.next
return False
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
list.addToEnd("Red");
list.addToEnd("Green");
list.addToEnd("Blue");
list.addToEnd("Yellow");
System.out.println("Before:");
list.printForward();
list.remove("Green"); // middle
System.out.println("After removing Green:");
list.printForward();
list.remove("Red"); // head
System.out.println("After removing Red:");
list.printForward();
list.printBackward();
}
items = DoublyLinkedList() # "list" is a built-in name in Python
items.add_to_end("Red")
items.add_to_end("Green")
items.add_to_end("Blue")
items.add_to_end("Yellow")
print("Before:")
items.print_forward()
items.remove("Green") # middle
print("After removing Green:")
items.print_forward()
items.remove("Red") # head
print("After removing Red:")
items.print_forward()
items.print_backward()
Output:
Before:
Red <-> Green <-> Blue <-> Yellow <-> null
After removing Green:
Red <-> Blue <-> Yellow <-> null
After removing Red:
Blue <-> Yellow <-> null
Yellow <-> Blue <-> null
removeNode က အခြေအနေ လေးမျိုးကို ကိုင်တွယ်ပုံ:
| အခြေအနေ | လုပ်ဆောင်ချက် |
|---|---|
| List ထဲမှာ node တစ်ခုတည်း ရှိရင် | head နဲ့ tail ကို null လုပ်ပါ |
| Head node | head ကို နောက်က node ဆီ ရွှေ့ပြီး head အသစ်ရဲ့ prev ကို null လုပ်ပါ |
| Tail node | tail ကို ရှေ့က node ဆီ ပြန်ရွှေ့ပြီး tail အသစ်ရဲ့ next ကို null လုပ်ပါ |
| အလယ်က node | Predecessor ကို successor (နောက်မှာ ရှိတဲ့ node) နဲ့ ချိတ်ပြီး successor ကိုလည်း predecessor နဲ့ ပြန်ချိတ်ပါ |
အလယ်က node ကို ဖျက်တဲ့ အခြေအနေ: Green ကို ဖယ်ထုတ်ခြင်း။ အရောင်ခြယ်ထားတဲ့ မျဉ်းကွေးက code line တစ်ကြောင်းစီက ပြောင်းလိုက်တဲ့ pointer ပါ။ Line နှစ်ကြောင်းလုံး run ပြီးရင် Green ကို ဘယ် node ကမှ မညွှန်းတော့လို့ head ကနေ ဖြစ်ဖြစ်၊ tail ကနေ ဖြစ်ဖြစ် ချိတ်ဆက်မှုတွေ အတိုင်း လိုက်သွားရင် Green ကို ကျော်သွားပါတယ်။ Parameter (method ကို ပေးလိုက်တဲ့ တန်ဖိုးကို လက်ခံတဲ့ variable) node က Green ကို ညွှန်းနေတုန်းပေမယ့် Green က list ရဲ့ အစိတ်အပိုင်း မဟုတ်တော့ပါဘူး။
အလယ်က node ကို ဖျက်ရင် pointer နှစ်ခု update လုပ်ရပါတယ်။ အလယ်က node ကို ဖယ်ထုတ်တဲ့အခါ
node.prev.nextရောnode.next.prevပါ နှစ်ခုလုံးကို update လုပ်ရပါမယ်။ တစ်ခုခု ကျန်ခဲ့ရင် ကွင်းဆက် ပြတ်သွားပြီး ဦးတည်ချက် တစ်ဘက်တည်းမှာပဲ မှန်မှန် အလုပ်လုပ်ပါတော့မယ်။
ဥပမာ 3: ပေးထားတဲ့ node ရဲ့ ရှေ့မှာ ထည့်ခြင်း
// Insert a new node before a target value
public void insertBefore(String target, String data) {
DNode current = head;
while (current != null) {
if (current.data.equals(target)) {
if (current == head) {
addToFront(data);
} else {
DNode newNode = new DNode(data);
newNode.next = current;
newNode.prev = current.prev;
current.prev.next = newNode;
current.prev = newNode;
}
return;
}
current = current.next;
}
}
# Insert a new node before a target value
def insert_before(self, target, data):
temp = self._head
while temp != None:
if temp.data == target:
if temp == self._head:
self.add_to_front(data)
else:
new_node = DNode(data)
new_node.next = temp
new_node.prev = temp.prev
temp.prev.next = new_node
temp.prev = new_node
return
temp = temp.next
Singly linked list မှာ ပေးထားတဲ့ node ရဲ့ ရှေ့မှာ ထည့်ဖို့ head ကနေ traverse လုပ်ပြီး predecessor ကို ရှာရပါတယ်: O(n) ပါ။ Doubly linked list မှာတော့ current.prev ကနေ predecessor ကို တိုက်ရိုက် ရနိုင်လို့ ရှာနေတဲ့ node ကို တွေ့ပြီးတာနဲ့ ထည့်တဲ့ အလုပ် ကိုယ်တိုင်က O(1) ပဲ ဖြစ်ပါတယ်။
Red၊ Blue၊ Yellow list ပေါ်မှာ insertBefore("Blue", "Green")insert_before("Blue", "Green") ကို run ပုံပါ။ နံပါတ်တွေက code line လေးကြောင်းနဲ့ ကိုက်ညီပါတယ်: အရင်ဆုံး node အသစ်ရဲ့ ကိုယ်ပိုင် pointer တွေ (1, 2)၊ ပြီးမှ ဘေးက node တွေရဲ့ pointer တွေ (3, 4) ပါ။ အဆင့် 4 ကို အဆင့် 2 မတိုင်ခင် လုပ်မိရင် current.prevtemp.prev က ပြောင်းပြီးသား ဖြစ်နေလို့ newNode.prevnew_node.prev က node အသစ် ကိုယ်တိုင်ကို ညွှန်းသွားပါလိမ့်မယ်။
Quick Check (အမြန် စစ်ဆေးမေးခွန်း)
Q1. Doubly linked list ထဲက node တစ်ခုစီမှာ reference ဘယ်နှစ်ခု ပါသလဲ။
Q2. Circular မဟုတ်တဲ့ doubly linked list မှာ head.prev ရဲ့ တန်ဖိုးက ဘာလဲ။
Q3. Tail reference ကို သိမ်းထားတဲ့ doubly linked list မှာ addToEnd ရဲ့ time complexity (input ကြီးလာရင် ကြာချိန် တိုးပုံ) က ဘာလဲ။
Q4. Singly linked list နဲ့ နှိုင်းယှဉ်ရင် doubly linked list ရဲ့ အဓိက အားနည်းချက်က ဘာလဲ။
Q5. Node ကို ညွှန်းထားတဲ့ reference ရှိပြီးသားဆိုရင် doubly linked list မှာ အဲဒီ node ကို ဖျက်တာ ဘာကြောင့် ပိုမြန်သလဲ။
Trace Exercise (code ကို တစ်ဆင့်ချင်း လိုက်ကြည့်ခြင်း)
အောက်က code ကို trace (တစ်ဆင့်ချင်း လိုက်ကြည့်ပြီး မှတ်) လုပ်ပြီး operation တစ်ခုစီ ပြီးတဲ့အခါ list ရဲ့ အခြေအနေကို ဖြည့်ပါ။
DoublyLinkedList list = new DoublyLinkedList();
list.addToEnd("X");
list.addToEnd("Y");
list.addToFront("W");
list.addToEnd("Z");
list.remove("Y");
items = DoublyLinkedList() # "list" is a built-in name in Python
items.add_to_end("X")
items.add_to_end("Y")
items.add_to_front("W")
items.add_to_end("Z")
items.remove("Y")
ကွက်လပ်တွေမှာ node ရဲ့ တန်ဖိုး (X၊ Y၊ W၊ Z)၊ list တစ်ခုလုံး (ဥပမာ X <-> null) နဲ့ size ကို code ထုတ်ပေးတဲ့ ပုံစံအတိုင်း English လို ရိုက်ထည့်ပါ။
| Operation ပြီးနောက် | head | tail | Forward list (head ကနေ tail အထိ) | size() |
|---|---|---|---|---|
| addToEnd("X") | X <-> null | 1 | ||
| addToEnd("Y") | X | 2 | ||
| addToFront("W") | Y | |||
| addToEnd("Z") | W | W <-> X <-> Y <-> Z <-> null | 4 | |
| remove("Y") | W | Z |
Code Completion (code ကွက်လပ် ဖြည့်ခြင်း)
Doubly linked list အတွက် addToEnd method (သီးခြား အလုပ်တစ်ခု လုပ်ပေးတဲ့ code အပိုင်း) ကို ဖြည့်ပါ။
Node အသစ်ကို list အဆုံးမှာ ချိတ်ဖို့ ကွက်လပ်တွေကို ဖြည့်ပါ:
public void addToEnd(String data) {
DNode newNode = new DNode(data);
if (tail == null) {
head = newNode;
tail = newNode;
} else {
newNode. = tail;
tail. = newNode;
= newNode;
}
}
အလယ်က node ကို ဖယ်ထုတ်တဲ့ code ကို ဖြည့်ပါ (node ကို ဦးတည်ချက် နှစ်ဘက်လုံးမှာ ကျော်သွားအောင် ချိတ်ပါ)။
အလယ်က node တစ်ခုကို ညွှန်းထားတဲ့ reference ကို ပေးထားပါတယ်။ အဲဒီ node ကို ဖယ်ထုတ်ဖို့ ကွက်လပ်တွေကို ဖြည့်ပါ။ Code ထဲက comment က ဒီ node က head လည်း မဟုတ်၊ tail လည်း မဟုတ်ဘူးလို့ ဆိုလိုပါတယ်:
// node is not head or tail
node.prev. = node.next;
node..prev = node.prev;
Spot the Error (အမှား ရှာခြင်း)
ဒီ addToFront method က နောက်ပြန် ကွင်းဆက်ကို ပျက်စေလို့ printBackward မှန်မှန် အလုပ်မလုပ်ပါဘူး:
မှန်ကန်တဲ့ ပြင်နည်းကို ရွေးပါ:
Tail node ကို ဖယ်ထုတ်ပြီးတဲ့နောက် printBackward က node တချို့ ပျောက်နေတဲ့ မပြည့်စုံတဲ့ list ကို ထုတ်ပေးပါတယ်။ Line 1 က tail node ကို ဖယ်ထုတ်နေတယ်လို့ ပြတဲ့ comment ပါ:
Line 3 အတွက် မှန်ကန်တဲ့ ပြင်နည်းကို ရွေးပါ:
Predict the Output (output ကို ကြိုခန့်မှန်းခြင်း)
ဒီ code က ဘာကို print ထုတ်မလဲ။
DoublyLinkedList d = new DoublyLinkedList();
d.addToFront("B");
d.addToFront("A");
d.addToEnd("C");
d.printForward();
d.printBackward();Output ကို အတိအကျ ရိုက်ထည့်ပါ:
ဒီ code က ဘာကို print ထုတ်မလဲ။
DoublyLinkedList d = new DoublyLinkedList();
d.addToEnd("P");
d.addToEnd("Q");
d.addToEnd("R");
d.addToEnd("S");
d.remove("Q");
d.remove("S");
System.out.println(d.size());
d.printForward();Output ကို အတိအကျ ရိုက်ထည့်ပါ:
Practice Exercises (လေ့ကျင့်ခန်းများ)
Core (အခြေခံ အဆင့်)
- တည်ဆောက်ပြီး နှစ်ဘက်လုံး traverse လုပ်ပါ: Element (အစုထဲက အချက်) 5 ခုပါတဲ့ doubly linked list တစ်ခု ဖန်တီးပါ။ ရှေ့ဆက် (forward) ရော နောက်ပြန် (backward) ပါ print ထုတ်ပါ။ နောက်ပြန် output က ရှေ့ဆက် output ရဲ့ ပြောင်းပြန် ဖြစ်ကြောင်း စစ်ကြည့်ပါ။
- အခြေအနေ အားလုံးမှာ ဖျက်ကြည့်ပါ: Node 4 ခုပါတဲ့ list တစ်ခု ဖန်တီးပါ။ Head၊ အလယ်က node တစ်ခုနဲ့ tail ကို (သီးခြား အဆင့်တွေအဖြစ်) ဖယ်ထုတ်ပါ။ ဖယ်ထုတ်ပြီးတိုင်း list ကို print ထုတ်ပြီး ရှေ့ဆက် traversal ရော နောက်ပြန် traversal ပါ မှန်မှန် အလုပ်လုပ်ကြောင်း စစ်ကြည့်ပါ။
- Size ကို မှတ်ထားခြင်း: ထည့်တိုင်း 1 တိုးပြီး ဖယ်ထုတ်တိုင်း 1 လျော့တဲ့ private
int sizefield (object ထဲက အချက်အလက် အကွက်) တစ်ခု ထည့်ပါ။ Operation တိုင်း ပြီးတဲ့နောက် အဲဒီ တန်ဖိုးက traverse လုပ်ပြီး ရေတွက်တဲ့size()method ရဲ့ ရလဒ်နဲ့ တူကြောင်း စစ်ကြည့်ပါ။
Extension (တိုးချဲ့ အဆင့်)
- Index နေရာမှာ ထည့်ခြင်း: ပေးထားတဲ့ နေရာမှာ node အသစ် ထည့်ပေးတဲ့
public void insertAt(int index, String data)method ကို ရေးပါ။ Index (နေရာအမှတ်) ကို 0 ကနေ စရေတွက်ပါ။ နေရာကို တွေ့ပြီးတာနဲ့prevpointer ကို သုံးပြီး ထိထိရောက်ရောက် ထည့်ပါ။ - Palindrome (ရှေ့က ဖတ်ဖတ် နောက်က ဖတ်ဖတ် တူတဲ့ အစဉ်) စစ်ခြင်း: List ကို ရှေ့ကနေ ဖတ်ဖတ်၊ နောက်ကနေ ဖတ်ဖတ် တူမတူ စစ်ပေးတဲ့
public boolean isPalindrome()method ကို ရေးပါ။ Head နဲ့ tail ကနေ စပြီး အလယ်ဘက်ကို ရွှေ့သွားတဲ့ pointer နှစ်ခုကို သုံးပါ။
Challenge (စိန်ခေါ်မှု အဆင့်)
- Circular doubly linked list:
tail.nextကheadကို ညွှန်းပြီးhead.prevကtailကို ညွှန်းအောင်DoublyLinkedListclass (object တွေ ဖန်တီးဖို့ ပုံစံခွက်) ကို ပြင်ပါ။addToFront၊addToEndနဲ့printForwardကို update လုပ်ပါ။ Loop က ဘယ်တော့မှ မရပ်တဲ့ infinite loop မဖြစ်အောင် counter (အရေအတွက် မှတ်တဲ့ variable) ဒါမှမဟုတ် ရပ်မယ့် condition တစ်ခုကို သုံးပါ။ Element 4 ခု ထည့်ပြီး ဘယ် node ကနေ စပြီး print ထုတ်ထုတ် မှန်ကြောင်း စမ်းသပ်ပါ။ - ပုံစံ သုံးမျိုးလုံးကို နှိုင်းယှဉ်ပါ: Element 5 ခုစီပါတဲ့ singly linked list၊ doubly linked list နဲ့ circular doubly linked list တစ်ခုစီကို ဖန်တီးတဲ့ program တစ်ခု ရေးပါ။ တစ်ခုစီအတွက် (a) ရှေ့ဆုံးမှာ ထည့်ဖို့၊ (b) အဆုံးမှာ ထည့်ဖို့၊ (c) တတိယ element ကို ဖယ်ထုတ်ဖို့ update လုပ်ရတဲ့ pointer အရေအတွက်ကို ရေတွက်ပါ။ ရလဒ်တွေကို ဇယားနဲ့ ပြပြီး operation တစ်ခုစီအတွက် ဘယ်ပုံစံက အကောင်းဆုံးလဲ ရှင်းပြပါ။
ဆက်စပ် ခေါင်းစဉ်များ
- အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: Linked Lists (node တွေ ချိတ်ဆက်ထားတဲ့ list များ): singly linked list ရဲ့ operation တွေနဲ့ Node class
- ဆက်စပ် ခေါင်းစဉ်: Stacks from Scratch (stack ကို အစကနေ ကိုယ်တိုင် တည်ဆောက်ခြင်း): stack (အပေါ်ကနေပဲ ထည့်၊ ထုတ်တဲ့ အထပ်) ကို doubly linked list နဲ့ တည်ဆောက်လို့ ရပါတယ်
- ဆက်စပ် ခေါင်းစဉ်: Queues from Scratch (queue ကို အစကနေ ကိုယ်တိုင် တည်ဆောက်ခြင်း): doubly linked list နဲ့ဆိုရင် deque (double-ended queue၊ ရှေ့ရော နောက်ပါ ထည့်၊ ထုတ်လို့ရတဲ့ queue) ကို သဘာဝကျကျ တည်ဆောက်နိုင်ပါတယ်
- နောက်ထပ် လေ့လာမယ့် ခေါင်းစဉ်: Stacks from Scratch: node တွေကို သုံးပြီး stack တည်ဆောက်ခြင်း