Οδηγίες
Γράψε μια διπλά συνδεδεμένη λίστα χρησιμοποιώντας unsafe Rust, μαζί με έναν επαναλήπτη πάνω στη λίστα και έναν δρομέα για αποδοτική τροποποίηση.
Η διπλά συνδεδεμένη λίστα είναι μια θεμελιώδης δομή δεδομένων στην επιστήμη των υπολογιστών.
Κάθε κόμβος σε μια διπλά συνδεδεμένη λίστα περιέχει δεδομένα και δείκτες προς τον επόμενο και τον προηγούμενο κόμβο, εφόσον υπάρχουν.
Νέοι κόμβοι μπορούν να προστεθούν αποδοτικά σε οποιοδήποτε σημείο της λίστας, αν έχεις ήδη μια αναφορά στη θέση. Παρομοίως, όλα τα στοιχεία μιας άλλης λίστας μπορούν να εισαχθούν σε οποιοδήποτε σημείο σε σταθερό χρόνο.
Στη Rust, οι συνδεδεμένες λίστες χρησιμοποιούνται πολύ σπάνια, αλλά κατά καιρούς ξεγελούν τους αρχάριους, όταν προσπαθούν να υλοποιήσουν μία. Συχνά, τους φαίνεται απροσδόκητα δύσκολο να δουλέψουν με τον ακόμη άγνωστο σε αυτούς borrow checker.
Μια σημείωση για το unsafe
Θυμήσου, ο στόχος του unsafe Rust είναι να γράφουμε ασφαλή κώδικα σε περιπτώσεις όπου ο μεταγλωττιστής δεν μπορεί να μας βοηθήσει να εγγυηθούμε την ορθότητα. Δεν πρέπει να είναι δυνατόν ένας χρήστης να προκαλέσει οποιουδήποτε είδους ανασφάλεια μνήμης χρησιμοποιώντας μόνο τις ασφαλείς διεπαφές που εκθέτουμε.
Τεκμηρίωσε τις κρίσιμες για την ασφάλεια αναλλοίωτες συνθήκες που πρέπει να διατηρείς και σχολίασε κάθε μπλοκ unsafe εξηγώντας γιατί είναι ασφαλές.
Κάθε συνάρτηση όπου αυτός που την καλεί πρέπει να διατηρεί κρίσιμες για την ασφάλεια αναλλοίωτες συνθήκες θα πρέπει να σημειώνεται ως unsafe. Αυτό περιλαμβάνει και τις ιδιωτικές συναρτήσεις.
Βήμα 1
Υλοποίησε τη λειτουργικότητα για προσθήκη και αφαίρεση στοιχείων (push και pop) στο μπροστινό και στο πίσω άκρο. Αυτό αρκεί για να χρησιμοποιήσεις τη λίστα ως ουρά διπλού άκρου. Υλοποίησε επίσης τις συναρτήσεις len και is_empty.
Στην τελική υλοποίηση, όλες οι τροποποιήσεις της λίστας θα πρέπει να γίνονται μέσω της δομής δρομέα, ώστε να ελαχιστοποιηθεί η επανάληψη κώδικα. Οι μέθοδοι push_* και pop_* του LinkedList ορίζονται με βάση τις απαιτούμενες μεθόδους του δρομέα στο module pre_implemented. Αν θέλεις, μπορείς να παραλείψεις προς το παρόν τη δομή Cursor και να παρακάμψεις τις μεθόδους, αλλά σε παρακαλώ να τις επαναφέρεις στο τέλος.
Βήμα 2
Υλοποίησε την επανάληψη πάνω στη λίστα από την αρχή προς το τέλος με τη δομή Iter.
Βήμα 3
Ολοκλήρωσε τη λειτουργικότητα του δρομέα. Θα πρέπει να μπορεί να μετακινηθεί σε οποιαδήποτε θέση και να εισάγει ή να αφαιρεί στοιχεία εκεί.
Βήμα 4
Υλοποίησε το trait Drop για το LinkedList σου, ώστε να καθαρίζονται οι πόροι.
Βήμα 5 (προχωρημένο και προαιρετικό)
Τα τεστ για τα δύο τελευταία πράγματα μεταγλωττίζονται υπό συνθήκη, μέσω της σημαίας δυνατότητας advanced. Πρόσθεσε το κλειδί default = ["advanced"] στο αρχείο Cargo.toml, κάτω από το [features], για να τα ενεργοποιήσεις.
Για να δώσεις στους χρήστες της δομής σου τη μέγιστη δυνατή ευελιξία, φρόντισε το LinkedList<T> σου να είναι συνμεταβλητό ως προς το T. Αυτό σημαίνει, για παράδειγμα, ότι ένα LinkedList<&'static T> μπορεί να χρησιμοποιηθεί και ως LinkedList<&'a T>. Δες το Rustonomicon για μια εξήγηση της μεταβλητότητας των τύπων στη Rust.
Φρόντισε η λίστα σου να μπορεί να σταλεί και να μοιραστεί με ασφάλεια πέρα από τα όρια νημάτων, και δήλωσέ το αυτό στο σύστημα τύπων υλοποιώντας χειροκίνητα τα Send και Sync. Αυτά τα trait συνήθως παράγονται αυτόματα, αλλά εδώ δεν υλοποιούνται αυτόματα, λόγω της χρήσης ακατέργαστων δεικτών. Δες την τεκμηρίωση για τα Send και Sync και το κεφάλαιο του rustonomicon σχετικά με αυτά, για λεπτομέρειες ως προς τη σημασία τους.
