Arc

Rc<T> uses a non-atomic counter — fast, but unsound across threads. Arc<T> is the same shape with fetch_add/fetch_sub on the count, identical to going from shared_ptr to atomic_shared_ptr. The compiler refuses to send an Rc across threads; switching to Arc makes the list Send and Sync automatically.

1. 01
   Mechanical change: use std::sync::Arc instead of std::rc::Rc, then global rename. The API is identical — Arc::new, Arc::clone, Arc::try_unwrap all exist with the same signatures. Cost is one atomic RMW per clone/drop instead of a plain integer write; for a persistent immutable list this is usually fine.

   use std::sync::Arc;
   
   pub struct List<T> {
       head: Link<T>,
   }
   
   type Link<T> = Option<Arc<Node<T>>>;
   
   struct Node<T> {
       elem: T,
       next: Link<T>,
   }
   
   // prepend, tail, head, Drop are unchanged except Rc -> Arc.

2. 02
   Send and Sync are auto traits — the compiler infers them from the fields. A type is Send if all its fields are Send (movable across threads) and Sync if &T is safe to share across threads. Arc<T> is both when T: Send + Sync; Rc<T> is neither. Once you swap, List<T> picks up both auto traits and you can std::thread::spawn with it for free.

   use std::thread;
   
   let shared = List::new().prepend(1).prepend(2).prepend(3);
   let clone1 = shared.clone();   // refcount bump, atomic
   let clone2 = shared.clone();
   
   thread::spawn(move || {
       assert_eq!(clone1.head(), Some(&3));
   });
   thread::spawn(move || {
       assert_eq!(clone2.head(), Some(&3));
   });
   // would not compile with Rc — the closures aren't Send.