Link List in Data structure

Array कुछ परिस्थितियों में Data को Store करने के लिए उपयुक्त नहीं है। ऐसी स्थिति में Link List (लिक लिस्ट) का प्रयोग किया जाता है। Link List (लिक लिस्ट) में प्रोग्राम के प्रारंभ में ही list का आकार पता होना आवश्यक नहीं होता है। जैसे-जैसे जरूरत होती है, Link List का आकार बढ़ाया जा सकता है।

Link List (लिंक लिस्ट) में dynamic Memory Allocation (डायनेमिक मैमोरी एलोकेशन) तकनीक को प्रयोग करते हुए List बनाई जाती है। सरल शब्दों में यह कहा जा सकता है कि Link List (लिंक लिस्ट) ऐसा Data Structure (डेटा स्ट्रक्चर) है, जिसमें प्रोग्राम के रन होते समय टुकड़ों में मैमोरी Allocate होती है. और इन सभी टुकड़ों को link करा दिया जाता है।

तकनीकी शब्दों में Link List (लिंक लिस्ट) Nodes (नोड्स) का समूह होती है, जिसमें प्रत्येक Node के दो भाग होते हैं:

1. Data (डेटा)
2. pointer to next node(अगले नोड का एड्रेस )

Data में User द्वारा दी गई सूचनाओं को store किया जाता है जैसे किसी Student का Roll Number, उसका Name , Mobile Number , Class आदि ।

Node के दूसरे भाग pointer to next node में Link List  में मौजूद अगले Node का Address स्टोर किया जाता है। Link List (लिंक लिस्ट) के Last Node पर इस Pointer (पॉइंटर) में null स्टोर करा दिया जाता है जो कि end of link list को प्रदर्शित करता है।

Features of linked list data structure

1.  प्रोग्राम के प्रारंभ में यह ज्ञात होना आवश्यक नहीं कि कितनी मैमोरी की आवश्यकता होगी, अतः Link list Array की कमी को पूरा करती है।
2. प्रोग्राम के रन होने के दौरान आवश्यकतानुसार मैमोरी Allocate करवाई जा सकती है, तथा आवश्यकता नहीं होने पर उसे वापस Free भी किया जा सकता है।
3. जितनी आवश्यकता होती है, उतनी मैमोरी का ही प्रयोग किया जाता है।
4. Link List में नया Data  Insert(इंसर्ट) करना अथवा Data Delete करना आसानी से हो जाता है।
5. चूंकि प्रत्येक Data को स्टोर करवाते समय अगले Data का Link भी स्टोर किया जाता है, अतः मैमोरी का प्रयोग थोड़ा ज्यादा होता है।

linked list and structure

Array कुछ परिस्थितियों में Data को Store करने के लिए उपयुक्त नहीं है। ऐसी स्थिति में Link List (लिक लिस्ट) का प्रयोग किया जाता है। Link List (लिक लिस्ट) में प्रोग्राम के प्रारंभ में ही list का आकार पता होना आवश्यक नहीं होता है। जैसे-जैसे जरूरत होती है, Link List का आकार बढ़ाया जा सकता है।

 Link List (लिक लिस्ट) का प्रयोग Structure (स्ट्रक्चर) की सहायता से किया जाता है। इस Structure  में Data स्टोर करने के लिए आवश्यक Members के अतिरिक्त एक Member (Pointer) ऐसा होता है जो List के अगले Item को Point करता इसीलिए इसे Link List(लिंक लिस्ट) कहा जाता है।

For Example यदि हमें कुछ Employees की Information  स्टोर करनी है तो इसके लिए निम्न प्रकार Structure बनाया जा सकता है:

    struct emp

    {

        int emp_name;

        float salary;

    };

उपरोक्त Structure (स्ट्रक्चर) Link List (लिंक लिस्ट) के लिए पर्याप्त नहीं है। इसमें emp_name तथा salary के अतिरिक्त एक Pointer और होना चाहिए जो अगले Employee के Data को point करते हुए होगा। चूंकि अगले Employee का data भी emp Structure में ही स्टोर करना है, अतः उस Pointer का Data type emp ही होगा।

निम्नांकित Structure में अगले Employee का Link Store करने के लिए ptr_next का प्रयोग किया गया

    struct emp

    {

        int emp_name;

        float salary;

        struct emp *ptr_next;

    };

इस प्रकार Link List(लिंक लिस्ट) को Graphical रूप में निम्न प्रकार दर्शाया जा सकता है। 

इस प्रकार प्रोग्राम में जब किसी Employee का Data स्टोर करना हो, उसी समय मैमोरी Allocate  की जा सकती है। चूंकि इस प्रकार प्रत्येक कर्मचारी के लिए अलग-अलग बार मैमोरी Allocate की जाएगी, अतः यह जरूरी नहीं है कि सभी Employees का Data मैमोरी में एक क्रम (contiguous) में ही हो। इसी कारण से प्रत्येक Employee के Data में मौजूद next Pointer अगले Employee के Data ओर Point करते हुए अगले Employee  के Data  तक हमारी पहुंच बना देता है

Type of link List:-

Link list (लिंक लिस्ट) को Link के आधार पर विभिन्न प्रकारों में विभाजित किया जा सकता है। यह विभिन्न प्रकार निम्नानुसार हैं:

Single Link List

इसमें प्रत्येक Node मूल Data के साथ अगले Node का Link स्टोर करता है। इसमें अंतिम Node Null को Point करते हुए होता है। इसे निम्नानुसार दर्शाया जा सकता है:

Circular Link List

इसमें प्रत्येक Node मूल Data के साथ अगले Node का Link स्टोर करता है। इसमें Last Node वापस पहले Node  को Point करते हुए होता है। इसे निम्नानुसार दर्शाया जा सकता है:

Doubly linked list

इसमें प्रत्येक Node मूल Data के साथ अगले Node तथा previous Node का Link स्टोर किया जाता है। एक प्रकार से यह कहा जा सकता है कि इसमें प्रत्येक Node के तीन भाग होते हैं, जिसमें से first तथा Last भाग में क्रमश: previous तथा next Node का Address स्टोर किया जाता है। वहीं बीच वाले भाग में Data स्टोर करवाया जाता है।

इसके प्रथम Node के previous Pointer तथा Last Node के next Pointer में null स्टोर करवाया जाता है। इसे निम्नानुसार दर्शाया जा सकता है:

Doubly Circular Link List

Doubly Link List (डबली लिंक लिस्ट) की जैसे ही इसमें भी प्रत्येक Node मूल Data के साथ अगले Node तथा previous Node का Link स्टोर किया जाता है। किन्तु इसमें first Node वापस Last को तथा Last Node वापस First Node को Point करते हैं। इसे निम्नानुसार दर्शाया जा सकता है:

Link list operations

लिंक लिस्ट पर मुख्यतया निम्नांकित ऑपरेशन किए जा सकते हैं:

1. Data insert: List में insert किया जाने वाला New Data (Node) निम्नानुसार अलग-अलग Position पर जोड़ा जा सकता है:

• at the beginning of the list
• At the End of the list
• Before any value in the list
• After any value in the list

Traversal : Traversal (ट्रावर्जल) शब्द travel से बना है, जिसका अर्थ होता है- घूमना। दी गई List के प्रत्येक Node को At Least  एक बार access करने की प्रक्रिया को Traversal (ट्रावर्जल)कहा जाता है।

Searching: दी गई List में से इच्छित Data की उपस्थिति का पता लगाना Searching (सर्चिंग) कहलाता है। Searching (सर्चिंग) में यह पता लगाया जाता है कि Search किया जाने वाला Data लिस्ट में किस Position (पोज़िशन) पर है। यह Position (पोज़िशन) User को बता दी जाती है। यदि Data लिस्ट में नहीं मिलता है तो इसकी सूचना भी User को दी जाती है।

Deletion: Deletion (डिलीशन) से आशय दी गई लिस्ट से किसी Data को Delete से है। हटाए जाने वाला एलीमेंट भी लिस्ट के प्रारंभ, अंत अथवा किसी अन्य Position (पोज़िशन) पर हो सकता है।

Inserting data in the linked list

Node को represent के लिए C Language में Structure  का प्रयोग किया जा सकता है, Link List (लिंक लिस्ट) को प्रारंभ में खाली माना जा सकता है। ऐसी स्थिति में Link List (लिंक लिस्ट) का Pointer  Null वैल्यू को Point करते हुए होता है। जैसे ही list में कोई Node(नोड) Insert (इंसर्ट) किया जाता है तो ptr Pointer (पॉइंटर) प्रथम Node को Point करने लगता है।

माना कि List प्रारंभ में खाली है, अतः प्रारंभिंग pointer null को Point करेगा। 

ptr → Null

अब List में नए Employee का Data Insert करवाना है, अतः इसके लिए Memory (मैमोरी) Allocate (एलोकेट) करवाई जाएगी। Memory Allocate सफलतापूर्वक होने पर ptr पॉइंटर में उसका Address Store कर दिया जाएगा। अंत में उस स्थान पर नया Data (Mukesh) स्टोर कर दिया जाएगा, तथा New Node के ptr->next पर null स्टोर करवा दिया जाएगा। इसे निम्नानुसार प्रदर्शित किया जा सकता है:

अब List में वापस नए Employee का Data Insert करवाना है, अतः इसके लिए Memory (मैमोरी) Allocate (एलोकेट) करवाई जाएगी। Memory Allocate सफलतापूर्वक होने पर Mukesh के ptr->next पर New Allocation का Address स्टोर कर दिया जाएगा। अंत में New Node पर New Data (Nirma) Store कर दिया जाएगा तथा इस New Node के ptr>next पर null स्टोर करवा दिया जाएगा। इसे निम्नानुसार प्रदर्शित किया जा सकता है.

इस प्रकार ptr से Start होने वाली Link List (लिंक लिस्ट) में और भी New Node Insert किए जा सकते हैं। इस प्रकार यह कहा जा सकता है कि Link List (लिंक लिस्ट) बनाने की प्रक्रिया निम्नानुसार होती है:

1. New Node के लिए Memory Allocate करवाइए, तथा यह check कि क्या Memory वास्तव में Allocate हो चुकी है।
2. Allocated Memory Location पर Data स्टोर करवाइए
3. यदि Next Node स्टोर करना हो तो उसके लिए वापस step 1 पर जाइए ।
4. यदि Next Node  स्टोर नहीं करना हो तो प्रक्रिया समाप्त कीजिए ।

Algorithm to insert node at the end of linked list

इस Algorithm (एल्गोरिद्म) में List के End  में New Data Insert करवाया जा रहा है

Algorithm 

*PTR :     start of link list
ITEM :     new data to be added

Insert_Node_after(*PTR, ITEM)

Step 1	// initialization       Node * TEMPNODE
Step 2	// allocation memory for new node       TEMPNODE = memory_alloc(NODE)     if(TEMPNODE = NULL) then         print"Insufficient Memory"         return     end if
Step 3	// storing data and making new node to point to NULL     TEMPNODE->DATA = ITEM     TEMPNODE->NEXT = NULL
Step 4	//Pointing ptr to last node     while(PTR->Next != NULL) repeat         PTR = PTR->NEXT     end while
Step 5	// Placing Node at end of list     PTR->NEXT = TEMPNODE
Step 6	return

Sort Example:-

    void insert_End(struct node *str, int val)

    {

        struct node *tempNode;

        tempNode = (struct node *)malloc(sizeof(struct node));

        tempNode->data = val;           // Store data no New NODE

        tempNode->link = NULL;          // as new NODE will be placed at end-of-list    

        while (str->link != NULL)        // Position ptr to last NODE

        {

            str = str->link;

        }

        str->link = tempNode;

    }

Example:-

    #include <stdio.h>

    #include <conio.h>

    #include <malloc.h>

    struct node

    {

        int data;

        struct node *link;

    };

    // declearation

    void insert_End(struct node *str, int val);

    void travel(struct node *str);

    void main()

    {

        int num = 4, num2;

        struct node *list;

        list = (struct node *)malloc(sizeof(struct node));

        list->data = num;

        list->link = NULL;

        for (int i = 1; i < 6; i++)

        {

            ;

            insert_End(list, num + num * i);

        }

        printf("\nBefore Insertion(At last Position) Linked list : ");

        travel(list);

        printf("\nEnter a Data in new Node : ");

        scanf("%d", &num2);

        insert_End(list, num2);

        printf("\nAfter Insertion(At last Position) Linked list : ");

        travel(list);

    }

    // create a liked list

    void insert_End(struct node *str, int val)

    {

        struct node *tempNode;

        tempNode = (struct node *)malloc(sizeof(struct node));

        tempNode->data = val;     // Store data no New NODE

        tempNode->link = NULL;    // as new NODE will be placed at end-of-list              

        while (str->link != NULL) // Position ptr to last NODE

        {

            str = str->link;

        }

        str->link = tempNode;

    }

    // traversion

    void travel(struct node *str)

    {

        while (str->link != NULL)

        {

            printf("\n%d ", str->data);

            str = str->link;

        }

        printf("\n%d \n\n", str->data);

    }

   

Output:-

Before Insertion(At last Position) Linked list : 
4 
8 
12 
16 
20 
24 

Enter a Data in new Node : 123
After Insertion(At last Position) Linked list :
4
8
12
16
20
24
123

Algorithm for link list traversal

*PTR :     started point of Link List

Traverse_list(*PTR)

Step 1	// initialization a temprary pointer       TEMP = PTR
Step 2	// check list     if(TEMP = NULL) then         print"Link list is empty"         return     end if
Step 3	while(TEMP != NULL) repeat         Print (TEMP -> DATA)         TEMP = TEMP->NEXT     end while
Step 4	return

Example 

    // traversion of Link List

    void Traverse_list(struct node *ptr)

    {

        while (ptr->next != NULL)

        {

            printf("\n%d ", ptr->data);

            ptr = ptr->next;

        }

        printf("\n%d \n\n", ptr->data);

    }

Algorithm to insert node at the Beginning of linked list

इस Algorithm (एल्गोरिद्म) में List के Start में New Data Insert करवाया जा रहा है

Algorithm 

*PTR :     start of link list
ITEM :     new data to be added

Insert_Node_beg(*PTR, ITEM)

Step 1	// initialization       Node * TEMPNODE
Step 2	// allocation memory for new node       TEMPNODE = memory_alloc(NODE)     if(TEMPNODE = NULL) then         print"Insufficient Memory"         return     end if
Step 3	// storing data and making new node to point to NULL     TEMPNODE->DATA = ITEM     TEMPNODE->NEXT = PTR
Step 4	return(TEMPNODE)

Sort Example:-

    struct node *Insert_Node_beg(struct node *ptr, int Item)

    {

        struct node *TempNode;

        TempNode = (struct node *)malloc(sizeof(struct node));

        TempNode->data = Item;

        TempNode->link = ptr;

        return TempNode;

    }

Example:-

    #include <stdio.h>

    #include <conio.h>

    #include <malloc.h>

    struct node

    {

        int data;

        struct node *link;

    };

    // declearation

    void insertDatav(struct node *ptr, int Item);

    struct node *Insert_Node_beg(struct node *ptr, int Item);

    void travel(struct node *ptr);

    void main()

    {

        int num = 4, num2;

        struct node *list;

        list = (struct node *)malloc(sizeof(struct node));

        list->data = num;

        list->link = NULL;

        for (int i = 1; i < 6; i++)

        {

            ;

            insertDatav(list, num + num * i);

        }

        printf("\nBefore Insertion(At Frist Position) Linked list : ");

        travel(list);

        printf("\nEnter a Data in new Node : ");

        scanf("%d", &num2);

        list = Insert_Node_beg(list, num2);

        printf("\nAfter Insertion(At Frist Position) Linked list : ");      

        travel(list);

    }

    // create a liked list

    void insertDatav(struct node *ptr, int Item)

    {

        struct node *TempNode;

        TempNode = (struct node *)malloc(sizeof(struct node));

        TempNode->data = Item;

        TempNode->link = NULL;

        while (ptr->link != NULL)

        {

            ptr = ptr->link;

        }

        ptr->link = TempNode;

    }

    // Insert Node at the Begnning

    struct node *Insert_Node_beg(struct node *ptr, int Item)

    {

        struct node *TempNode;

        TempNode = (struct node *)malloc(sizeof(struct node));

        TempNode->data = Item;

        TempNode->link = ptr;

        return TempNode;

    }

    // traversion

    void travel(struct node *ptr)

    {

        while (ptr->link != NULL)

        {

            printf("\n%d ", ptr->data);

            ptr = ptr->link;

        }

        printf("\n%d \n\n", ptr->data);

    }

Output:-

Before Insertion(At Frist Position) Linked list : 
4 
8 
12 
16 
20 
24 

Enter a Data in new Node : 2917
After Insertion(At Frist Position) Linked list : 
2917 
4 
8 
12 
16 
20 
24 

Algorithm to insert node at the Position of linked list

इस Algorithm (एल्गोरिद्म) में List के Start में New Data Insert करवाया जा रहा है

Algorithm 

*PTR :     start of link list
*REFER : reference of ptr
IND     :     Index Number
ITEM :     new data to be added

struct node *dataInsertAtIndex(*PTR, ITEM, IND)

Step 1	// initialization       Node * TEMPNODE  // New Node for  Insert     Node * REFER    //for Reference
Step 2	// allocation memory for new node and Reference Node       TEMPNODE = memory_alloc(NODE)     REFER = memory_alloc(NODE)     if(TEMPNODE = NULL || REFER = NULL ) then         print"Insufficient Memory"         return     end if
Step 3	REFER = PTR
Step 4	// storing data and making new node to point to NULL     TEMPNODE->DATA = ITEM
Step 5	TEMPNODE->NEXT = REFER->NEXT;     REFER->NEXT = TEMPNODE;
Step 6	return PTR

Sort Example:-

    struct node *dataInsertAtIndex(struct node *ptr, int Item, int index)

    {

        struct node *tempNode;

        struct node *Refer;

        tempNode = (struct node *)malloc(sizeof(struct node));

        Refer = (struct node *)malloc(sizeof(struct node));

        Refer = ptr;

        tempNode->data = Item;

        int i = 0;

        while (i < index - 1)

        {

            Refer = Refer->Next;

            i++;

        }

        tempNode->Next = Refer->Next;

        Refer->Next = tempNode;

        return ptr;

    }

Example:-

    #include <stdio.h>

    #include <conio.h>

    #include <malloc.h>

    struct node

    {

        int data;

        struct node *Next;

    };

    // random data insertion

    void insertionData(struct node *ptr, int Item)

    {

        struct node *tempNode;

        tempNode = (struct node *)malloc(sizeof(struct node));

        tempNode->data = Item;

        tempNode->Next = NULL;

        while (ptr->Next != NULL)

        {

            ptr = ptr->Next;

        }

        ptr->Next = tempNode;

    }

    // data traversion

    void traversion(struct node *ptr)

    {

        while (ptr->Next != NULL)

        {

            printf("\n%d", ptr->data);

            ptr = ptr->Next;

        }

        printf("\n%d\n\n", ptr->data);

    }

    struct node *dataInsertAtIndex(struct node *ptr, int Item, int index)

    {

        struct node *tempNode;

        struct node *Refer;

        tempNode = (struct node *)malloc(sizeof(struct node));

        Refer = (struct node *)malloc(sizeof(struct node));

        Refer = ptr;

        tempNode->data = Item;

        int i = 0;

        while (i < index - 1)

        {

            Refer = Refer->Next;

            i++;

        }

        tempNode->Next = Refer->Next;

        Refer->Next = tempNode;

        return ptr;

    }

    void main()

    {

        struct node *list;

        int Item, ind;

        list = (struct node *)malloc(sizeof(struct node));

        list->data = 5;

        list->Next = NULL;

        for (int i = 1; i < 6; i++)

        {

            insertionData(list, i * 3 + 5);

        }

        traversion(list);

        printf("\nEnter New Element in Array : ");

        scanf("%d", &Item);

        printf("Enter New Element's Position in Array : ");

        scanf("%d", &ind);

        list = dataInsertAtIndex(list, Item, ind);

        traversion(list);

    }

Output:-

5
8
11
14
17
20

Enter New Element in Array : 2917
Enter New Element's Position in Array : 2

5
8
2917
11
14
17
20

Algorithm for searching Node in Linked List

*PTR   :     Start Link list
ITEM   :     Searching item

Step 1	if(PTR = NULL) then         Print "Link list is empty"         return(NULL)     end if
Step 2	while(PTR != NULL) repeat step 3 and 4
Step 3	if(PTR->DATA = item) then         Print "item Found"         return (PTR) // Stop the searching proccess & return.     end if
Step 4	PTR = PTR->NEXT     //forwarding ptr not found       end while           // goto step 2
Step 5	//if this line executes, means item not found     print "Item not Found"
Step 6	// NULL Indicate failure     return (NULL)

Example:-

    // Searching node form link list

    struct node *searching_node(struct node *ptr, int Item)

    {

        while (ptr != NULL)

        {

            if (ptr->data == Item)

            {

                printf("\nItem Found : ");

                return (ptr);

            }

            ptr = ptr->link;

        }

        // if following line  exucute means, item note found

        // therwise in above loop it will return back to main().

        printf("\nItem not found.");

        return (NULL);

    }