فهرست پیوندی دوطرفه

دستورالعمل‌ها

یک لیست پیوندی دوطرفه با استفاده از unsafe در Rust بنویسید، به همراه یک تکرارگر روی لیست و یک مکان‌نما برای تغییرهای کارآمد.

لیست پیوندی دوطرفه یکی از ساختارهای داده‌ی بنیادی در علوم کامپیوتر است.

هر گره در یک لیست پیوندی دوطرفه شامل داده و اشاره‌گرهایی به گره‌ی بعدی و گره‌ی قبلی است، اگر وجود داشته باشند.

اگر از قبل ارجاعی به آن موقعیت داشته باشیم، می‌توان گره‌های جدید را به‌طور کارآمد در هر نقطه از لیست افزود. به همین ترتیب، اگر ارجاعی به آن موقعیت داشته باشیم، می‌توان همه‌ی عناصر یک لیست دیگر را در زمان ثابت در هر نقطه‌ای درج کرد.

در Rust، لیست‌های پیوندی به‌ندرت به کار می‌روند، اما گاهی هنگام پیاده‌سازی یکی از آن‌ها، تازه‌کارها را به دردسر می‌اندازند. آن‌ها اغلب کار کردن با borrow checker را، که هنوز برایشان ناآشناست، به‌طور غیرمنتظره‌ای دشوار می‌یابند.

نکته‌ای درباره‌ی unsafe

به یاد داشته باشید، هدف unsafe در Rust نوشتن کد ایمن در مواردی است که کامپایلر نمی‌تواند به ما در تضمین درستی کمک کند. نباید ممکن باشد که کاربری تنها با استفاده از رابط‌های ایمنی که در معرض دید قرار می‌دهیم، به هرگونه ناایمنی حافظه دامن بزند.

ناورداهای حیاتی ایمنی را که باید حفظ کنید مستند کنید و برای هر بلوک unsafe توضیح دهید چرا ایمن است.

هر تابعی که فراخواننده باید در آن ناورداهای حیاتی ایمنی را حفظ کند، باید unsafe علامت‌گذاری شود. این شامل توابع خصوصی هم می‌شود.

گام ۱

قابلیت افزودن و حذف عناصر (push و pop) را در ابتدا و انتهای لیست پیاده‌سازی کنید. این برای استفاده از لیست به‌عنوان یک صف دوطرفه کافی است. همچنین توابع len و is_empty را پیاده‌سازی کنید.

در پیاده‌سازی نهایی، همه‌ی تغییرهای لیست باید از طریق ساختار مکان‌نما انجام شود تا تکرار به کمترین حد برسد. متدهای push_* و pop_* روی LinkedList بر پایه‌ی متدهای لازم مکان‌نما در ماژول pre_implemented تعریف شده‌اند. اگر بخواهید، می‌توانید فعلاً ساختار Cursor را نادیده بگیرید و متدها را بازنویسی کنید، اما لطفاً در پایان آن‌ها را به حالت اول برگردانید.

گام ۲

تکرار روی لیست از ابتدا به انتها را با ساختار Iter پیاده‌سازی کنید.

گام ۳

قابلیت‌های مکان‌نما را کامل کنید. باید بتواند به هر موقعیتی جابه‌جا شود و در آنجا عناصر را درج یا حذف کند.

گام ۴

ویژگی Drop را برای LinkedList خود پیاده‌سازی کنید تا منابع را آزاد کنید.

گام ۵ (پیشرفته و اختیاری)

آزمون‌های این دو مورد آخر به‌صورت شرطی و با پرچم ویژگی advanced کامپایل می‌شوند. برای فعال کردن آن‌ها، کلید default = ["advanced"] را در فایل Cargo.toml زیر [features] اضافه کنید.

برای اینکه به کاربران ساختار شما بیشترین انعطاف را بدهید، مطمئن شوید که LinkedList<T> نسبت به T covariant است. برای نمونه، این یعنی یک LinkedList<&'static T> را می‌توان به‌عنوان یک LinkedList<&'a T> هم به کار برد. برای توضیح واریانس در Rust به Rustonomicon مراجعه کنید.

مطمئن شوید که لیستتان برای فرستادن و به اشتراک گذاشتن میان مرزهای نخ ایمن است و این را با پیاده‌سازی دستی Send و Sync به سیستم نوع اطلاع دهید. این ویژگی‌ها معمولاً به‌صورت خودکار مشتق می‌شوند، اما اینجا به دلیل استفاده از اشاره‌گرهای خام به‌طور خودکار پیاده‌سازی نشده‌اند. برای جزئیات اهمیت آن‌ها، مستندات Send و Sync و فصل rustonomicon درباره‌ی آن‌ها را ببینید.