지침
unsafe Rust로 이중 연결 리스트를 작성해요. 리스트를 순회하는 반복자와 효율적인 변경을 위한 커서도 함께 구현해요.
이중 연결 리스트는 컴퓨터 과학의 기본적인 자료 구조예요.
이중 연결 리스트의 각 노드는 데이터와, 존재한다면 다음 노드와 이전 노드에 대한 포인터를 담고 있어요.
위치에 대한 참조만 있다면 리스트의 어느 지점에든 새 노드를 효율적으로 추가할 수 있어요. 마찬가지로 다른 리스트의 모든 원소를 상수 시간에 어느 지점에든 삽입할 수 있어요.
Rust에서는 연결 리스트를 아주 드물게 사용하지만, 초보자가 직접 구현해 보려다 가끔 여기서 발목을 잡히곤 해요. 그러면서 아직 익숙하지 않은 빌림 검사기와 씨름하는 일이 생각보다 어렵다고 느끼는 경우가 많아요.
unsafe에 대한 참고
기억하세요, unsafe Rust의 목표는 컴파일러가 정확성을 보장해 줄 수 없는 상황에서도 안전한 코드를 작성하는 거예요. 사용자가 우리가 노출한 안전한 인터페이스만으로는 어떤 종류의 메모리 비안전성도 일으킬 수 없어야 해요.
지켜야 하는 안전에 중요한 불변 조건을 문서화하고, 각 unsafe 블록이 왜 안전한지 설명하는 주석을 달아요.
호출자가 안전에 중요한 불변 조건을 유지해야 하는 함수는 모두 unsafe로 표시해야 해요. 비공개 함수도 마찬가지예요.
1단계
앞과 뒤에서 원소를 추가하고 제거하는 기능(푸시와 팝)을 구현해요. 이것만으로도 리스트를 양방향 큐로 사용할 수 있어요. len과 is_empty 함수도 구현해요.
완성된 구현에서는 중복을 최소화하기 위해 리스트의 모든 변경이 커서 구조체를 통해 이루어져야 해요. LinkedList의 push_*와 pop_* 메서드는 pre_implemented 모듈에 있는 필수 커서 메서드를 바탕으로 정의되어 있어요. 원한다면 지금은 Cursor 구조체를 건너뛰고 메서드를 재정의해도 되지만, 마지막에는 원래대로 되돌려 주세요.
2단계
Iter 구조체로 리스트를 앞에서 뒤로 순회하는 반복을 구현해요.
3단계
커서의 기능을 완성해요. 커서는 어떤 위치로든 이동할 수 있어야 하고, 그 위치에서 원소를 삽입하거나 제거할 수 있어야 해요.
4단계
리소스를 정리하기 위해 LinkedList에 Drop 트레이트를 구현해요.
5단계 (심화, 선택 사항)
이 마지막 두 가지에 대한 테스트는 advanced 기능 플래그를 통해 조건부로 컴파일돼요. 활성화하려면 Cargo.toml 파일의 [features] 아래에 default = ["advanced"] 키를 추가해요.
여러분의 구조체를 사용하는 사람이 최대한 유연하게 쓸 수 있도록, LinkedList<T>가 T에 대해 공변하도록 만들어요. 예를 들어 LinkedList<&'static T>를 LinkedList<&'a T>로도 사용할 수 있다는 뜻이에요. Rust에서의 변성에 대한 설명은 Rustonomicon을 참고해요.
리스트가 스레드 경계를 넘어 안전하게 전송되고 공유될 수 있는지 확인하고, Send와 Sync를 직접 구현해서 이를 타입 시스템에 알려요. 이 트레이트들은 보통 자동으로 파생되지만, 원시 포인터를 사용하기 때문에 여기서는 자동으로 구현되지 않아요. 이들의 중요성에 대한 자세한 내용은 Send와 Sync 문서, 그리고 이에 관한 rustonomicon 장을 참고해요.
