// 1034: Safe Linked List — Option<Box<Node<T>>>
// Building a singly-linked list using only safe Rust
/// A singly-linked list node
#[derive(Debug)]
struct Node<T> {
value: T,
next: Option<Box<Node<T>>>,
}
/// A singly-linked list (stack-like: push/pop at head)
#[derive(Debug)]
struct List<T> {
head: Option<Box<Node<T>>>,
len: usize,
}
impl<T> List<T> {
fn new() -> Self {
List { head: None, len: 0 }
}
fn push(&mut self, value: T) {
let new_node = Box::new(Node {
value,
next: self.head.take(), // Take ownership of old head
});
self.head = Some(new_node);
self.len += 1;
}
fn pop(&mut self) -> Option<T> {
self.head.take().map(|node| {
self.head = node.next;
self.len -= 1;
node.value
})
}
fn peek(&self) -> Option<&T> {
self.head.as_ref().map(|node| &node.value)
}
fn len(&self) -> usize {
self.len
}
fn is_empty(&self) -> bool {
self.head.is_none()
}
fn iter(&self) -> ListIter<T> {
ListIter {
current: self.head.as_deref(),
}
}
}
/// Iterator over list references
struct ListIter<'a, T> {
current: Option<&'a Node<T>>,
}
impl<'a, T> Iterator for ListIter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
self.current.map(|node| {
self.current = node.next.as_deref();
&node.value
})
}
}
/// Implement Drop to avoid stack overflow on large lists
impl<T> Drop for List<T> {
fn drop(&mut self) {
let mut current = self.head.take();
while let Some(mut node) = current {
current = node.next.take();
}
}
}
fn basic_operations() {
let mut list = List::new();
assert!(list.is_empty());
list.push(1);
list.push(2);
list.push(3);
assert_eq!(list.len(), 3);
assert_eq!(list.peek(), Some(&3));
assert_eq!(list.pop(), Some(3));
assert_eq!(list.pop(), Some(2));
assert_eq!(list.pop(), Some(1));
assert_eq!(list.pop(), None);
}
fn iterator_demo() {
let mut list = List::new();
for i in (1..=5).rev() {
list.push(i);
}
let collected: Vec<_> = list.iter().copied().collect();
assert_eq!(collected, vec![1, 2, 3, 4, 5]);
let sum: i32 = list.iter().sum();
assert_eq!(sum, 15);
let evens: Vec<_> = list.iter().filter(|&&x| x % 2 == 0).copied().collect();
assert_eq!(evens, vec![2, 4]);
}
fn from_vec() {
let mut list = List::new();
for &x in [5, 4, 3, 2, 1].iter() {
list.push(x);
}
let items: Vec<_> = list.iter().copied().collect();
assert_eq!(items, vec![1, 2, 3, 4, 5]);
}
fn main() {
basic_operations();
iterator_demo();
from_vec();
println!("✓ All tests passed");
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_basic() { basic_operations(); }
#[test]
fn test_iterator() { iterator_demo(); }
#[test]
fn test_from_vec() { from_vec(); }
#[test]
fn test_empty() {
let list: List<i32> = List::new();
assert!(list.is_empty());
assert_eq!(list.peek(), None);
assert_eq!(list.len(), 0);
}
#[test]
fn test_single_element() {
let mut list = List::new();
list.push(42);
assert_eq!(list.peek(), Some(&42));
assert_eq!(list.pop(), Some(42));
assert!(list.is_empty());
}
}
(* 1034: Safe Linked List *)
(* OCaml lists ARE linked lists — this is the native data structure *)
(* Approach 1: OCaml's built-in list (singly-linked, immutable) *)
let builtin_list () =
let lst = [1; 2; 3] in
(* Cons is O(1) *)
let lst = 0 :: lst in
assert (lst = [0; 1; 2; 3]);
(* Pattern match for head/tail *)
let (hd, tl) = match lst with
| x :: xs -> (x, xs)
| [] -> failwith "empty"
in
assert (hd = 0);
assert (tl = [1; 2; 3])
(* Approach 2: Custom linked list type (explicit) *)
type 'a node = Nil | Cons of 'a * 'a node
let rec to_list = function
| Nil -> []
| Cons (x, next) -> x :: to_list next
let rec from_list = function
| [] -> Nil
| x :: xs -> Cons (x, from_list xs)
let rec length = function
| Nil -> 0
| Cons (_, next) -> 1 + length next
let push x lst = Cons (x, lst)
let pop = function
| Nil -> None
| Cons (x, next) -> Some (x, next)
let custom_list () =
let lst = from_list [1; 2; 3] in
assert (length lst = 3);
let lst = push 0 lst in
assert (length lst = 4);
let (v, lst) = Option.get (pop lst) in
assert (v = 0);
assert (to_list lst = [1; 2; 3])
(* Approach 3: Functional operations on custom list *)
let rec map f = function
| Nil -> Nil
| Cons (x, next) -> Cons (f x, map f next)
let rec filter p = function
| Nil -> Nil
| Cons (x, next) ->
if p x then Cons (x, filter p next)
else filter p next
let rec fold f acc = function
| Nil -> acc
| Cons (x, next) -> fold f (f acc x) next
let functional_ops () =
let lst = from_list [1; 2; 3; 4; 5] in
let doubled = map (fun x -> x * 2) lst in
assert (to_list doubled = [2; 4; 6; 8; 10]);
let evens = filter (fun x -> x mod 2 = 0) lst in
assert (to_list evens = [2; 4]);
let sum = fold (fun acc x -> acc + x) 0 lst in
assert (sum = 15)
let () =
builtin_list ();
custom_list ();
functional_ops ();
Printf.printf "✓ All tests passed\n"