लिंक्ड सूचियों के सरल ट्रैवर्सल के लिए पॉइंटर-टू-पॉइंटर तकनीक क्या है?

Question

दस साल पहले, मुझे एक लिंक्ड सूची को पार करने के लिए एक तकनीक दिखाई गई थी: एक पॉइंटर का उपयोग करने के बजाय, आपने एक डबल पॉइंटर (पॉइंटर-टू-पॉइंटर) का उपयोग किया था।

तकनीक ने कुछ सीमा/किनारे के मामलों की जांच करने की आवश्यकता को समाप्त कर छोटे, अधिक सुरुचिपूर्ण कोड प्रदान किए।

क्या कोई यह जानता है कि वास्तव में यह तकनीक क्या है?

Answer 1

मुझे लगता है कि आप जो एक अकेले के अंत में सम्मिलित करने के लिए बहुत ही कुशल है "एक सूचक सूचक" के रूप में डबल सूचक मतलब लिंक्ड सूची या वृक्ष संरचना। विचार यह है कि एक बार जब आप अंत (एक पूर्ण सूचक) पाते हैं तो आपको अपने ट्रैवर्सल पॉइंटर का पालन करने के लिए एक विशेष केस या "पिछला पॉइंटर" की आवश्यकता नहीं होती है। चूंकि आप अपने पॉइंटर को पॉइंटर (केवल अंक को अंतिम नोड के अगले पॉइंटर पर) को सम्मिलित कर सकते हैं!) डालने के लिए। कुछ इस तरह:

T **p = &list_start; 
while (*p) { 
    p = &(*p)->next; 
} 
*p = new T; 

के बजाय कुछ इस तरह:

T *p = list_start; 
if (p == NULL) { 
    list_start = new T; 
} else { 
    while (p->next) { 
     p = p->next; 
    } 
    p->next = new T; 
} 

नोट: यह भी एक अकेले लिंक्ड सूची के लिए कुशल हटाने कोड बनाने के लिए उपयोगी है। किसी भी बिंदु पर *p = (*p)->next उस नोड को हटा देगा जिसे आप "देख रहे हैं" (बेशक आपको अभी भी नोड के भंडारण को साफ करने की आवश्यकता है)।

Answer 2

मुझे लगता है कि तुम्हारा मतलब doubly-linked lists जहां एक नोड की तरह कुछ है:

struct Node { 
(..) data // The data being stored in the node, it can be of any data type 
Node *next; // A pointer to the next node; null for last node 
Node *prev; // A pointer to the previous node; null for first node 
} 

Answer 3

आप शायद एक दोगुनी-लिंक्ड सूची का मतलब है, एक पॉइंटर्स आगे बढ़ रहे हैं और दूसरा पिछड़ा जा रहा है। यह आपको दिए गए नोड के लिए अगले और पिछले नोड्स को अंतिम या दो नोड्स को याद किए बिना (एकल-लिंक्ड सूची में) याद रखने की अनुमति देता है।

लेकिन एक चीज जिसने मुझे खोजा, जिसने कोड भी बनाया और सुरुचिपूर्ण हमेशा सूची में दो और धूल तत्वों को हमेशा, आखिरी और आखिरी बार रखना था। यह प्रविष्टि और हटाने के लिए किनारे के मामलों से छुटकारा पाता है क्योंकि आप हमेशा सूची के मध्य में नोड पर कार्य करते हैं।

उदाहरण के लिए, एक खाली सूची बनाई गई है:

first = new node 
last = new node 
first.next = last 
first.prev = null 
last.next = null 
last.prev = first 
// null <- first <-> last -> null 

जाहिर है, सूची traversing थोड़ा संशोधित किया जाता है (आगे संस्करण केवल दिखाया गया है):

curr = first.next 
while curr <> last: 
    do something with curr 
    curr = curr.next 

सम्मिलन आप के बाद से डॉन अधिक सरल होती हैं सूची के आरंभ या अंत में आप डालने के साथ खुद को चिंता करने की ज़रूरत नहीं है। वर्तमान बिंदु से पहले सम्मिलित करने के लिए:

if curr = first: 
    raise error 
add = new node 
add.next = curr 
add.prev = curr.prev 
curr.prev.next = add 
curr.prev = add 

विलोपन, यह भी सरल हैं किनारे मामलों से परहेज:

if curr = first or curr = last: 
    raise error 
curr.prev.next = curr.next 
curr.next.prev = curr.prev 
delete curr 

सभी बहुत अधिक स्वच्छ कोड और केवल सूची के अनुसार दो अतिरिक्त नोड्स बनाए रखने के लिए होने की कीमत पर , आज के विशाल स्मृति अंतरिक्ष वातावरण में एक बड़ा बोझ नहीं है।

चेतावनी 1: यदि आप एम्बेडेड प्रोग्रामिंग कर रहे हैं जहां अंतरिक्ष अभी भी महत्वपूर्ण हो सकता है, तो यह एक व्यवहार्य समाधान नहीं हो सकता है (हालांकि कुछ एम्बेडेड वातावरण इन दिनों भी बहुत गड़बड़ हैं)।

चेतावनी 2: यदि आप ऐसी भाषा का उपयोग कर रहे हैं जो पहले से ही लिंक्ड सूची क्षमताओं को प्रदान करता है, तो शायद यह स्वयं को रोल करने के बजाय बेहतर है (बहुत विशिष्ट परिस्थितियों के अलावा)।

Answer 4

"डबल-पॉइंटर" द्वारा, मुझे लगता है कि आपका मतलब है "पॉइंटर-टू-पॉइंटर"। यह उपयोगी है क्योंकि यह आपको सिर या पूंछ पॉइंटर्स के लिए विशेष मामलों को खत्म करने की अनुमति देता है।

if (head->key == search_key) 
{ 
    removed = head; 
    head = head->next; 
} 
else 
{ 
    struct node *cur; 

    for (cur = head; cur->next != NULL; cur = cur->next) 
    { 
     if (cur->next->key == search_key) 
     { 
      removed = cur->next; 
      cur->next = cur->next->next; 
      break; 
     } 
    } 
} 

जबकि सूचक-टू:

struct node { 
    struct node *next; 
    int key; 
    /* ... */ 
}; 

struct node *head; 

आप एक नोड के लिए खोज और सूची से निकालने चाहते हैं, एकल सूचक विधि दिखाई देगा: उदाहरण के लिए, यह सूची दी गयी -pointer विधि बहुत सरल है:

struct node **cur; 

for (cur = &head; *cur != NULL; cur = &(*cur)->next) 
{ 
    if ((*cur)->key == search_key) 
    { 
     removed = *cur; 
     *cur = (*cur)->next; 
     break; 
    } 
} 

Answer 5

मैं अपनी सूची गंदे काम से निपटने के लिए एसटीएल कंटेनरों का इस्तेमाल के बारे में टिप्पणी से सहमत हैं। हालांकि, यह स्टैक ओवरफ़्लो है, हम सब कुछ सीखने के लिए यहां हैं।

यहाँ कैसे आप सामान्य रूप से एक सूची में सम्मिलित होता है:

typedef struct _Node { 
    void * data; 
    Node * next; 
} Node; 

Node * insert(Node * root, void * data) { 
    Node * list = root; 
    Node * listSave = root; 

    while (list != null) { 
     if (data < list->data) { 
      break; 
     } 

     listSave = list; 
     list = list->next; 
    } 

    Node * newNode = (Node*)malloc(sizeof(Node)); 
    newNode->data = data; 
    /* Insert at the beginning of the list */ 
    if (listSave == list) { 
     newNode->next = list; 
     list = newNode; 
    } 
    /* Insert at the end of the list */ 
    else if (list == null) { 
     listSave->next = newNode; 
     newNode->next = null; 
     list = root; 
    } 
    /* Insert at the middle of the list */ 
    else { 
     listSave->next = newNode; 
     newNode->next = list; 
     list = root; 
    } 

    return list; 
} 

सूचना सभी अतिरिक्त जाँच तुम पर प्रविष्टि शुरुआत है, अंत या सूची के बीच में होता है कि क्या निर्भर करता है क्या करना है। डबल सूचक विधि के साथ इस कंट्रास्ट:

void insert(Node ** proot, void * data) { 
    Node ** plist = proot; 

    while (*plist != null) { 
     if (data < (*plist)->data) { 
      break; 
     } 

     plist = &(*plist)->next; 
    } 

    Node * newNode = (Node *)malloc(sizeof(Node)); 
    newNode->data = data; 
    newNode->next = *plist; 
    *plist = newNode; 
} 

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