Utasítások
Írj kétszeresen láncolt listát unsafe Rustban, a lista fölötti iterátorral és egy kurzorral a hatékony módosításhoz.
A kétszeresen láncolt lista a számítástudomány egyik alapvető adatszerkezete.
A kétszeresen láncolt lista minden csomópontja adatot, valamint mutatót tartalmaz a következő és az előző csomópontra, amennyiben azok léteznek.
Új csomópontokat hatékonyan lehet a lista bármely pontjára beszúrni, ha már van hivatkozásunk a pozícióra. Hasonlóképpen egy másik lista összes eleme is beszúrható bármely pontra konstans időben.
Rustban a láncolt listákat nagyon ritkán használják, de néha mégis megtréfálják az újoncokat, amikor megpróbálnak implementálni egyet. Gyakran váratlanul nehéznek találják a munkát a még ismeretlen kölcsönzésellenőrzővel.
Megjegyzés az unsafe-hez
Ne feledd, az unsafe Rust célja az, hogy biztonságos kódot írjunk azokban az esetekben, amikor a fordító nem tud segíteni a helyesség garantálásában. Egy felhasználó számára nem lehet lehetséges, hogy kizárólag az általunk közzétett biztonságos felületeken keresztül bármilyen memóriabiztonsági problémát okozzon.
Dokumentáld a betartandó biztonságkritikus invariánsokat, és kommenteld az egyes unsafe blokkokat, elmagyarázva, miért biztonságosak.
Minden olyan függvényt, ahol a hívónak biztonságkritikus invariánsokat kell fenntartania, unsafe-ként kell megjelölni. Ez a privát függvényekre is vonatkozik.
1. lépés
Valósítsd meg az elemek hozzáadásának és eltávolításának (push és pop) funkcióját a lista elején és végén. Ez elég ahhoz, hogy a listát kétvégű sorként használd. Valósítsd meg a len és is_empty függvényeket is.
A kész implementációban a lista minden módosítását a kurzor struktúrán keresztül kell végezni, hogy minimalizáljuk a duplikációt. A LinkedList push_* és pop_* metódusai a pre_implemented modulban megkövetelt kurzormetódusokra épülnek. Ha szeretnéd, egyelőre kihagyhatod a Cursor struktúrát, és felülírhatod a metódusokat, de a végén kérünk, állítsd vissza őket.
2. lépés
Valósítsd meg a lista elejétől a végéig történő iterálást az Iter struktúrával.
3. lépés
Fejezd be a kurzor funkcionalitását. Képesnek kell lennie bármely pozícióra mozogni, és ott elemeket beszúrni vagy eltávolítani.
4. lépés
Valósítsd meg a Drop traitet a LinkedList típusodhoz, hogy felszabadítsd az erőforrásokat.
5. lépés (haladó és opcionális)
Az utolsó két dologhoz tartozó tesztek feltételesen fordulnak le az advanced feature flag segítségével. Add hozzá a default = ["advanced"] kulcsot a Cargo.toml fájlhoz a [features] szakasz alatt, hogy aktiváld őket.
Hogy a struktúrád felhasználóinak maximális rugalmasságot nyújts, gondoskodj róla, hogy a LinkedList<T> kovariáns legyen T fölött. Ez például azt jelenti, hogy egy LinkedList<&'static T> LinkedList<&'a T>-ként is használható. A Rustbeli variancia magyarázatáért lásd a Rustonomicon című dokumentumot.
Gondoskodj róla, hogy a listád biztonságosan küldhető és osztható legyen szálak között, és jelezd ezt a típusrendszernek a Send és Sync trait kézi megvalósításával. Ezeket a traiteket általában automatikusan származtatja a fordító, itt viszont a nyers mutatók használata miatt nem valósulnak meg automatikusan. A jelentőségük részleteiért lásd a Send és a Sync dokumentációját, valamint a rustonomicon fejezetet róluk.
