Вказівки
Напишіть двобічно звʼязаний список на Rust з використанням unsafe, а також ітератор по списку й курсор для ефективного змінювання.
Двобічно звʼязаний список - одна з фундаментальних структур даних в інформатиці.
Кожен вузол двобічно звʼязаного списку містить дані та вказівники на наступний і попередній вузли, якщо вони існують.
Нові вузли можна ефективно додавати в будь-яке місце списку, якщо вже є посилання на цю позицію. Так само всі елементи з іншого списку можна вставити в будь-яке місце за сталий час.
У Rust звʼязані списки використовують дуже рідко, але іноді вони стають пасткою для новачків, коли ті намагаються реалізувати такий список. Часто виявляється, що працювати з іще незнайомим перевіряльником позичань несподівано складно.
Зауваження щодо unsafe
Памʼятаймо: мета unsafe у Rust - писати безпечний код у випадках, коли компілятор не може допомогти нам гарантувати коректність. Користувач не повинен мати можливості спричинити будь-яке порушення безпеки памʼяті, використовуючи лише безпечні інтерфейси, які ми надаємо.
Задокументуйте критичні для безпеки інваріанти, яких потрібно дотримуватися, і прокоментуйте кожен блок unsafe, пояснивши, чому він безпечний.
Будь-яку функцію, де той, хто її викликає, має дотримуватися критичних для безпеки інваріантів, слід позначити як unsafe. Це стосується і приватних функцій.
Крок 1
Реалізуйте функціональність додавання і вилучення елементів (push і pop) на початку та в кінці списку. Цього достатньо, щоб використовувати список як чергу з двома кінцями. Також реалізуйте функції len та is_empty.
У готовій реалізації всі зміни списку слід робити через структуру курсора, щоб мінімізувати дублювання. Методи push_* і pop_* у LinkedList визначено через потрібні методи курсора в модулі pre_implemented. За бажанням можна поки що пропустити структуру Cursor і перевизначити методи, але наприкінці поверніть їх до початкового стану.
Крок 2
Реалізуйте ітерацію по списку від початку до кінця за допомогою структури Iter.
Крок 3
Доповніть функціональність курсора. Він має вміти переміщатися в будь-яку позицію та вставляти або вилучати там елементи.
Крок 4
Реалізуйте трейт Drop для свого LinkedList, щоб звільняти ресурси.
Крок 5 (просунутий і необовʼязковий)
Тести для цих двох останніх пунктів компілюються умовно, через прапорець функціональності advanced. Щоб їх активувати, додайте ключ default = ["advanced"] до файлу Cargo.toml у розділі [features].
Щоб користувачі вашої структури мали максимальну гнучкість, подбайте про те, щоб ваш LinkedList<T> був коваріантним щодо T. Це означає, наприклад, що LinkedList<&'static T> можна також використовувати як LinkedList<&'a T>. Пояснення варіантності в Rust дивіться в Rustonomicon.
Подбайте про те, щоб ваш список можна було безпечно передавати через межі потоків і ділитися ним, та повідомте про це системі типів, реалізувавши Send і Sync вручну. Зазвичай ці трейти виводяться автоматично, але тут вони не реалізуються автоматично через використання сирих вказівників. Докладніше про їхнє значення дивіться в документації Send і Sync, а також у розділі про них у Rustonomicon.
