Two – Way Lists OR Doubly Linked List

Two – Way Lists OR Doubly Linked List – अभी तक हमने जितने भी प्रकार के Linked Lists को समझ है वे सभी One – Way Lists कहलाते हैं क्योंकि इन सभी में Traversing केवल एक ही Node से की जा सकती है। यानी इन सभी में एक Pointer Variable START होता है, जो Header Node को Point करता है और इसके LINK Pointer को Use करके List की Traversing की जाती है। इस List को हम केवल एक ही दिशा से Traverse कर सकते हैं। यानी हम START से शुरू करके Linked List के अन्त तक जा सकते हैं लेकिन किसी Linked List के अन्त से START की तरफ नहीं बढ सकते।

हमने देखा है कि किसी One – Way Linked List में किसी Data Element को Insert करने के लिए हमें दो Pointers को Maintain करना पडता है। पहला वह Pointer जहां पर किसी Node को Insert करना है और दूसरा Current Pointer से पिछले Node का Pointer,  एक One – Way Linear Linked List में किसी Linked List की Traversing केवल एक ही दिशा में सम्भव है।

लेकिन कई बार ऐसी जरूरत पडती है कि हमें Linked List की उल्टी दिशा में चलना पडता है। यदि हमें किसी Linked List में कोई Data Insert करना हो] तो सबसे पहले हमें Linked List के START से Traversing करके उस Location तक पहुंचना पडता है जहां पर किसी Node को Insert करना है। फिर Node को Insert किया जाता है। यदि हमें और Nodes Insert करने हों, तो वापस से हमें START से Traversing करके Required Location तक पहुंच कर नए Node को Insert करना पडता है।

यानी हमें जितने Nodes Insert करने होते हैं, उतनी बार Required Location तक Traversing करनी पडती है। इस प्रक्रिया में Linked List Data Structure की Efficiency प्रभावित होती है।

यदि कोई ऐसी व्‍यवस्था हो जिससे किसी भी नए Node को Insert या Delete करने के लिए हमें Required Location तक पहुंचने के लिए पूरी Linked List की Traversing ना करनी पडे और हम जिस Current Location पर हैं, उसी Location से Forward या Reverse दोनों Direction में Traversing कर सकें, तो हमारे Algorithm की Efficiency बढ सकती है। Doubly Linked List या Two – Way Linked List इसी व्‍यवस्था का एक उदाहरण है। Doubly Linked List एक ऐसी व्‍यवस्था है जिसमें हम किसी भी Data Structure में दोनों दिशाओं में यानी START से Linked List के END तक व Linked List के END से START तक Traversing कर सकते हैं।

Two – Way LIST भी Data Elements का एक Linear Collection होता है, जिसमें हर Node N में दो के बजाय कम से कम तीन Fields होते हैं।

1    INFO Field     इसमें Data की Information होती है।

2    FORW Field     इसमें Current Node से अगले Node का Address होता है।

3    BACK Field इसमें Current Node से पिछले Node का Address होता है।

इस List को दो अन्‍य Pointer Variables FIRST व LAST की जरूरत भी होती है जो कि किसी Linked List के First व Last Node को Point करते हैं। इस प्रकार की Linked List को निम्नानुसार दर्शाया गया है-

इस Linked List को देखने से पता चलता है कि हम FIRST व FORW Pointer Variables का प्रयोग करके इस Linked List की Forward Direction में Traversing कर सकते हैं और LAST व BACK Variables का प्रयोग करके इस Linked List की Backward Direction में Traversing कर सकते हैं। इस Linked List के LEFT Node में X दर्शाता है कि Linked List के LEFT में कोई और Node नहीं है जबकि Right Node का X दर्शाता है कि इस Linked List के Right Side में भी कोई और Node नहीं है। यानी इस Linked List का दोनों दिशाओं में अन्त हो चुका है।

मानलो किसी Node A व B के क्रमश% LOCA व LOCB Locations हैं। इस स्थिति में हम FORW व BACK Pointers को निम्नानुसार Define करके दोनों दिशाओं में Traversing कर सकते हैं-

LOCA[FORW] = LOCB और LOCB[BACK] = LOCA

यदि हमें किसी Linked List की Current Node की Location LOCA से अगले Node की Location LOCB पर जाना हो] तो हम LOCA[FORW] = LOCB कर सकते हैं और यदि हम Current Location LOCB पर हों और हमें पिछली Node की Location LOCA पर जाना हो] तो हम LOCB[BACK] = LOCA कर सकते हैं। किसी Linked List के दोनों दिशाओं को Represent करने के लिए विभिन्न प्रकार के शब्द उपयोग में लिए जाते हैं। जैसे जब किसी Linked List की Traversing START से END की तरफ करते हैं तब Linked List की शुरूआत को FIRST, FORW, FRONT, LEFT, NEXT या SUCCESSOR Node से Represent कर सकते हैं। जबकि यदि किसी Linked List के End से START की तरफ Traversing करनी होती है तब हम Linked List के END को LAST, BACK, REAR, RIGHT, PREVIOUS या PREDECESSOR से Represent करते हैं।