linked_list/
linked-list.rs

1use vec_arena::Arena;
2
3/// The null index, akin to null pointers.
4///
5/// Just like a null pointer indicates an address no object is ever stored at,
6/// the null index indicates an index no object is ever stored at.
7///
8/// Number `!0` is the largest possible value representable by `usize`.
9const NULL: usize = !0;
10
11struct Node<T> {
12    /// Previous node in the list.
13    prev: usize,
14
15    /// Next node in the list.
16    next: usize,
17
18    /// Actual value stored in node.
19    value: T,
20}
21
22struct List<T> {
23    /// This is where nodes are stored.
24    arena: Arena<Node<T>>,
25
26    /// First node in the list.
27    head: usize,
28
29    /// Last node in the list.
30    tail: usize,
31}
32
33impl<T> List<T> {
34    /// Constructs a new, empty doubly linked list.
35    fn new() -> Self {
36        List {
37            arena: Arena::new(),
38            head: NULL,
39            tail: NULL,
40        }
41    }
42
43    /// Returns the number of elements in the list.
44    fn len(&self) -> usize {
45        self.arena.len()
46    }
47
48    /// Links nodes `a` and `b` together, so that `a` comes before `b` in the list.
49    fn link(&mut self, a: usize, b: usize) {
50        if a != NULL {
51            self.arena[a].next = b;
52        }
53        if b != NULL {
54            self.arena[b].prev = a;
55        }
56    }
57
58    /// Appends `value` to the back of the list.
59    fn push_back(&mut self, value: T) -> usize {
60        let node = self.arena.insert(Node {
61            prev: NULL,
62            next: NULL,
63            value: value,
64        });
65
66        let tail = self.tail;
67        self.link(tail, node);
68
69        self.tail = node;
70        if self.head == NULL {
71            self.head = node;
72        }
73        node
74    }
75
76    /// Pops and returns the value at the front of the list.
77    fn pop_front(&mut self) -> T {
78        let node = self.arena.remove(self.head).unwrap();
79
80        self.link(NULL, node.next);
81        self.head = node.next;
82        if node.next == NULL {
83            self.tail = NULL;
84        }
85        node.value
86    }
87
88    /// Removes the element specified by `index`.
89    fn remove(&mut self, index: usize) -> T {
90        let node = self.arena.remove(index).unwrap();
91
92        self.link(node.prev, node.next);
93        if self.head == index {
94            self.head = node.next;
95        }
96        if self.tail == index {
97            self.tail = node.prev;
98        }
99
100        node.value
101    }
102}
103
104fn main() {
105    let mut list = List::new();
106
107    // The list is now [].
108
109    let one = list.push_back(1);
110    list.push_back(2);
111    list.push_back(3);
112
113    // The list is now [1, 2, 3].
114
115    list.push_back(10);
116    let twenty = list.push_back(20);
117    list.push_back(30);
118
119    // The list is now [1, 2, 3, 10, 20, 30].
120
121    assert!(list.len() == 6);
122
123    assert!(list.remove(one) == 1);
124    assert!(list.remove(twenty) == 20);
125
126    // The list is now [2, 3, 10, 30].
127
128    assert!(list.len() == 4);
129
130    assert!(list.pop_front() == 2);
131    assert!(list.pop_front() == 3);
132    assert!(list.pop_front() == 10);
133    assert!(list.pop_front() == 30);
134
135    // The list is now [].
136
137    assert!(list.len() == 0);
138}
linked_list/linked-list.rs

linked_list/
linked-list.rs
