NLinker

Two Double Linked List implementations

May 3rd, 2020
975
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. mod x_c3db81ec94bf231b721ef483f58deb35 {
  2.     //! A doubly-linked list in 50 LOCs of stable and safe Rust.
  3.     use std::cell::RefCell;
  4.     use std::rc::{Rc, Weak};
  5.     use std::fmt::Display;
  6.  
  7.     // The node type stores the data and two pointers.
  8.     //
  9.     // It uses Option to represent nullability in safe Rust. It has zero overhead
  10.     // over a null pointer due to the NonZero optimization.
  11.     //
  12.     // It uses an Rc (Reference Counted) pointer to give ownership of the next node
  13.     // to the current node. And a Weak (weak Reference Counted) pointer to reference
  14.     // the previous node without owning it.
  15.     //
  16.     // It uses RefCell for interior mutability. It allows mutation through
  17.     // shared references.
  18.     struct Node<T> {
  19.         pub data: T,
  20.         pub prev: Option<Weak<RefCell<Node<T>>>>,
  21.         pub next: Option<Rc<RefCell<Node<T>>>>,
  22.     }
  23.  
  24.     impl<T> Node<T> {
  25.         // Constructs a node with some `data` initializing prev and next to null.
  26.         pub fn new(data: T) -> Self {
  27.             Self { data, prev: None, next: None }
  28.         }
  29.  
  30.         // Appends `data` to the chain of nodes. The implementation is recursive
  31.         // but one could rewrite it to use a while-let imperative loop instead
  32.         // without too much effort.
  33.         pub fn append(node: &mut Rc<RefCell<Node<T>>>, data: T) -> Option<Rc<RefCell<Node<T>>>> {
  34.             let is_last = node.borrow().next.is_none();
  35.             if is_last {
  36.                 // If the current node is the last one, create a new node,
  37.                 // set its prev pointer to the current node, and store it as
  38.                 // the node after the current one.
  39.                 let mut new_node = Node::new(data);
  40.                 new_node.prev = Some(Rc::downgrade(&node));
  41.                 let rc = Rc::new(RefCell::new(new_node));
  42.                 node.borrow_mut().next = Some(rc.clone());
  43.                 Some(rc)
  44.             } else {
  45.                 // Not the last node, just continue traversing the list:
  46.                 if let Some(ref mut next) = node.borrow_mut().next {
  47.                     Self::append(next, data)
  48.                 } else { None }
  49.             }
  50.         }
  51.     }
  52.  
  53.     // The doubly-linked list with pointers to the first and last nodes in the list.
  54.     struct List<T> {
  55.         first: Option<Rc<RefCell<Node<T>>>>,
  56.         last: Option<Rc<RefCell<Node<T>>>>,
  57.     }
  58.  
  59.     impl<T> List<T> {
  60.         // Constructs an empty list.
  61.         pub fn new() -> Self {
  62.             Self { first: None, last: None }
  63.         }
  64.         // Appends a new node to the list, handling the case where the list is empty.
  65.         pub fn append(&mut self, data: T) {
  66.             if let Some(ref mut next) = self.first {
  67.                 self.last = Node::append(next, data);
  68.             } else {
  69.                 let f = Rc::new(RefCell::new(Node::new(data)));
  70.                 self.first = Some(f.clone());
  71.                 self.last = Some(f);
  72.             }
  73.         }
  74.     }
  75.  
  76.     // Pretty-printing
  77.     impl<T: Display> Display for List<T> {
  78.         fn fmt(&self, w: &mut std::fmt::Formatter) -> std::result::Result<(), std::fmt::Error> {
  79.             write!(w, "[")?;
  80.             let mut node = self.first.clone();
  81.             while let Some(n) = node {
  82.                 write!(w, "{}", n.borrow().data)?;
  83.                 node = n.borrow().next.clone();
  84.                 if node.is_some() {
  85.                     write!(w, ", ")?;
  86.                 }
  87.             }
  88.             write!(w, "]")
  89.         }
  90.     }
  91.  
  92.     fn main() {
  93.         let mut list = List::new();
  94.         println!("{}", list);
  95.         for i in 0..5 {
  96.             list.append(i);
  97.         }
  98.         println!("{}", list);
  99.     }
  100. }
  101.  
  102. mod x_71c6bc45ff92452d5a4397ddb2dbb3de {
  103.     //! A doubly-linked list in 50 LOCs of stable and safe Rust.
  104.     use std::cell::RefCell;
  105.     use std::rc::{Rc, Weak};
  106.     use std::fmt::Display;
  107.  
  108.     // The node type stores the data and two pointers.
  109.     //
  110.     // It uses Option to represent nullability in safe Rust. It has zero overhead
  111.     // over a null pointer due to the NonZero optimization.
  112.     //
  113.     // It uses an Rc (Reference Counted) pointer to give ownership of the next node
  114.     // to the current node. And a Weak (weak Reference Counted) pointer to reference
  115.     // the previous node without owning it.
  116.     //
  117.     // It uses RefCell for interior mutability. It allows mutation through
  118.     // shared references.
  119.     struct Node<T> {
  120.         pub data: T,
  121.         pub prev: Option<Weak<RefCell<Node<T>>>>,
  122.         pub next: Option<Rc<RefCell<Node<T>>>>,
  123.     }
  124.  
  125.     impl<T> Node<T> {
  126.         // Constructs a node with some `data` initializing prev and next to null.
  127.         pub fn new(data: T) -> Self {
  128.             Self { data, prev: None, next: None }
  129.         }
  130.         // Appends `data` to the chain of nodes. The implementation is recursive
  131.         // but one could rewrite it to use a while-let imperative loop instead
  132.         // without too much effort.
  133.         pub fn append(node: &mut Rc<RefCell<Node<T>>>, data: T) {
  134.             let is_last = node.borrow().next.is_none();
  135.             if is_last {
  136.                 // If the current node is the last one, create a new node,
  137.                 // set its prev pointer to the current node, and store it as
  138.                 // the node after the current one.
  139.                 let mut new_node = Node::new(data);
  140.                 new_node.prev = Some(Rc::downgrade(&node));
  141.                 node.borrow_mut().next = Some(Rc::new(RefCell::new(new_node)));
  142.             } else {
  143.                 // Not the last node, just continue traversing the list:
  144.                 if let Some(ref mut next) = node.borrow_mut().next {
  145.                     Self::append(next, data);
  146.                 }
  147.             }
  148.         }
  149.     }
  150.  
  151.     // The doubly-linked list with pointers to the first and last nodes in the list.
  152.     struct List<T> {
  153.         first: Option<Rc<RefCell<Node<T>>>>,
  154.         last: Option<Rc<RefCell<Node<T>>>>,
  155.     }
  156.  
  157.     impl<T> List<T> {
  158.         // Constructs an empty list.
  159.         pub fn new() -> Self {
  160.             Self { first: None, last: None }
  161.         }
  162.         // Appends a new node to the list, handling the case where the list is empty.
  163.         pub fn append(&mut self, data: T) {
  164.             if let Some(ref mut next) = self.first {
  165.                 Node::append(next, data);
  166.                 let v = self.last.as_ref().unwrap().borrow().next
  167.                     .as_ref().unwrap().clone();
  168.                 self.last = Some(v);
  169.             } else {
  170.                 let f = Rc::new(RefCell::new(Node::new(data)));
  171.                 self.first = Some(f.clone());
  172.                 self.last = Some(f);
  173.             }
  174.         }
  175.     }
  176.  
  177.     // Pretty-printing
  178.     impl<T: Display> Display for List<T> {
  179.         fn fmt(&self, w: &mut std::fmt::Formatter) -> std::result::Result<(), std::fmt::Error> {
  180.             write!(w, "[")?;
  181.             let mut node = self.first.clone();
  182.             while let Some(n) = node {
  183.                 write!(w, "{}", n.borrow().data)?;
  184.                 node = n.borrow().next.clone();
  185.                 if node.is_some() {
  186.                     write!(w, ", ")?;
  187.                 }
  188.             }
  189.             write!(w, "]")
  190.         }
  191.     }
  192.  
  193.     fn main() {
  194.         let mut list = List::new();
  195.         println!("{}", list);
  196.         for i in 0..5 {
  197.             list.append(i);
  198.         }
  199.         println!("{}", list);
  200.     }
  201. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×