Over on this thread How to make rust usable in schools - #45 by ZiCog is a discussion about the suitability of using Rust as an introductory language for those that had never programmed before.
It was suggested that if one were to do that one should not teach the idea of a linked list to those beginner programmers. Especially not a doubly liked list. Which I would agree with if one thinks of a linked list in terms of nodes allocate to random memory locations and linked by references. As one might think of a linked list in C using pointers for example. Which every C beginner learns very early on, what with it being an example in the "White Book". This is a notoriously complicated thing to do in Rust: Introduction - Learning Rust With Entirely Too Many Linked Lists
My claim however was that this was not a problem, one could introduce the concept of a linked list very easily as a collection of nodes in an array or vec. Linked together by a "next" index in each node. Nodes being linked together by array indices rather than raw memory pointers. All the operations one expects to perform on a linked list, insertion, removal, search, can be done on such an array based Linked list in exactly the same way a the traditional C style linked list.
Surprising to me, some people disagreed. Stating that a linked list in a vec is somehow not a real linked list.
Some called for code to demonstrate my point.
Ok. Last week or so I was busy generating random mazes as seen in the old Unix "Hunt The Wumpus" game. The thing about the mazes is that they are a graph of 20 nodes and 30 edges. Each node has 3 links to next nodes. The links are bidirectional. I made that Wumpus graph in a Vec. It looks like this:
type Exits = Vec<usize>;
#[derive(Eq, PartialEq, Clone, Debug, Serialize, Deserialize)]
pub struct Node {
id: usize,
exits: Exits,
data: HashSet<i32>,
}
impl Node {
pub fn new(id: usize) -> Node {
Node {
id,
exits: Exits::new(),
data: HashSet::new(),
}
}
}
#[derive(Hash, Eq, PartialEq, Debug, Clone, Serialize, Deserialize)]
pub struct Edge {
node_1: usize,
node_2: usize,
}
impl Edge {
pub fn new(node_1: usize, node_2: usize) -> Edge {
let mut edge = Edge { node_1, node_2 };
if node_1 < node_2 {
std::mem::swap(&mut edge.node_1, &mut edge.node_2);
}
edge
}
pub fn to_string(&self) -> String {
format!(
" {} -- {};\n",
//" {} -> {} [dir=\"both\", weight=1];\n",
self.node_1,
self.node_2
)
}
}
pub type Nodes = Vec<Node>;
#[derive(Eq, PartialEq, Clone, Debug, Serialize, Deserialize)]
pub struct Graph {
pub nodes: Vec<Node>,
pub edges: HashSet<Edge>,
}
impl Graph {
pub fn new() -> Graph {
Graph {
nodes: vec![],
edges: HashSet::new(),
}
}
fn add(&mut self, node: Node) {
self.nodes.push(node);
}
fn connect(&mut self, start: usize, end: usize) {
self.edges.insert(Edge::new(start, end));
self.nodes[start].exits.push(end);
//self.nodes[end].exits.push(start);
}
pub fn to_string(&mut self) -> String {
let mut result: String = "".to_string();
for edge in &self.edges {
result.push_str(&edge.to_string());
}
result
}
}
pub mod wumpus_graph {
use super::{Graph, Node};
use rand::Rng;
pub fn generate(size: usize) -> super::Graph{
let mut graph = super::Graph::new();
let mut valence_2_nodes: Vec<usize> = vec![];
// Create a set of numbered nodes
for id in 0..size {
graph.add(super::Node::new(id));
}
// Create bidirectional connections of all nodes in a simple loop, thus ensuring at least one Hamiltonian path/cycle in the graph.
for id in 0..size {
graph.connect(id, (id + 1) % size);
valence_2_nodes.push(id);
}
graph.nodes[12].data.insert(4);
while !valence_2_nodes.is_empty() {
// Choose a random pair of nodes to connect.
let (n1, n2) = remove_random_pair(&mut valence_2_nodes);
// Connect the chosen nodes bidirectionally.
graph.connect(n1, n2);
}
graph
}
fn remove_random_pair<T: PartialEq + Clone>(v: &mut Vec<T>) -> (T, T) {
assert!(v.len() > 1);
let mut rng = rand::thread_rng();
let i = rng.gen_range(0, v.len());
let n1 = v[i].clone();
v.retain(|n| *n != n1);
let i = rng.gen_range(0, v.len());
let n2 = v[i].clone();
v.retain(|n| *n != n2);
(n1, n2)
}
}
Probably not brilliant. Very probably not brilliant Rust. But still, a graph, in a Vec. A doubly linked list is a subset of that. In fact the random wumpus_graph enerator starts by creating such a doubly linked list.
Can it really be said that this is less a linked list than some memory allocated arrangement using pointers?