एल्गोरिथ्म्स और डेटा स्ट्रक्चर्स

लिंक्ड लिस्ट (Linked List)

सीक्वेंशियल डेटा के साथ काम करते समय, आम तौर पर हम लिस्ट या ऐरे (array) का इस्तेमाल करते हैं। हालांकि, कुछ परिस्थितियों में लिंक्ड लिस्ट का उपयोग करना तेज़ साबित हो सकता है। ख़ासतौर पर जब प्रोग्राम को बार-बार लिस्ट की शुरुआत में कोई एलिमेंट जोड़ना या हटाना हो, तब लिंक्ड लिस्ट के साथ काम करना अधिक प्रभावी हो सकता है।
लिंक्ड लिस्ट (Linked List) एक बहुत बुनियादी डाटा स्ट्रक्चर है। यह डेटाओं को सूचीबद्ध तरीके से रखती है, उनमें नए एलिमेंट जोड़ती है, और उनकी पहुंच को मैनेज करती है—यह सब कुछ पारंपरिक लिस्ट/ऐरे की तरह ही करती है। लिंक्ड लिस्ट में हम प्रत्येक एलिमेंट को Node कहते हैं, जो अपने अंदर डेटा और अगले Node का संदर्भ (reference) रखता है। एक सिंगली लिंक्ड लिस्ट (singly linked list) में प्रत्येक Node अगली नोड की ओर रिफरेंस रखता है, जबकि अंतिम नोड का रिफरेंस शून्य (null) होता है। साहित्य में सिंगली लिंक्ड लिस्ट के पहले एलिमेंट को हेड (head) और आखिरी एलिमेंट को टेल (tail) कहा जाता है। नीचे दिया गया उदाहरण इसके एक संभावित इम्प्लीमेंटेशन को दिखाता है:
class Node:
    def __init__(self, data):
        self.data = data               # डेटा को सहेज कर रखें
        self.after = None              # अगले एलिमेंट का संदर्भ रखें


class LinkedList:
    def __init__(self):
        self.head = None               # शुरुआत में कोई एलिमेंट नहीं है

    def append(self, data):            # लिस्ट में एक नया एलिमेंट जोड़ें
        new_node = Node(data)          # एक नया नोड बनाएं जिसमें data होगा
        if self.head is None:          # अगर लिस्ट में अभी तक कोई एलिमेंट नहीं है
            self.head = new_node       # हेड को इस नए नोड पर सेट कर दें
            return
        current = self.head            # लिस्ट को हेड से ट्रैवर्स करना शुरू करें
        while current.after:           # जब तक टेल तक नहीं पहुंचते
            current = current.after    # अगले नोड पर जाएँ
        current.after = new_node       # टेल को अपडेट करें और नए नोड से जोड़ दें

    def print(self):                   # लिस्ट के सभी एलिमेंट प्रिंट करें
        current = self.head            # हेड से शुरुआत करें
        while current:                 # जब तक लिस्ट का अंत नहीं आ जाता
            print(current.data, end='\n' if current.after is None else ' --> ')
            current = current.after    # अगले नोड पर जाएँ


names = LinkedList()                   # एक खाली लिंक्ड लिस्ट बनाएं
names.append('Anna')                   # लिस्ट में Anna जोड़ें
names.append('Bob')                    # लिस्ट में Bob जोड़ें
names.append('Sona')                   # लिस्ट में Sona जोड़ें
names.print()                          # Anna --> Bob --> Sona
notion image
इस इम्प्लीमेंटेशन में दो क्लास हैं: Node और LinkedList। Node क्लास में दो ऐट्रिब्यूट होते हैं: data और after। data में नोड का मान (value) रखा जाता है, जबकि after में अगले नोड का संदर्भ रखा जाता है। LinkedList क्लास में एक ऐट्रिब्यूट head होता है, जो लिस्ट के पहले नोड को दर्शाता है। append() मेथड लिस्ट के अंत में एक नया नोड जोड़ने के लिए इस्तेमाल होता है, और print() मेथड लिस्ट के सभी एलिमेंट प्रिंट करने के लिए।

डबल लिंक्ड लिस्ट (Doubly Linked List)

साथ ही, डबल लिंक्ड लिस्ट भी होती हैं, जिनमें हर एलिमेंट के पास अगले और पिछले एलिमेंट का संदर्भ होता है। इसकी मदद से लिस्ट को दोनों दिशाओं में ट्रैवर्स किया जा सकता है।

लिंक्ड लिस्ट का विश्लेषण

लिंक्ड लिस्ट के साथ काम करते समय कुछ ज़रूरी बातों का ध्यान रखना चाहिए:
  • किसी एलिमेंट तक पहुंचने में समय लगता है, क्योंकि आपको उस एलिमेंट तक पहुंचने के लिए लिस्ट को हेड से ट्रैवर्स करना पड़ता है।
  • अगर आपको पता है कि किस Node के बाद नया एलिमेंट डालना है, तो यह ऑपरेशन समय में हो सकता है, क्योंकि बस आस-पास के एलिमेंट के संदर्भ अपडेट करने होते हैं।
  • अगर आपको पता है कि कौन-सा Node हटाना है, तो उसे हटाने में भी समय लगता है, क्योंकि फिर केवल पड़ोसी नोड के संदर्भ बदले जाते हैं।
  • लिंक्ड लिस्ट में, ऐरे की तुलना में हर एलिमेंट एक अतिरिक्त संदर्भ रखता है, जिससे मेमोरी उपयोग बढ़ जाता है।

चुनौती

मान लीजिए आपके पास n क्वेरीज हैं, जिन्हें आपको निष्पादित करना है। इन क्वेरीज के दो प्रकार हैं:
  1. लिस्ट की शुरुआत में कोई संख्या Insert करना।
  1. पूरी लिस्ट को प्रिंट करना।

इनपुट

इनपुट की पहली पंक्ति में एक पूर्णांक n (1 ≤ n ≤ 1000) होता है, जो क्वेरीज की संख्या बताता है।
अगली n पंक्तियों में क्वेरीज होती हैं — print अगर आपको पूरी लिस्ट प्रिंट करनी है, और insert x अगर आपको संख्या x को लिस्ट की शुरुआत में डालना है ( ≤ x ≤ )।

आउटपुट

प्रोग्राम को सभी क्वेरीज सही तरीके से निष्पादित करना चाहिए और लिस्ट की सभी संख्याओं को स्पेस से अलग करके प्रिंट करना चाहिए।

Examples

Input
Output
6 insert 8 print insert 10 insert -2 insert -6 print
8 -6 -2 10 8
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue