লিংকড লিস্ট (Linked List) একটি লিনিয়ার ডেটা স্ট্রাকচার যেখানে প্রতিটি নোডের দুটি ব্লক থাকে: একটি ব্লকে নোডের ভ্যালু বা ডেটা, অন্যটিতে নেক্সট ফিল্ডের অ্যাড্রেস।
ধরি, একটি লিংকড লিস্ট আছে যেখানে প্রতিটি নোডে একটি র্যান্ডম পয়েন্টার রয়েছে যা লিস্টের অন্যান্য নোডকে পয়েন্ট করে। টাস্ক হলো অরিজিনাল লিস্টের মতোই একটি লিস্ট কনস্ট্রাক্ট করা। র্যান্ডম পয়েন্টারসহ অরিজিনাল লিস্ট থেকে কপি করা কে লিংকড লিস্টের 'ডিপ কপি' (Deep Copy) বলা হয়।
উদাহরণ-১:
ইনপুট-১:
আউটপুট:
5-> 2 -> 3 -> 7 -> 4 ->
ব্যাখ্যা:
যদি অরিজিনাল লিস্টের নোডের ভ্যালু দিয়ে নতুন লিস্টে অ্যাপেন্ড করি এবং অরিজিনাল লিস্টের র্যান্ডম পয়েন্টারকে নতুন লিস্টের নেক্সট নোড দিয়ে রিপ্লেস করি, তবে সেটা হবে 5-> 2-> 3-> 7-> 4->
সমস্যা সমাধানের পদ্ধতি
একটি লিংকড লিস্ট আছে যেখানে নোডে ডেটা ফিল্ড এবং র্যান্ডম পয়েন্টার রয়েছে। ডেটা এবং র্যান্ডম পয়েন্টারসহ লিংকড লিস্টের কপি পেতে প্রথমে অরিজিনাল লিস্টের প্রতিটি নোডের পর aynı ভ্যালুর একটি নতুন নোড ইনসার্ট করব। এতে প্রতিটি নোডের পর ডুপ্লিকেট নোড তৈরি হবে।
ইনিশিয়ালাইজেশনের পর লিস্টে র্যান্ডম পয়েন্টারের পাথ চেক করব এবং নতুন তৈরি নোডে র্যান্ডম পয়েন্টার অনুযায়ী প্লেস করব।
এখন অরিজিনাল লিস্টের প্রতিটি নোডের পর তৈরি নতুন নোডগুলো আলাদা করলে লিংকড লিস্টের ডিপ কপি তৈরি হবে।
ডেটা ফিল্ড এবং র্যান্ডম পয়েন্টারসহ একটি লিংকড লিস্ট নিন।
copyRandomList(listnode* head) ফাংশন অরিজিনাল লিস্টের হেড নোড ইনপুট নেয় এবং লিস্টের ডিপ কপি রিটার্ন করে।
যদি হেড খালি হয়, তবে লিস্ট খালি এবং হেড রিটার্ন করুন।
এখন অরিজিনাল লিস্টের প্রতিটি নোডের পর একই ভ্যালুর নতুন নোড ইনসার্ট করুন।
তারপর অরিজিনাল লিস্ট থেকে র্যান্ডম পয়েন্টার কপি করে নতুন নোডে ইনসার্ট করুন: newnode->next = curr->randomPointer
নতুন নোড পয়েন্টার এবং ডেটাসহ তৈরি হলে লিস্ট আলাদা করে আউটপুট হিসেবে রিটার্ন করুন।
উদাহরণ
class listnode:
def __init__(self, data):
self.data = data
self.next = None
self.random = None
def copyRandomList(head):
if head is None:
return head
# অরিজিনাল লিস্টের প্রতিটি নোডের পর একই ভ্যালুর নতুন নোড ইনসার্ট
curr = head
while curr != None:
new = listnode(curr.data)
new.next = curr.next
curr.next = new
curr = curr.next.next
# নতুন তৈরি নোডে র্যান্ডম পয়েন্টার প্লেস
curr = head
while curr != None:
curr.next.random = curr.random.next
curr = curr.next.next
# নতুন লিস্ট অরিজিনাল থেকে আলাদা
curr = head
temp = head.next
while curr.next != None:
dummyHead = curr.next
curr.next = curr.next.next
curr = dummyHead
return temp
def printList(head):
curr = head
while curr != None:
print(curr.data, "", curr.random.data)
curr = curr.next
head = listnode(1)
head.next = listnode(2)
head.next.next = listnode(3)
head.next.next.next = listnode(4)
head.next.next.next.next = listnode(5)
head.random = head.next.next
head.next.random = head
head.next.next.random = head.next.next.next.next
head.next.next.next.random = head.next.next.next.next
head.next.next.next.next.random = head.next
print("Original list:\n")
printList(head)
copiedList = copyRandomList(head)
print("\n Deep Copy of the List:")
printList(copiedList)
উপরের কোড রান করলে আউটপুট আসবে:
আউটপুট
Original list: 1 3 2 1 3 5 4 5 5 2 Deep Copy of the List: 1 3 2 1 3 5 4 5 5 2
