C++ Linked List Class

C++ Linked List Class: Linked List Data को Store करने का एक और तरीका या Data Structure है। हमने अभी तक कई उदाहरण देखें हैं जिनमें Data को Array या Pointers के Array में Store किया है। Array व Array of Pointers दोनों ही एक ही समस्या से ग्रसित रहते हैं और वह समस्या है Array की Size को Program की शुरूआत में ही Define करना।  Linked List एक ऐसा तरीका है जिसमें हम Exactly उतनी ही Memory को Use करते हैं जितने की हमें जरूरत होती है और हमें Program को पहले से ही ये बताने की जरूरत भी नहीं होती है कि हमें कितना Data Store करना है। यानी Array की तरह इसकी Size Program की शुरूआत में Define करने की जरूरत नहीं होती है।

Linked List हमें एक बहुत ही Flexible Storage System प्रदान करता है, जिसमें Array का प्रयोग नहीं किया जाता है। इस Data Structure में जितने Space की जरूरत होती है, उतना Space new Operator का प्रयोग करके प्राप्त किया जाता है और हर Data Item को दूसरे Data Item से Connected या Linked रखने के लिए एक Pointer का प्रयोग किया जाता है। इस Storage System में कोई भी Data Item Continuous Memory Location पर हो, ये भी जरूरी नहीं होता है जैसाकि Array के सम्बंध में होता है। Array का हर Data Item लगातार Memory Location पर Store होता है। Linked List के Data Items Memory में कहीं भी Store हो सकते हैं और आपस में एक Pointer द्वारा Linked रहते हैं।

हमारे अगले उदाहरण में एक Linked List Class है और हर Data Item या Link या Node को एक link Type के Structure से Represent किया गया है। Link के लिए हम Class का प्रयोग भी कर सकते हैं लेकिन चूंकि link में कोई भी Member Function नहीं है, इसलिए हम Class के स्थान पर link नाम का Structure Create कर रहे हैं। link प्रकार के हर Structure में एक Integer Variable है जो Object के एक Single Data Item को Represent करता है और एक Pointer है जो अगले Node या link को Represent करता है। linklist Object स्वयं एक link Pointer को Store करता है जो कि list का Head होता है। ये Pointer ही इसका Data Item होता है।

linklist Class में Member Functions हैं जो Class User को List में नया link Add करने व सभी Links के Data को Display करने की सुविधा प्रदान करते हैं। हालांकि हमारे उदाहरण में केवल एक ही Data Item है लेकिन Practical उदाहरण में कई Data Items हो सकते हैं। उदाहरण निम्नानुसार है:

	#include <iostream.h>
	#include <conio.h>

	struct link                           	// one element of list
	{
		int data;                          	// data item
		link* next;                        	// pointer to next link
	};

	class linklist                        	// a list of links
	{
		private:
			link* first;                    	// pointer to first link

		public:
			linklist()                      	// no-argument constructor
			{ first = NULL; }            	// no first link yet

			void additem(int d);            	// add data item (one link)
			void display();                 	// display all links
	};

	void linklist::additem(int d)         	// add data item
	{
		link* newlink = new link;          	// make a new link
		newlink->data = d;                 	// give it data
		newlink->next = first;             	// it points to next link
		first = newlink;                   	// now first points to this
	}

	void linklist::display()              	// display all links
	{
		link* current = first;             	// set ptr to first link

		while( current != NULL )           	// quit on last link
		{
			cout << endl << current->data;  	// print data
			current = current->next;        	// move to next link
		}
	}


	void main()
	{
		linklist list;       	// make linked list
		list.additem(25);    	// add four items to list
		list.additem(36);
		list.additem(49);
		list.additem(64);
		list.display();      	// display entire list
		getch();
	}

linklist Class में केवल एक ही Data Item है जो कि list का Start Pointer है। जब List सबसे पहले Create होती है तब Constructor इस First Pointer को Null Initialize करता है। NULL Constant को mem.h नाम की Header file में Define किया गया है इसलिए इस Header File को अपनी Source File में Include करना जरूरी होता है।  ये मान इस बात को Indicate करता है कि Pointer अभी किसी भी link के Valid Address को Point नहीं कर रहा है। इस Program में एक link जिसके next Member में NULL होता है, List के End को Represent करता है।

Program का additem() Member Function Linked List में एक नए Data Item को Add करता है। ये Item Linked List की Beginning में Add होता है। Linked List व ऐसे ही कई और Data Structures के बारे में प;र्ाप्त जानकारी प्राप्त करने के लिए “B with C in Hindi” पुस्तक को पढें। जब हम additem Member Function को Call करते हैं, तब सबसे पहले निम्नानुसार Statement द्वारा structure प्रकार का एक नया link Create होता है:

Link* newlink = new link;

ये Statement एक नए link Structure के लिए Memory Create करता है और Memory के Pointer को newlink में Store कर देता है। फिर हम Create होने वाले नए link Structure को मान प्रदान करते हैं। मान प्रदान करने के लिए हमें Arrow Operator का ही प्रयोग करना पडता है क्योंकि Structure को हम Pointer द्वारा Access कर रहे हैं।  निम्न दो Statements द्वारा additem() Member Function में Argument के रूप में दिया गया मान Data Variable को प्रदान किया जाता है और next Pointer Object first को Point करता है जिसमें Linked List के Start का Address होता है।

newlink->data = d;
newlink->next = first;

अन्त में हम first Variable को नए link को Point करने के लिए निम्नानुसार Assign करते हैं:

first = newlink;

इसका प्रभाव ये होता है कि जो नया link Create होता है, उसे first Pointer Point करने लगता है और पूराने link को इस नए link का next Point करता है।

एक बार जब Linked List Create हो जाती है तब उसके सभी Data को Display करने के लिए हमें केवल next Pointer को Use करना होता है। next Pointer के प्रयोग से हम list के सभी links तक Traversing कर सकते हैं। list के सभी Items को Display करने के लिए हमने display() Member Function Create किया है। list के Current link के Data को Print करने के लिए हमें निम्न Statement Use करना पडता है:

cout << endl << current->data;

और अगले link पर Move करने के लिए हम निम्न Statement का प्रयोग करते हैं:

current = current->next;

हम इस Statement द्वारा अगले link पर तब तक Move करते रहते हैं जब तक कि निम्न Condition सत्य नहीं हो जाती है:

while(current != NULL)

Data को Store करने के लिए Linked List का प्रयोग Arrays के बाद सबसे ज्यादा होता है। इस Data Structure की कमी ये है कि इसमें किसी Data Item को Find करने के लिए भी हमें पूरी Linked List को Traverse करना पडता है। इससे काफी समय व्‍यर्थ होता है। जबकि इसके स्थान पर यदि Array का प्रयोग किया जाता है, तो हम Index Number की मदद से किसी भी Data Item पर तेजी से पहुंच सकते हैं।

इस उदाहरण में हम देख सकते हैं कि हमने Structure में उसी Structure के एक Variable को Pointer के रूप में Use कर लिया है। यही प्रक्रिया हम Classes के साथ भी Use कर सकते हैं। जैसे:

	class sampleclass
	{
	   sampleclass* ptr;  // this is fine
	};

लेकिन हालांकि Class में उसी Class के Type का Pointer to Object Data Member की तरह से Define किया जा सकता है लेकिन Class में उसी Class का Object Define नहीं किया जा सकता है। जैसे:

	class sampleclass
	{
	   sampleclass object;  // it’s not possible
	};

यही बात Structure पर भी लागू होती है। यानी हम Structure में उसी Structure के प्रकार का Pointer तो Define कर सकते हैं, लेकिन उसी Structure का Variable Data Member के रूप में Declare नहीं कर सकते हैं। (C++ Linked List Class – StackExchange)