data-structures
लिंक्ड सूची

लिंक्ड सूची का परिचय

एक लिंक की गई सूची डेटा तत्वों का एक रैखिक संग्रह है, जिसे नोड्स कहा जाता है, जो "नोड्टर" के माध्यम से अन्य नोड्स से जुड़े होते हैं। नीचे एक प्रमुख संदर्भ के साथ एक एकल लिंक की गई सूची है।

         ┌─────────┬─────────┐   ┌─────────┬─────────┐         
 HEAD ──▶│  data   │"pointer"│──▶│  data   │"pointer"│──▶ null 
         └─────────┴─────────┘   └─────────┴─────────┘         

कई तरह की लिंक्ड लिस्ट्स हैं, जिनमें सिंगल और डबल लिंक्ड लिस्ट्स और सर्कुलर लिंक्ड लिस्ट्स शामिल हैं।

लाभ

• लिंक्ड लिस्ट एक डायनेमिक डेटा स्ट्रक्चर है, जो प्रोग्राम के चलने के दौरान मेमोरी को बढ़ा और सिकोड़, आवंटित और डीलिट कर सकता है।

• नोड प्रविष्टि और विलोपन कार्यों को आसानी से एक लिंक्ड सूची में लागू किया जाता है।

• लिंक्ड डेटा संरचनाएं जैसे स्टैक और कतारें आसानी से लिंक की गई सूची के साथ कार्यान्वित की जाती हैं।

• लिंक की गई सूची एक्सेस समय को कम कर सकती है और मेमोरी ओवरहेड के बिना वास्तविक समय में विस्तार कर सकती है।

सिंगली लिंक्ड लिस्ट

सिंगली लिंक्ड लिस्ट एक प्रकार की लिंक्ड लिस्ट है । एक एकल लिंक की गई सूची के नोड्स में केवल एक "पॉइंटर" से दूसरे नोड तक, आमतौर पर "अगला" होता है। इसे एक एकल लिंक की गई सूची कहा जाता है क्योंकि प्रत्येक नोड में केवल एक "पॉइंटर" दूसरे नोड के लिए होता है। एक जुड़ी हुई सूची में एक सिर और / या पूंछ संदर्भ हो सकता है। एक पूंछ संदर्भ होने का लाभ getFromBack , addToBack और removeFromBack मामले हैं, जो O (1) बन जाते हैं।

         ┌─────────┬─────────┐   ┌─────────┬─────────┐         
 HEAD ──▶│  data   │"pointer"│──▶│  data   │"pointer"│──▶ null 
         └─────────┴────△────┘   └─────────┴─────────┘         
          SINGLE        │                                      
          REFERENCE ────┘                                                                

C में उदाहरण कोड

उदाहरण के लिए जावा में यूनिट टेस्ट के साथ कोड - प्रमुख संदर्भ के साथ एकल रूप से जुड़ी सूची

XOR लिंक्ड सूची

XOR लिंक्ड लिस्ट को मेमोरी-एफिशिएंट लिंक्ड लिस्ट भी कहा जाता है। यह एक डबल लिंक की गई सूची का दूसरा रूप है। यह XOR लॉजिक गेट और उसके गुणों पर अत्यधिक निर्भर है।

इसे मेमोरी-एफिशिएंट लिंक्ड लिस्ट क्यों कहा जाता है?

इसे इसलिए कहा जाता है क्योंकि यह पारंपरिक रूप से लिंक की गई सूची की तुलना में कम मेमोरी का उपयोग करता है।

क्या यह डबली लिंक्ड लिस्ट से अलग है?

हाँ , यह है।

Doubly-Linked List दो पॉइंटर्स को स्टोर कर रही है, जो अगले और पिछले नोड पर इंगित करते हैं। मूल रूप से, यदि आप वापस जाना चाहते हैं, तो आप back पॉइंटर द्वारा बताए गए पते पर back । यदि आप आगे जाना चाहते हैं, तो आप next पॉइंटर द्वारा बताए गए पते पर जाएं। यह पसंद है:

एक मेमोरी-एफिशिएंट लिंक्ड लिस्ट , या XOR लिंक्ड लिस्ट में दो के बजाय केवल एक पॉइंटर होता है। यह पिछला पता (addr (prev)) XOR (^) अगला पता (addr (अगला)) संग्रहीत करता है। जब आप अगले नोड पर जाना चाहते हैं, तो आप कुछ गणनाएँ करते हैं, और अगले नोड का पता पाते हैं। पिछले नोड पर जाने के लिए यह समान है। जैसे की:

यह कैसे काम करता है?

यह समझने के लिए कि लिंक की गई सूची कैसे काम करती है, आपको XOR (^) के गुणों को जानना होगा:

|-------------|------------|------------|
|    Name     |   Formula  |    Result  |
|-------------|------------|------------|
| Commutative |    A ^ B   |    B ^ A   |
|-------------|------------|------------|
| Associative | A ^ (B ^ C)| (A ^ B) ^ C|
|-------------|------------|------------|
| None (1)    |    A ^ 0   |     A      |
|-------------|------------|------------|
| None (2)    |    A ^ A   |     0      |
|-------------|------------|------------|
| None (3)    | (A ^ B) ^ A|     B      |
|-------------|------------|------------|

अब इसे एक तरफ छोड़ दें, और देखें कि प्रत्येक नोड स्टोर क्या है।

पहला नोड या सिर , 0 ^ addr (next) को संग्रहीत करता है क्योंकि कोई पिछला नोड या पता नहीं है। ऐसा लग रहा है इस ।

फिर दूसरा नोड स्टोर addr (prev) ^ addr (next) । ऐसा लग रहा है इस ।

सूची की पूंछ में कोई अगला नोड नहीं है, इसलिए यह addr (prev) ^ 0 संग्रहीत करता है। ऐसा लग रहा है इस ।

सिर से अगले नोड तक बढ़ रहा है

मान लें कि आप अब पहले नोड पर हैं, या नोड ए पर। अब आप नोड बी पर जाना चाहते हैं। ऐसा करने के लिए यह सूत्र है:

Address of Next Node = Address of Previous Node ^ pointer in the current Node

तो यह होगा:

addr (next) = addr (prev) ^ (0 ^ addr (next))

जैसा कि यह प्रमुख है, पिछला पता बस 0 होगा, इसलिए:

addr (next) = 0 ^ (0 ^ addr (next))

हम कोष्ठक हटा सकते हैं:

addr (next) = 0 ^ 0 addr (next)

none (2) संपत्ति का उपयोग करते हुए, हम कह सकते हैं कि 0 ^ 0 हमेशा 0 ^ 0 होगा:

addr (next) = 0 ^ addr (next)

none (1) संपत्ति का उपयोग करके, हम इसे सरल कर सकते हैं:

addr (next) = addr (next)

आपको अगले नोड का पता मिल गया है!

एक नोड से अगले नोड तक ले जाना

अब कहते हैं कि हम एक मध्य नोड में हैं, जिसमें एक पिछला और अगला नोड है।

आइए सूत्र लागू करें:

Address of Next Node = Address of Previous Node ^ pointer in the current Node

अब मानों को प्रतिस्थापित करें:

addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))

कोष्ठक निकालें:

addr (next) = addr (prev) ^ addr (prev) ^ addr (next)

none (2) संपत्ति का उपयोग करना, हम सरल कर सकते हैं:

addr (next) = 0 ^ addr (next)

none (1) संपत्ति का उपयोग करना, हम सरल कर सकते हैं:

addr (next) = addr (next)

और आप इसे प्राप्त करें!

एक नोड से उस नोड पर जाना जो आप पहले थे

यदि आप शीर्षक को नहीं समझ रहे हैं, तो इसका मूल रूप से मतलब है कि यदि आप नोड एक्स पर थे, और अब नोड वाई पर चले गए हैं, तो आप पहले देखे गए नोड पर वापस जाना चाहते हैं, या मूल रूप से नोड एक्स।

यह एक बोझिल काम नहीं है। याद रखें कि मैंने ऊपर उल्लेख किया था, कि आप उस पते को संग्रहीत करते हैं जो आप एक अस्थायी चर में थे। तो जिस नोड पर आप जाना चाहते हैं, उसका पता एक चर में पड़ा है:

addr (prev) = temp_addr

एक नोड से पिछले नोड के लिए आगे बढ़ रहा है

यह ऊपर वर्णित के समान नहीं है। मेरे कहने का मतलब है कि, आप नोड Z पर थे, अब आप नोड Y पर हैं, और नोड X पर जाना चाहते हैं।

यह लगभग नोड से अगले नोड पर जाने के समान है। बस यह है कि यह इसके विपरीत है। जब आप कोई प्रोग्राम लिखते हैं, तो आप उन्हीं चरणों का उपयोग करेंगे, जैसा कि मैंने एक नोड से अगले नोड तक ले जाने में उल्लेख किया था, बस आपको अगले तत्व को खोजने की तुलना में सूची में पहले वाला तत्व मिल रहा है।

C में उदाहरण कोड

/* C/C++ Implementation of Memory efficient Doubly Linked List */
#include <stdio.h>
#include <stdlib.h>
 
// Node structure of a memory efficient doubly linked list
struct node
{
    int data;
    struct node* npx;  /* XOR of next and previous node */
};
 
/* returns XORed value of the node addresses */
struct node* XOR (struct node *a, struct node *b)
{
    return (struct node*) ((unsigned int) (a) ^ (unsigned int) (b));
}
 
/* Insert a node at the begining of the XORed linked list and makes the
   newly inserted node as head */
void insert(struct node **head_ref, int data)
{
    // Allocate memory for new node
    struct node *new_node  = (struct node *) malloc (sizeof (struct node) );
    new_node->data = data;
 
    /* Since new node is being inserted at the begining, npx of new node
       will always be XOR of current head and NULL */
    new_node->npx = XOR(*head_ref, NULL);
 
    /* If linked list is not empty, then npx of current head node will be XOR 
       of new node and node next to current head */
    if (*head_ref != NULL)
    {
        // *(head_ref)->npx is XOR of NULL and next. So if we do XOR of 
        // it with NULL, we get next
        struct node* next = XOR((*head_ref)->npx,  NULL);
        (*head_ref)->npx = XOR(new_node, next);
    }
 
    // Change head
    *head_ref = new_node;
}
 
// prints contents of doubly linked list in forward direction
void printList (struct node *head)
{
    struct node *curr = head;
    struct node *prev = NULL;
    struct node *next;
 
    printf ("Following are the nodes of Linked List: \n");
 
    while (curr != NULL)
    {
        // print current node
        printf ("%d ", curr->data);
 
        // get address of next node: curr->npx is next^prev, so curr->npx^prev
        // will be next^prev^prev which is next
        next = XOR (prev, curr->npx);
 
        // update prev and curr for next iteration
        prev = curr;
        curr = next;
    }
}
 
// Driver program to test above functions
int main ()
{
    /* Create following Doubly Linked List
       head-->40<-->30<-->20<-->10   */
    struct node *head = NULL;
    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);
    insert(&head, 40);
 
    // print the created list
    printList (head);
 
    return (0);
}

उपरोक्त कोड दो बुनियादी कार्य करता है: सम्मिलन और ट्रांसवर्सल।

• सम्मिलन: यह फ़ंक्शन insert द्वारा किया जाता है। यह शुरुआत में एक नया नोड सम्मिलित करता है। जब इस फ़ंक्शन को कहा जाता है, तो यह नए नोड को सिर के रूप में डालता है, और पिछले नोड को दूसरे नोड के रूप में।

• ट्रैवर्सल: यह फंक्शन printList द्वारा किया जाता है। यह बस प्रत्येक नोड के माध्यम से जाता है और मूल्य को प्रिंट करता है।

ध्यान दें कि पॉइंटर्स का XOR C / C ++ मानक द्वारा परिभाषित नहीं है। इसलिए उपरोक्त कार्यान्वयन सभी प्लेटफार्मों पर काम नहीं कर सकता है।

संदर्भ

• https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/

• http://www.ritambhara.in/memory-efficient-doubly-linked-list/comment-page-1/

• http://www.geeksforgeeks.org/xor-linked-list-a-memory-efficient-doubly-linked-list-set-2/

ध्यान दें कि मैंने मुख्य पर अपने स्वयं के उत्तर से बहुत सारी सामग्री ली है।

सूची छोड़ें

स्किप लिस्ट जुड़ी हुई लिस्ट हैं जो आपको सही नोड पर जाने की अनुमति देती हैं। यह एक ऐसी विधि है जो सामान्य रूप से जुड़ी हुई सूची की तुलना में अधिक तेज़ है। यह मूल रूप से एक जुड़ी हुई सूची है, लेकिन संकेत एक नोड से अगले नोड तक नहीं जा रहे हैं, लेकिन कुछ नोड्स को छोड़ देते हैं। इस प्रकार नाम "छोड़ें सूची"।

क्या यह एक लिंक्ड लिस्ट से अलग है?

हाँ , यह है।

एक सिंगली लिंक्ड लिस्ट अगले नोड की ओर इशारा करते हुए प्रत्येक नोड के साथ एक सूची है। एक गायन से जुड़ी सूची का चित्रमय प्रतिनिधित्व इस प्रकार है:

एक स्किप सूची एक नोड के साथ इंगित करने वाले प्रत्येक नोड के साथ एक सूची है जो इसके बाद हो सकती है या नहीं। एक स्किप सूची का चित्रमय प्रतिनिधित्व है:

यह कैसे काम करता है?

स्किप लिस्ट सरल है। मान लें कि हम उपरोक्त छवि में नोड 3 तक पहुंचना चाहते हैं। हम तीसरे नोड के बाद सिर से चौथे नोड तक जाने का मार्ग नहीं अपना सकते हैं। तो हम सिर से दूसरे नोड तक जाते हैं, और फिर तीसरे से।

एक चित्रमय प्रतिनिधित्व इस प्रकार है:

संदर्भ

• http://igoro.com/archive/skip-lists-are-fascinating/

संदेह से जुड़ी सूची

डाउनली लिंक्ड लिस्ट एक प्रकार की लिंक्ड लिस्ट है । एक डबल लिंक की गई सूची के नोड्स में दो "पॉइंटर्स" हैं अन्य नोड्स के लिए, "अगला" और "पिछला।" इसे एक डबल लिंक्ड सूची कहा जाता है क्योंकि प्रत्येक नोड में अन्य नोड्स के लिए केवल दो "पॉइंटर्स" होते हैं। एक दोहरी लिंक की गई सूची में एक सिर और / या पूंछ सूचक हो सकता है।

         ┌─────────┬─────────┬─────────┐   ┌─────────┬─────────┬─────────┐         
 null ◀──┤previous │  data   │  next   │◀──┤previous │  data   │  next   │         
         │"pointer"│         │"pointer"│──▶│"pointer"│         │"pointer"│──▶ null 
         └─────────┴─────────┴─────────┘   └─────────┴─────────┴─────────┘         
                          ▲                     △                   △              
                     HEAD │                     │     DOUBLE        │              
                                                └──── REFERENCE ────┘                 

संदेहजनक रूप से लिंक की गई सूचियाँ, एकल लिंक्ड सूचियों की तुलना में कम स्थान की कुशल हैं; हालांकि, कुछ कार्यों के लिए, वे समय दक्षता में महत्वपूर्ण सुधार प्रदान करते हैं। एक सरल उदाहरण get फ़ंक्शन है, जो एक सिर और पूंछ के संदर्भ के साथ एक दोहरी लिंक की गई सूची के लिए सिर या पूंछ से शुरू होगा जो प्राप्त करने के लिए तत्व के सूचकांक पर निर्भर करता है। n nmentment सूची के लिए, n/2 + i अनुक्रमित तत्व प्राप्त करने के लिए, सिर / पूंछ संदर्भों के साथ एक एकल लिंक की गई सूची में n/2 + i नोड्स को पार करना होगा, क्योंकि यह पूंछ से "वापस नहीं" जा सकता है। सिर / पूंछ संदर्भों के साथ एक दोहरी लिंक की गई सूची में केवल n/2 - i नोड्स का पता लगाना है, क्योंकि यह पूंछ से "वापस जा सकता है", सूची को रिवर्स ऑर्डर में ट्रैवर्स करना।

C में उदाहरण कोड

जावा में एक बेसिक सिंगनलिंकडलिस्ट उदाहरण

जावा में एकल-लिंक्ड-लिस्ट के लिए एक बुनियादी कार्यान्वयन - जो सूची के अंत में पूर्णांक मान जोड़ सकते हैं, सूची से पहला मान प्राप्त मान निकाल सकते हैं, दिए गए इंस्टेंट पर मानों की एक सरणी लौटा सकते हैं और निर्धारित कर सकते हैं कि दिया गया मान मौजूद है या नहीं सूची मैं।

Node.java

package com.example.so.ds;


/**
 * <p> Basic node implementation </p>
 * @since 20161008
 * @author Ravindra HV
 * @version 0.1
 */
public class Node {
    
    private Node next;
    private int value;
    
    public Node(int value) {
        this.value=value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public int getValue() {
        return value;
    }
    
    
}

SinglyLinkedList.java

package com.example.so.ds;


/**
 * <p> Basic single-linked-list implementation </p>
 * @since 20161008
 * @author Ravindra HV
 * @version 0.2
 */
public class SinglyLinkedList {
    
    private Node head;
    private volatile int size;
    
    public int getSize() {
        return size;
    }
    
    public synchronized void append(int value) {
        
        Node entry = new Node(value);
        if(head == null) {
            head=entry;
        }
        else {
            Node temp=head;
            while( temp.getNext() != null) {
                temp=temp.getNext();
            }
            temp.setNext(entry);
        }
        
        size++;
    }
    
    
    public synchronized boolean removeFirst(int value) {
        boolean result = false;
        
        if( head == null ) { // or size is zero..
            // no action
        }
        else if( head.getValue() == value ) {
            head = head.getNext();
            result = true;
        }
        else {

            Node previous = head;
            Node temp = head.getNext();
            while( (temp != null) && (temp.getValue() != value) ) {
                previous = temp;
                temp = temp.getNext();
            }
            
            if((temp != null) && (temp.getValue() == value)) { // if temp is null then not found..
                previous.setNext( temp.getNext() );
                result = true;
            }

        }
        
        if(result) {
            size--;
        }
        
        return result;
        
    }
    
    public synchronized int[] snapshot() {
        Node temp=head;
        int[] result = new int[size];
        for(int i=0;i<size;i++) {
            result[i]=temp.getValue();
            temp = temp.getNext();
        }
        return result;
    }
    
    public synchronized boolean contains(int value) {
        boolean result = false;
        Node temp = head;
        
        while(temp!=null) {
            if(temp.getValue() == value) {
                result=true;
                break;
            }
            temp=temp.getNext();
        }
        return result;
    }
    
}

TestSinglyLinkedList.java

package com.example.so.ds;

import java.util.Arrays;
import java.util.Random;


/**
 * 
 * <p> Test-case for single-linked list</p>
 * @since 20161008
 * @author Ravindra HV
 * @version 0.2
 *
 */
public class TestSinglyLinkedList {

    /**
     * @param args
     */
    public static void main(String[] args) {
        
        SinglyLinkedList singleLinkedList = new SinglyLinkedList();
        
        int loop = 11;
        Random random = new Random();
        
        for(int i=0;i<loop;i++) {
            
            int value = random.nextInt(loop);
            singleLinkedList.append(value);

            System.out.println();
            System.out.println("Append :"+value);
            System.out.println(Arrays.toString(singleLinkedList.snapshot()));
            System.out.println(singleLinkedList.getSize());
            System.out.println();
        }
        
        for(int i=0;i<loop;i++) {
            int value = random.nextInt(loop);
            boolean contains = singleLinkedList.contains(value);
            singleLinkedList.removeFirst(value);
            
            System.out.println();
            System.out.println("Contains :"+contains);
            System.out.println("RemoveFirst :"+value);
            System.out.println(Arrays.toString(singleLinkedList.snapshot()));
            System.out.println(singleLinkedList.getSize());
            System.out.println();
        }
        

    }

}