A Rust implementation of [my O(n) array-to-list algorithm](https://discord.com/channels/1246152587883970662/1246156450875707556/1317876681255686206), using the `loaned` crate.

array_to_list.rs

use loaned::{take, LoanedMut};
use std::mem::replace;

#[derive(Debug, Clone)]
struct List<T>(Option<(T, Box<List<T>>)>);

impl<T> List<T> {
  fn into_vec(self) -> Vec<T> {
    let mut vec = Vec::new();
    let mut list = self;
    while let Some((head, tail)) = list.0 {
      vec.push(head);
      list = *tail;
    }
    vec
  }
}

#[derive(Debug, Clone)]
enum Array<T> {
  Empty,
  Item(T),
  Tree(usize, Box<Array<T>>, Box<Array<T>>),
}

impl<T> Array<T> {
  fn len(&self) -> usize {
    match *self {
      Array::Empty => 0,
      Array::Item(_) => 1,
      Array::Tree(len, ..) => len,
    }
  }

  fn push_front(&mut self, value: T) {
    match replace(self, Array::Empty) {
      Array::Empty => *self = Array::Item(value),
      Array::Item(prev) => {
        *self = Array::Tree(2, Box::new(Array::Item(value)), Box::new(Array::Item(prev)));
      }
      Array::Tree(len, even, mut odd) => {
        odd.push_front(value);
        *self = Array::Tree(len + 1, odd, even);
      }
    }
  }

  fn push_back(&mut self, value: T) {
    match replace(self, Array::Empty) {
      Array::Empty => *self = Array::Item(value),
      Array::Item(prev) => {
        *self = Array::Tree(2, Box::new(Array::Item(prev)), Box::new(Array::Item(value)))
      }
      Array::Tree(len, mut even, mut odd) => {
        if len % 2 == 0 {
          even.push_back(value);
        } else {
          odd.push_back(value);
        }
        *self = Array::Tree(len + 1, even, odd);
      }
    }
  }

  fn pop_front(&mut self) -> Option<T> {
    match replace(self, Array::Empty) {
      Array::Empty => None,
      Array::Item(value) => Some(value),
      Array::Tree(len, mut even, odd) => {
        let value = even.pop_front();
        if len == 2 {
          *self = *odd;
        } else {
          *self = Array::Tree(len - 1, odd, even);
        }
        value
      }
    }
  }

  fn pop_back(&mut self) -> Option<T> {
    match replace(self, Array::Empty) {
      Array::Empty => None,
      Array::Item(value) => Some(value),
      Array::Tree(len, mut even, mut odd) => {
        let value = if len % 2 == 0 { odd.pop_back() } else { even.pop_back() };
        if len == 2 {
          *self = *even;
        } else {
          *self = Array::Tree(len - 1, even, odd);
        }
        value
      }
    }
  }

  fn into_list(self) -> List<T> {
    let (mut lists, holes) = create_lists_holes(self);
    lists.push_back(LoanedMut::new(List(None)));
    let list = lists.pop_front().unwrap();
    merge_lists_holes(lists, holes);
    return take!(list);

    fn create_lists_holes<'a, T>(
      array: Array<T>,
    ) -> (Array<LoanedMut<'a, List<T>>>, Array<&'a mut List<T>>) {
      match array {
        Array::Empty => (Array::Empty, Array::Empty),
        Array::Item(value) => {
          let (hole, list) =
            LoanedMut::loan_with(List(Some((value, Box::new(List(None))))), |list, l| {
              l.loan_mut(&mut list.0.as_mut().unwrap().1)
            });
          (Array::Item(list), Array::Item(hole))
        }
        Array::Tree(len, even, odd) => {
          let (lists_even, holes_even) = create_lists_holes(*even);
          let (lists_odd, holes_odd) = create_lists_holes(*odd);
          (
            Array::Tree(len, Box::new(lists_even), Box::new(lists_odd)),
            Array::Tree(len, Box::new(holes_even), Box::new(holes_odd)),
          )
        }
      }
    }

    fn merge_lists_holes<'a, T>(
      lists: Array<LoanedMut<'a, List<T>>>,
      holes: Array<&'a mut List<T>>,
    ) {
      match (lists, holes) {
        (Array::Empty, Array::Empty) => {}
        (Array::Item(list), Array::Item(hole)) => list.place(hole),
        (Array::Tree(_, lists_even, lists_odd), Array::Tree(_, holes_even, holes_odd)) => {
          merge_lists_holes(*lists_even, *holes_even);
          merge_lists_holes(*lists_odd, *holes_odd);
        }
        _ => unreachable!(),
      }
    }
  }
}

fn main() {
  let mut a = Array::<u8>::Empty;
  a.push_back(2);
  a.push_back(3);
  a.push_front(1);
  a.push_back(4);
  a.push_front(0);
  assert_eq!(a.into_list().into_vec(), vec![0, 1, 2, 3, 4]);
}