पूंछ सूचक के साथ एक लिंक्ड सूची लिखने का बेवकूफ तरीका क्या है?

Question

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

type NodePtr<T> = Option<Box<Node<T>>>; 

struct Node<T> { 
    data: T, 
    next: NodePtr<T>, 
} 

pub struct LinkedList<T> { 
    head: NodePtr<T>, 
} 

को लागू करने size और push_front दोनों यथोचित सीधी-सपाट थे, हालांकि कर आकार iteratively शामिल था कुछ "उधार चेकर के साथ लड़ रहे हैं।"

अगली चीज़ जो मैं कोशिश करना चाहता था tail पॉइंटर LinkedList संरचना में जोड़ रहा था। एक कुशल push_back ऑपरेशन सक्षम करने के लिए। यहाँ मैं एक दीवार में भाग गया है। पहले मैंने Option<&Box<Node<T>>> और फिर Option<&Node<T>> का उपयोग करने का प्रयास किया। उन दोनों ने 'a एस हर जगह छिड़कने का नेतृत्व किया, लेकिन अंत में जीवन भर के चेकर का वादा करने में असमर्थ रहा कि tail मान्य होगा।

मैं के बाद से जांच निष्कर्ष यह है कि यह इन परिभाषाओं के साथ असंभव है के लिए आए हैं: गारंटी संकलक कि tail स्थानों मुझे लगता है कि यह मान्य है में मान्य होगा करने के लिए कोई रास्ता नहीं है कि वहाँ। एकमात्र तरीका यह है कि मैं संभवतः यह पूरा कर सकता हूं कि मेरे सभी पॉइंटर्स Rc<_> या Rc<RefCell<_>> हो, क्योंकि वे एक ही ऑब्जेक्ट (अंतिम नोड) पर इंगित करने वाली दो चीजें रखने का एकमात्र सुरक्षित तरीका हैं।

मेरा प्रश्न: क्या यह सही निष्कर्ष है? अधिक आम तौर पर: डेटा संरचनाओं के अंदर अज्ञात पॉइंटर्स के लिए बेवकूफ जंग समाधान क्या है? मेरे दिमाग में, संदर्भ गिनती इतनी सरल के लिए भारी वजन लगती है, इसलिए मुझे लगता है कि मुझे कुछ याद आना चाहिए। (या शायद मैं सिर्फ मेरे मन स्मृति सुरक्षा के लिए सही मानसिकता में अभी तक मिल गया है नहीं।)

Answer 1

हाँ, आप तीन विकल्प यदि आप एक पूंछ सूचक के साथ एक अकेले लिंक्ड-सूची लिखना चाहते हैं:

• सुरक्षित और परिवर्त्य: NodePtr उपयोग = Option<Rc<RefCell<Node<T>>>>
• सुरक्षित और अपरिवर्तनीय: उपयोग NodePtr = Option<Rc<Node<T>>>
• असुरक्षित और परिवर्त्य: उपयोग tail: *mut Node<T>

*mut अधिक कुशल होने जा रहा है, और यह Rc की तरह नहीं है वास्तव में को पूरी तरह बकवास राज्यों (जैसा कि आपने सही ढंग से घटाया है) का उत्पादन करने से रोक दिया है। यह सिर्फ यह गारंटी देने जा रहा है कि वे segfaults का कारण नहीं बनते हैं (और RefCell के साथ यह अभी भी रनटाइम क्रैश का कारण बन सकता है ...)।

आखिरकार, वेनिला सिंगल-लिंक्ड की तुलना में किसी भी लिंक्ड सूची में अधिक जटिल एक स्वामित्व की कहानी है जो जंग की स्वामित्व प्रणाली को सुरक्षित रूप से और कुशलता से एन्कोड करने के लिए बहुत जटिल है (यह एक पेड़ नहीं है)। मैं व्यक्तिगत रूप से उस बिंदु पर असुरक्षितता को स्वीकार करने और एक टुकड़े में फिनिश लाइन तक पहुंचने के लिए इकाई परीक्षणों पर झुकाव का पक्ष लेता हूं (एक उप-डेटा डेटा संरचना क्यों लिखें ...?)।