The Double Single

A doubly-linked list with a current position is just two singly-linked stacks glued at the cursor: everything left of the cursor on one stack, everything right of it on the other. Moving the cursor is pop from one stack and push onto the other. Insert and remove are local stack operations on whichever side you want.

1. 01
   Two List<T> from chapter 2, side by side. left is in reverse order (top of the stack is the element nearest the cursor). right is in forward order. The cursor sits between them.

   pub struct Zipper<T> {
       left: List<T>,   // elements before the cursor, reversed
       right: List<T>,  // elements after the cursor, in order
   }
   
   impl<T> Zipper<T> {
       pub fn new() -> Self {
           Zipper { left: List::new(), right: List::new() }
       }
   }

2. 02
   Move-left is left.pop() then right.push(x). Move-right is the mirror. Each is two O(1) stack ops; no node has a prev pointer because the stack itself encodes "what came before."

   impl<T> Zipper<T> {
       pub fn move_left(&mut self) -> bool {
           match self.left.pop() {
               Some(x) => { self.right.push(x); true }
               None => false,
           }
       }
   
       pub fn move_right(&mut self) -> bool {
           match self.right.pop() {
               Some(x) => { self.left.push(x); true }
               None => false,
           }
       }
   }

3. 03
   Insert-at-cursor is right.push(x) (or left.push(x) depending on which side you want the new element to land). Remove-at-cursor is right.pop(). All four edits are stack ops on a singly-linked list — exactly the operations we already know are easy in Rust.

   impl<T> Zipper<T> {
       pub fn insert_right(&mut self, x: T) { self.right.push(x); }
       pub fn insert_left(&mut self, x: T)  { self.left.push(x); }
       pub fn remove_right(&mut self) -> Option<T> { self.right.pop() }
       pub fn remove_left(&mut self)  -> Option<T> { self.left.pop() }
   }