Grounded Header Linked List

Grounded Header Linked List – Header Linked List में एक Special Node होता है, जो कि किसी Linked List की शुरूआत का पहला Node होता है। इस Node को हमेंशा START Point करता है। किसी Header Linked List में Linked List के इस प्रथम Node को Header Node कहते हैं।

इस प्रकार की Linked List तब बहुत उपयोगी होती है जब किसी Information को प्राप्त करने के लिए पूरी Linked List को Traverse करना पडता है। जैसे यदि हमें किसी Linked List के कुल Nodes की संख्‍या ज्ञात करनी हो, तो हमें हर बार पूरी Linked List की Traversing करके कुल Nodes की संख्‍या ज्ञात करनी पडती है।

लेकिन यदि किसी Linked List की Current Nodes की कुल संख्‍या को किसी Additional Header Node द्वारा Maintain किया जाए, तो हम इस Header Node का प्रयोग करके किसी भी समय किसी Linked List के कुल Nodes की संख्‍या ज्ञात कर सकते हैं और इसके लिए हमें पूरी Linked List की Traversing करने की भी जरूरत नहीं होती है। इस स्थिति में हम Header Linked List का प्रयोग कर सकते हैं।

इस Header Linked List के दो रूप होते हैं जिनका सबसे अधिक प्रयोग होता है-

Grounded Header

ये एक ऐसे Linked List होती है जिसमें Linked List के अन्तिम Node में हमेंशा NULL होता है। Grounded शब्द का प्रयोग इसलिए किया जाता है क्योंकि इस Linked List के NULL Pointer को Indicate करने के लिए Electrical Ground Symbol का प्रयोग किया जाता है। हम निम्न चित्र में देख सकते हैं कि इस Linked List के अन्तिम Node में NULL Initialize है जबकि इस Linked List के प्रथम Node को एक START Pointer Point कर रहा है। यदि START[LINK] = NULL हो तो इसका मतलब होता है कि Linked List अभी Empty है।

इस Linked List पर हम निम्न Operations कर सकते हैं-

• Insertion
• Deletion
• Traversing

किसी Grounded Header Linked List को Creation, Traversing व Insertion करने के लिए हम निम्न Algorithms का प्रयोग कर सकते हैं।

[code]
CREATE Header Linked List Algorithm
CREATE_HEADER_LINKED_LIST(LIST, INFO, LINK, START, NEWNODE, ITEM, COUNTER)
    SET NEWNODE = START [ Points to the Header Node ]
    NEWNODE[LINK] = CREATE NEWNODE [ Create Header Node ]
    SET COUNTER = 0 [ Set Counter ]
    REPEAT WHILE Choice <> N
        NEWNODE[LINK] = CREATE NEWNODE
        NEWNODE = NEWNODE[LINK] [ Link Current Node with Next Node ]
        NEWNODE[INFO] = ITEM [ Insert Item in the NEWNODE ]
        NEWNODE[LINK] = NULL [ Make NEWNODE the Last Node of the LIST ]
        COUNTER = COUNTER + 1 
    [ Copy Total Counting of the Nodes into Header Node ]
        NEWNODE = START
        NEWNODE[INFO] = COUNTER
    EXIT 
[/code]

हम देख सकते हैं कि इस Linked List व अभी तक हमने जो Linked List Create की है, दोनों में केवल इतना ही अन्तर है कि इस Linked List में हमनें एक Counter Variable का प्रयोग किया है और हर Node के Creation के साथ ही उस Variable को Increment किया है ताकि हमें पता रहे कि हमारी Linked List में कुल कितने Nodes हैं। इस Counter का प्रयोग करके हम इस Linked List को Efficiently Traverse कर सकते हैं।

[code]
TRAVERSE Header Linked List Algorithm

TRAVERSE_HEADER_LINKED_LIST(LIST, INFO, LINK, START, PTR, COUNT)
SET PTR = START [ Points to the Header Node ]
COUNT = PTR[INFO] [ Read the INFO Part of the Header Node ]
PTR = PTR[LINK] [ Move Pointer from Header Node to First Node of the List ]
REPEAT WHILE COUNT <> 0 [ Traverse the Header Linked List ]
   PROCESS PTR[INFO]
   PTR = PTR[LINK]
   COUNT = COUNT - 1
EXIT 
[code]

इस Algorithm में हम देख सकते हैं कि हमने Header Node में Store की गई कुल Node की संख्‍या का किस प्रकार से प्रयोग किया है। Header Node में Store की गई कुल Nodes की संख्‍या का पता होने से हमारा Traversing का काम कुछ सरल हो गया है। जबकि यदि हम किसी साधारण One – Way Linked List की Traversing करते हैं, तो हमें हर Node के LINK Part को Check करना पडता है, क्योंकि किसी One – Way Linked List का अन्तिम Node वह होता है जिसके LINK Part में NULL Stored हो।

[code]
INSERTION Header Linked List Algorithm

INSERTION_HEADER_LINKED_LIST(LIST, INFO, LINK, START, NEWNODE, ITEM, COUNTER, LOCATION)
SET PTR = START
COUNT = PTR[INFO] [ Process the Header Node ]
PTR = PTR[LINK] [ Move Pointer to First Node of the LIST. ]
COUNTER = 1

REPEAT WHILE PTR <> START [ Traverse through the LOCATION. ]
   IF COUNTER = LOCATION
      CREATE NEWNODE
      NEWNODE[LINK] = PTR[LINK]
      PTR[LINK] = NEWNODE[LINK]
      NEWNODE[INFO] = ITEM
   ELSE
      PTR = PTR[LINK]
      COUNTER = COUNTER + 1
      PTR = START       [ Update Header Node ]
      PTR[INFO] = PTR[INFO] + 1
EXIT 
[/code]

इस Algorithm का प्रयोग करके हम एक Grounded Header Linked List Create करके उसमें किसी Particular Location पर नया Node Create करके Insert कर सकते हैं।