dsa_rust/sequences/doubly_linked_list.rs
1/*! A doubly-linked list implementation over raw pointers
2
3# About
4Even in 2025 you still hear stories about coding interviews that involve linked lists despite the fact that the world has mostly moved on from them. Most programs opt instead to use contiguous storage structures that take advantage of cache locality and minimal allocations despite some hard coping with amortized `O(1)` "add" operations. So why do linked lists remain? What gives these simple structures such rich lore? The reality is that its probably just a simple litmus test to ensure you were awake in your CS courses. Linked lists are traditionally introduced early on in CS programs because they provide a good introduction to the foundational concepts required to build more complex structures, such as managing references (and/or pointers) correctly (and soundly in languages that use pointers).
5
6Rust takes a notoriously different approach to pointers and memory safety from languages like C/C++ which can make otherwise simple pointer-based structures unusually difficult for Rust novices. Singly-linked lists are easy to build with safe, beginner-friendly Rust code because each node only requires a single reference in an adjacent node. Using the [`Box`] type to create pointers in singly-linked lists neatly follows Rust's "one mutable reference or many immutable references" borrowing rules. It's in doubly-linked lists where you have to start keeping multiple mutable references to an object where things get necessarily tricky.
7
8One option for safe code is to use smart pointers like [`RefCell`](std::cell::RefCell) that provide [interior mutability](https://doc.rust-lang.org/reference/interior-mutability.html). You may even choose to wrap it in a [`Rc`](std::rc::Rc) type for multiple ownership, but this approach gets unwieldy fast and requires runtime checks which may incur undesirable performance hits<sup>[1]</sup>.
9
10Pragmatically speaking, the humble linked list only really excels in situations where you need _lots_ of list alterations (think splices and splits), so you want a structure that is as performant as possible. The natural conclusion is that you must dip into the shadows of `unsafe` Rust with either [`*mut T`](https://doc.rust-lang.org/std/primitive.pointer.html) or [`NonNull`](std::ptr::NonNull) pointers to get those _blazingly fast_... linked lists.
11
12This module attempts to illustrate the delicate operations necessary to safely manage multiple sets of raw, `unsafe` pointers in Rust. Your friends all told you this was a bad idea, but I made the sacrifice to find out why so you don't have to.
13
14<sup>[1]</sup> See the chapter on `Rc<RefCell<T>>` in the famous [Learning Rust With Entirely Too Many Linked Lists](https://rust-unofficial.github.io/too-many-lists/fourth.html) book for details.
15
16# Design
17The module consists of two primary structs; [`LinkedList`] and [`CursorMut`]. The list works by storing and managing pointer-based links to (private) `Node` structs. The `LinkedList` struct itself contains links to the list's head and its tail, and stores the list's length, which is simply the number of nodes that make up the list. You do not operate on nodes directly, but rather through list and cursor operations. Each node contains data, a link to the previous node, and a link to the next node. An empty list contains no nodes, but as soon as you add a single node, that node becomes the list's head _and_ tail node. Because each node contains links to previous and next nodes, a list with a single node effectively contains two "ghost" (sentinel) nodes in front of and behind the single list node.
18
19```text
20 None <- A -> None
21```
22
23The "ghost" nodes dont have any data or any links, which provides a natural stopping point for attempts to move beyond the head or tail of the list. You can remove or replace the head and tail nodes, but you cannot define what lays beyond until you get there. 👻 Ultimately, this is an overly poetic and long-winded way to say that the list does not wrap or provide circular buffering.
24
25The list takes on a more familiar shape once you start adding nodes.
26
27```text
28 None <- A <-> B <-> C -> None
29```
30
31#### The `LinkedList` Struct
32The [`LinkedList`] struct contains methods for basic list operations. These operations allow you to use
33the list as an unsorted linked list, a stack, or a queue with insert and remove operations
34on both the front and tail of the list in `O(1)` time.
35
36```rust
37 use dsa_rust::sequences::doubly_linked_list::LinkedList;
38
39 let mut list = LinkedList::new();
40 list.push_tail("a");
41 list.push_tail("b");
42 list.push_tail("c");
43
44 print!("First: [");
45 let mut i = 0;
46 for e in list.iter() {
47 print!("{e}");
48 if i == list.len() - 1 {
49 print!("]");
50 } else {
51 print!(", ");
52 }
53 i += 1;
54 }
55```
56
57#### The `CursorMut` Struct
58Rob Pike has famously claimed to have never written a program with cursors. Unfortunately for me, I'm not as clever as Rob Pike, so this module's second major struct is [`CursorMut`]. This mutable cursor type adds positional functionality to the list and contains functions for splitting and splicing lists, and range operations.
59
60```rust
61 use dsa_rust::sequences::doubly_linked_list::LinkedList;
62
63 // First list
64 let mut first = LinkedList::new();
65 first.push_tail("a");
66 first.push_tail("b");
67 first.push_tail("c");
68 assert_eq!(first.peek_head(), Some(&"a"));
69 assert_eq!(first.peek_tail(), Some(&"c"));
70
71 // Second list
72 let mut second = LinkedList::new();
73 second.push_tail("1");
74 second.push_tail("2");
75 second.push_tail("3");
76 second.push_tail("4");
77 assert_eq!(second.peek_head(), Some(&"1"));
78 assert_eq!(second.peek_tail(), Some(&"4"));
79
80 // Spliced
81 // Postcondition: [1, 2, a, b, c, 3, 4]
82 let mut cur = second.cursor_mut();
83 cur.move_next(); // 0
84 cur.move_next(); // 1
85 cur.splice_after(first);
86 assert_eq!(second.peek_head(), Some(&"1"));
87 assert_eq!(second.peek_tail(), Some(&"4"));
88
89 eprint!("All together now: [");
90 for (i, e) in second.iter().enumerate() {
91 eprint!("{e}");
92 if i == second.len() - 1 {
93 eprintln!("]");
94 } else {
95 eprint!(", ");
96 }
97 }
98
99 // Range split
100 // Postcondition: [1, 2] [a, b, c, 3, 4]
101 let mut cur = second.cursor_mut();
102 cur.move_next(); // 0
103 cur.move_next(); // 1
104 let mut new_list = cur.split_after(); // splits after "2"
105 assert_eq!(new_list.peek_head(), Some(&"a"));
106 assert_eq!(new_list.peek_tail(), Some(&"4"));
107
108 // Postcondition: [1, 2] [a, b, c] [3, 4]
109 let mut new_cur = new_list.cursor_mut();
110 new_cur.move_next(); // 0
111 new_cur.move_next(); // 1
112 new_cur.move_next(); // 2
113 let new_back = new_cur.split_after(); // splits again after "c"
114
115 // Reassembles the two numbered lists
116 // Postcondition: [1, 2, 3, 4] [a, b, c]
117 cur.splice_after(new_back);
118 drop(cur);
119
120 // Makes sure everything is as it seems
121 assert_eq!(new_list.peek_head(), Some(&"a"));
122 assert_eq!(new_list.peek_tail(), Some(&"c"));
123 assert_eq!(second.peek_head(), Some(&"1"));
124 assert_eq!(second.peek_tail(), Some(&"4"));
125
126 // Prints everything, in case you're a visual learner like me
127 eprint!("Split numbers: [");
128 for (i, e) in second.iter().enumerate() {
129 eprint!("{e}");
130 if i == second.len() - 1 {
131 eprintln!("]");
132 } else {
133 eprint!(", ");
134 }
135 }
136 eprint!("Split letters: [");
137 for (i, e) in new_list.iter().enumerate() {
138 eprint!("{e}");
139 if i == new_list.len() - 1 {
140 eprintln!("]");
141 } else {
142 eprint!(", ");
143 }
144 }
145 //panic!("Uncomment to show me them beautiful lists");
146```
147*/
148
149// Creates a raw pointer to some Node
150type Link<T> = Option<*mut Node<T>>;
151
152#[derive(Debug)]
153struct Node<T> {
154 data: T,
155 prev: Link<T>,
156 next: Link<T>,
157}
158/// # About
159/// All operations run in `O(1)` time unless otherwise noted. See the [module-level documentation](`crate::lists::doubly_linked_list`) for more information.
160#[derive(Debug)]
161pub struct LinkedList<T> {
162 head: Link<T>,
163 tail: Link<T>,
164 len: usize,
165}
166impl<T> Default for LinkedList<T> {
167 fn default() -> Self {
168 Self::new()
169 }
170}
171impl<T> LinkedList<T> {
172 /** Creates a new list */
173 pub fn new() -> LinkedList<T> {
174 LinkedList {
175 head: None,
176 tail: None,
177 len: 0,
178 }
179 }
180
181 /// Inserts a node at the head of the list.
182 ///
183 /// Can be used like a `push(k)` or `add(k)` operation for a stack.
184 pub fn push_head(&mut self, element: T) {
185 // Creates a NonNull<Node<T>> wrapper from a *mut pointer to the
186 // (new) unique heap object
187 let new_node_wrapper: *mut Node<T> = Box::into_raw(Box::new(Node {
188 data: element,
189 prev: None,
190 next: None,
191 })); // Unsafe
192
193 // If there are already elements in the list...
194 if let Some(node) = self.head {
195 // Sets the new node's next pointer to the current head
196 // SAFETY: New node was just allocated and is not aliased
197 unsafe { (*new_node_wrapper).next = self.head };
198 // Sets the original head's prev pointer to the new node
199 // SAFETY: self.head guaranteed to be non-null
200 unsafe { (*node).prev = Some(new_node_wrapper) };
201 }
202 // Inserts into empty list
203 else {
204 //println!("Inserts at head");
205 // Sets the list's head and tail pointers to the new node
206 self.tail = Some(new_node_wrapper);
207 }
208
209 // Resets the list's head and increments the list size
210 self.head = Some(new_node_wrapper);
211 self.len += 1;
212 }
213
214 /// Returns a reference to the data at the list's head,
215 /// if the list has a head node.
216 pub fn peek_head(&self) -> Option<&T> {
217 if let Some(node_ptr) = self.head {
218 // SAFETY: Creates an immutable reference to a guaranteed non-null
219 // allocation with properly initialized data field
220 let node = unsafe { &(*node_ptr).data };
221 Some(node)
222 } else {
223 None
224 }
225 }
226
227 /// Returns a reference to the data at the list's tail, if the list has a tail.
228 pub fn peek_tail(&self) -> Option<&T> {
229 unsafe {
230 if let Some(node_ptr) = self.tail {
231 let node = &(*node_ptr).data;
232 Some(node)
233 } else {
234 None
235 }
236 }
237 }
238
239 /// Returns an owned value of the head Node's data.
240 /// Use like a `pop()` or a `dequeue()` operation for a stack or queue.
241 pub fn pop_head(&mut self) -> Option<T> {
242 if let Some(head_ptr) = self.head {
243 // Takes ownership
244 // SAFETY:
245 let boxed_node: Box<Node<T>> = unsafe { Box::from_raw(head_ptr) };
246 // Resets the list head to the original head's next pointer
247 self.head = boxed_node.next;
248 self.len -= 1;
249 // Returns the old head's data
250 return Some(boxed_node.data);
251 }
252 None
253 }
254
255 /// Inserts a node at the tail of the list. Use like an `enqueue()`
256 /// operation for a queue.
257 pub fn push_tail(&mut self, element: T) {
258 // Creates a raw *mut pointer to the (new) unique heap object
259 let new_node_wrapper: *mut Node<T> = Box::into_raw(Box::new(Node {
260 data: element,
261 prev: None,
262 next: None,
263 }));
264
265 // Case 1: If there are already elements in the list...
266 if let Some(node) = self.tail {
267 // Sets the new node's prev pointer to the current tail
268 // SAFETY:
269 unsafe { (*new_node_wrapper).prev = self.tail };
270 // Sets the original tail's next pointer to the new node
271 // SAFETY:
272 unsafe { (*node).next = Some(new_node_wrapper) };
273 }
274 // Case 2: Inserts into empty list
275 else {
276 // Sets the list's head and tail pointers to the new node
277 self.head = Some(new_node_wrapper);
278 }
279
280 // Resets the list's tail and increments the list size
281 self.tail = Some(new_node_wrapper);
282 self.len += 1;
283 }
284
285 /// Removes and returns the tail node of the list.
286 pub fn pop_tail(&mut self) -> Option<T> {
287 if let Some(tail_ptr) = self.tail {
288 // Takes ownership
289 let boxed_node: Box<Node<T>> = unsafe { Box::from_raw(tail_ptr) };
290
291 // Update list tail pointer
292 self.tail = boxed_node.prev;
293
294 // If the new tail exists, its next pointer should be None
295 if let Some(new_tail_ptr) = self.tail {
296 unsafe { (*new_tail_ptr).next = None };
297 } else {
298 // If there was only one element, we must also update head
299 self.head = None;
300 }
301
302 self.len -= 1;
303 return Some(boxed_node.data); // Return the old tail's data
304 }
305 None
306 }
307
308 /// Returns the length of the list.
309 pub fn len(&self) -> usize {
310 self.len
311 }
312
313 /// Returns a Boolean indicating whether the list is empty.
314 pub fn is_empty(&self) -> bool {
315 self.head.is_none()
316 }
317
318 /// Clears all elements from the list in `O(n)` time.
319 pub fn clear(&mut self) {
320 //while self.iter().next.is_some() {
321 // self.pop_head();
322 //}
323 while self.pop_head().is_some() {}
324 }
325
326 /// Returns an iterator of references to data in the list's nodes as
327 /// `list.iter()`.
328 pub fn iter(&self) -> Iter<'_, T> {
329 Iter {
330 next: self.head,
331 // Needed for lifetime tracking
332 _marker: std::marker::PhantomData,
333 }
334 }
335
336 //iter_rev() -> Iter
337 //pub fn contains(&T) -> bool {}
338 //pub fn find(&T) -> Link<T> {}
339
340 /// Acts like a constructor for a cursor.
341 pub fn cursor_mut(&mut self) -> CursorMut<'_, T> {
342 CursorMut {
343 cursor: None,
344 list: self,
345 index: None,
346 }
347 }
348}
349
350pub struct Iter<'a, T> {
351 // Link, aka Option<*mut Node<T>>
352 next: Link<T>,
353 // Ensures correct lifetime tracking
354 _marker: std::marker::PhantomData<&'a T>,
355}
356impl<'a, T> Iterator for Iter<'a, T> {
357 type Item = &'a T;
358
359 fn next(&mut self) -> Option<Self::Item> {
360 if let Some(current) = self.next {
361 // SAFETY:
362 unsafe {
363 self.next = (*current).next; // Move to next node
364 Some(&(*current).data) // Return reference to data
365 }
366 } else {
367 None
368 }
369 }
370}
371
372impl<T> Drop for LinkedList<T> {
373 // LinkedList destructor works by popping each node into a Box
374 // which contains its own Drop semantics and cleans everything
375 // up nicely for us.
376 fn drop(&mut self) {
377 while self.pop_head().is_some() {}
378 // Manual implementation
379 //unsafe {
380 // let mut current_node_ptr = self.head;
381 // while let Some(ptr) = current_node_ptr {
382 // // Store a pointer to the next Node before deallocating the
383 // // current one
384 // let next_node_ptr = (*ptr.as_ptr()).next;
385
386 // // Deallocate the current node
387 // let _ = Box::from_raw(ptr.as_ptr());
388
389 // // Advance the Node pointer
390 // current_node_ptr = next_node_ptr;
391 // }
392 //}
393 }
394}
395
396/// # About
397/// Its the great cursor, Charlie Brown!
398///
399/// See the [module-level documentation](`crate::lists::doubly_linked_list`) for more information.
400pub struct CursorMut<'a, T> {
401 cursor: Link<T>,
402 list: &'a mut LinkedList<T>,
403 index: Option<usize>,
404}
405impl<T> CursorMut<'_, T> {
406 /// Returns `true` if the cursor points to Some, indicating that the cursor
407 /// is on a valid Node.
408 pub fn is_some(&self) -> bool {
409 self.cursor.is_some()
410 }
411
412 /// Returns `true` if the cursor points to None, indicating that the cursor
413 /// is on a ghost node.
414 pub fn is_none(&self) -> bool {
415 self.cursor.is_none()
416 }
417
418 /// Returns the "index" to the current list node in a zero-indexed sequence
419 fn _index(&self) -> Option<usize> {
420 self.index
421 }
422
423 /// Advances the cursor to the next node in the list, moving from head to tail.
424 /// If the cursor is at the ghost (pre-head) position and the list is
425 /// non-empty, it moves to the head. The function is a no-op if the cursor
426 /// is already at the tail or the list is empty.
427 pub fn move_next(&mut self) {
428 // Case 1) The current position is real, follow the next pointer
429 if let Some(cur) = self.cursor {
430 // SAFETY: The next pointer is to either Some or None,
431 // but always valid.
432 self.cursor = unsafe { (*cur).next };
433 // If Some, go there
434 if self.cursor.is_some() {
435 *self.index.as_mut().unwrap() += 1;
436 // If None, do nothing
437 } else {
438 self.index = None;
439 // no-op
440 }
441 // Case 2) The current position isn't real and the list is not
442 // empty, the next logical position must be the list's head
443 } else if !self.list.is_empty() {
444 self.cursor = self.list.head;
445 self.index = Some(0)
446 // Case 3) The cursor is at the ghost, but the list is empty,
447 // so theres nowhere to go and nothing to do
448 } else {
449 // no-op
450 }
451 }
452
453 /// Advances the cursor to the previous node in the list,
454 /// moving from head to tail. The function is a no-op if the cursor
455 /// is already at the head or the list is empty.
456 pub fn move_prev(&mut self) {
457 // Case 1) The current position is real, follow the prev pointer
458 if let Some(cur) = self.cursor {
459 // SAFETY: The prev pointer is to either Some or None,
460 // but always valid.
461 self.cursor = unsafe { (*cur).prev };
462 // If Some, go there
463 if self.cursor.is_some() {
464 *self.index.as_mut().unwrap() -= 1;
465 // If None, do nothing
466 } else {
467 self.index = None;
468 // no-op
469 }
470 // Case 2) The current position isn't real and the list is not empty,
471 // the next logical position must be the list's tail
472 } else if !self.list.is_empty() {
473 self.cursor = self.list.tail;
474 self.index = Some(self.list.len - 1)
475 // Case 3) The cursor is at the ghost, but theres nowhere to go
476 } else {
477 // no-op
478 }
479 }
480
481 /// Returns a mutable reference to the data at the current position.
482 /// It is necessary to return a _mutable_ reference to retain the elision
483 /// rule checks.
484 pub fn current(&mut self) -> Option<&mut T> {
485 self.cursor.map(|node| {
486 // SAFETY: node only gets dereferenced if cursor is Some,
487 // so its assumed to point to a valid and properly initialized Node
488 unsafe { &mut (*node).data }
489 })
490 }
491
492 /// Returns a mutable reference to the data at the next node's position.
493 /// It's necessary to return a _mutable_ reference to retain the elision
494 /// rule checks.
495 pub fn peek_next(&mut self) -> Option<&mut T> {
496 let next = if let Some(cur) = self.cursor {
497 // SAFETY:
498 unsafe { (*cur).next }
499 } else {
500 // Ghost case, try to use the list's head pointer
501 self.list.head
502 };
503 // Yield the data if the next node exists
504 // SAFETY:
505 unsafe { next.map(|node| &mut (*node).data) }
506 }
507
508 /** Returns a mutable reference to the data at the previous node's position;
509 It is necessary to return a _mutable_ reference to retain the elision
510 rule checks */
511 pub fn peek_prev(&mut self) -> Option<&mut T> {
512 unsafe {
513 let prev = if let Some(cur) = self.cursor {
514 (*cur).prev
515 } else {
516 // If you're at the ghost, point to the tail
517 self.list.tail
518 };
519 // Yield the data if the prev node exists
520 prev.map(|node| &mut (*node).data)
521 }
522 }
523
524 /// Inserts a node before the cursor;
525 ///
526 /// - If the cursor is on the ghost node of an empty list,
527 /// the new node becomes the new head and tail;
528 ///
529 /// - If the cursor is on the ghost node of a non-empty list,
530 /// the new node becomes the new tail;
531 ///
532 /// - If the cursor is on the head, the new node is the new head;
533 ///
534 /// Precondition:
535 ///
536 /// ```text
537 /// self.head -> A <-> C <- self.tail
538 /// ^
539 /// cursor
540 /// ```
541 ///
542 /// Postcondition:
543 ///
544 /// ```text
545 /// self.head -> A <-> B <-> C <- self.tail
546 /// ^
547 /// cursor
548 /// ```
549 pub fn insert_before(&mut self, element: T) {
550 let new_node_wrapper: *mut Node<T> = Box::into_raw(Box::new(Node {
551 data: element,
552 prev: None,
553 next: None,
554 }));
555
556 // Case 1) The cursor is at the ghost of an empty list;
557 // new head/tail
558 if self.cursor.is_none() && self.list.head.is_none() {
559 self.list.head = Some(new_node_wrapper);
560 self.list.tail = Some(new_node_wrapper);
561 }
562 // Case 2) The cursor is at the ghost of a non-empty list; new tail
563 else if self.cursor.is_none() && self.list.head.is_some() {
564 // Update the old tail's next pointer
565 let old_tail = self.list.tail.unwrap();
566 unsafe {
567 (*old_tail).next = Some(new_node_wrapper);
568 }
569
570 // Update the new node's prev pointer
571 unsafe {
572 (*new_node_wrapper).prev = Some(old_tail);
573 }
574
575 // Update the list's tail
576 self.list.tail = Some(new_node_wrapper);
577 }
578 // Case 3) The cursor is at the head of a non-empty list; new head
579 else if self.cursor == self.list.head && self.list.head.is_some() {
580 // Update the old head's prev pointer
581 let old_head = self.list.head.unwrap();
582 unsafe {
583 (*old_head).prev = Some(new_node_wrapper);
584 }
585
586 // Update the new node's next pointer
587 unsafe {
588 (*new_node_wrapper).next = Some(old_head);
589 }
590
591 // Update the list.head pointer
592 self.list.tail = Some(new_node_wrapper);
593 }
594 // Case 4) The cursor is somewhere between head+1 and tail of
595 // a non-empty list; reset all four pointers
596 else {
597 unsafe {
598 // Capture the node prior to the cursor node
599 // and start orgy of pointer swapping
600 let cursor_node = self.cursor.unwrap();
601 let old_prev = (*cursor_node).prev.unwrap();
602 (*old_prev).next = Some(new_node_wrapper);
603 (*new_node_wrapper).prev = Some(old_prev);
604 (*new_node_wrapper).next = Some(cursor_node);
605 (*cursor_node).prev = Some(new_node_wrapper);
606 }
607 }
608
609 // All cases
610 // - Adjust the cursor's index
611 // - Increment list len
612 if self.index.is_some() {
613 let mut new_index = self.index.unwrap();
614 new_index += 1;
615 self.index = Some(new_index);
616 } else {
617 self.index = Some(0)
618 };
619 self.list.len += 1;
620 }
621
622 /// Inserts a node after the cursor;
623 ///
624 /// - If the cursor is on the ghost node of an empty list,
625 /// the new node becomes the new head and tail;
626 ///
627 /// - If the cursor is on the ghost node of a non-empty list,
628 /// the new node becomes the new head;
629 ///
630 /// - If the cursor is on the tail, the new node is the new tail;
631 ///
632 /// Precondition:
633 ///
634 /// ```text
635 /// self.head -> A <-> C <- self.tail
636 /// ^
637 /// cursor
638 /// ```
639 ///
640 /// Postcondition:
641 ///
642 /// ```text
643 /// self.head -> A <-> B <-> C <- self.tail
644 /// ^
645 /// cursor
646 /// ```
647 pub fn insert_after(&mut self, element: T) {
648 let new_node_wrapper: *mut Node<T> = Box::into_raw(Box::new(Node {
649 data: element,
650 prev: None,
651 next: None,
652 }));
653
654 // Case 1) The cursor is at the ghost node in an empty list;
655 // new head/tail
656 if self.cursor.is_none() && self.list.head.is_none() {
657 self.list.head = Some(new_node_wrapper);
658 self.list.tail = Some(new_node_wrapper);
659 }
660 // Case 2) The cursor is at the ghost node in a non-empty list; new head
661 else if self.cursor.is_none() && self.list.head.is_some() {
662 // Capture the old head node
663 let old_head = self.list.head.unwrap();
664
665 // Update the old_head.prev to new node
666 unsafe {
667 (*old_head).prev = Some(new_node_wrapper);
668 }
669
670 // Update the new node.next to old_head
671 unsafe {
672 (*new_node_wrapper).next = Some(old_head);
673 }
674
675 // Update the list's head
676 self.list.head = Some(new_node_wrapper);
677 }
678 // Case 3) The cursor is at the tail of a non-empty list; new tail
679 else if self.cursor == self.list.tail && self.list.tail.is_some() {
680 // Capture the old tail
681 let old_tail = self.list.tail.unwrap();
682
683 // Update the old_tail.next to the new_node
684 unsafe {
685 (*old_tail).next = Some(new_node_wrapper);
686 }
687
688 // Update the new_node.prev to old_tail
689 unsafe {
690 (*new_node_wrapper).prev = Some(old_tail);
691 }
692
693 // Update the list.tail
694 self.list.tail = Some(new_node_wrapper);
695 }
696 // Case 4) The cursor is somewhere between head and tail-1 of
697 // a non-empty list
698 else {
699 unsafe {
700 // Capture the node after the current cursor node
701 // and start orgy of pointer swapping
702 let cursor_node = self.cursor.unwrap();
703 let old_next = (*cursor_node).next.unwrap();
704 (*old_next).prev = Some(new_node_wrapper);
705 (*new_node_wrapper).prev = Some(cursor_node);
706 (*new_node_wrapper).next = Some(old_next);
707 (*cursor_node).next = Some(new_node_wrapper);
708 }
709 }
710
711 // All cases
712 // - Increment list len
713 self.list.len += 1;
714 }
715
716 /// Removes and returns the data under the cursor's current position
717 /// and moves the cursor back one position
718 ///
719 /// Precondition:
720 ///
721 /// ```text
722 /// self.head -> A <-> B <-> C <-> D <- self.tail
723 /// ^
724 /// cursor
725 /// ```
726 ///
727 /// Postcondition:
728 ///
729 /// ```text
730 /// self.head -> A <-> B <-> D <- self.tail
731 /// ^
732 /// cursor
733 /// ```
734 pub fn remove_current(&mut self) -> Option<T> {
735 unsafe {
736 // Case 1) You're at the ghost, do nothing
737 //if self.current().is_none() { return None; }
738
739 // Case 2) You're in a non-empty list
740 let node_data = if let Some(node_ptr) = self.cursor {
741 // 2.1 You're at the head
742 if (*node_ptr).prev.is_none() {
743 // Reset the head and its pointers
744 if let Some(next_node) = (*node_ptr).next {
745 (*next_node).prev = None;
746 self.list.head = (*node_ptr).next;
747 }
748 }
749 // 2.2 You're at the tail
750 else if (*node_ptr).next.is_none() {
751 // Reset the head and its pointers
752 if let Some(next_node) = (*node_ptr).prev {
753 (*next_node).next = None;
754 self.list.tail = (*node_ptr).prev;
755 }
756
757 // 2.3 You're somewhere mid-list
758 } else {
759 // Reset the previous node's next
760 if let Some(prev_node) = (*node_ptr).prev {
761 (*prev_node).next = (*node_ptr).next;
762 }
763 // Resent the next node's prev
764 if let Some(next_node) = (*node_ptr).next {
765 (*next_node).prev = (*node_ptr).prev;
766 }
767 };
768 // For all non-empty list cases,
769 // take the cursor's underlying raw pointer data
770 // and adjust the cursor's position
771 self.move_prev(); // handles index placement too
772 let data: Box<Node<T>> = Box::from_raw(node_ptr);
773 Some(data.data)
774
775 // Just in case self.cursor is None (ghost)
776 } else {
777 None
778 };
779 // Decrement the underlying list's length and return
780 self.list.len -= 1;
781 node_data
782 }
783 }
784
785 /// Returns a new list containing all nodes before the cursor,
786 /// modifying `self` to become all nodes after (and including) the cursor.
787 ///
788 /// Precondition:
789 ///
790 /// ```text
791 /// self.head -> A <-> B <-> C <-> D <- self.tail
792 /// ^
793 /// cursor
794 /// ```
795 ///
796 /// Postcondition:
797 ///
798 /// ```text
799 /// self.head -> C <-> D <- self.tail
800 /// ^
801 /// cursor
802 ///
803 /// return.head -> A <-> B <- return.tail
804 /// ```
805 pub fn split_before(&mut self) -> LinkedList<T> {
806 // Case 1) The cursor is on an element of a non-empty list
807 if let Some(node_ptr) = self.cursor {
808 unsafe {
809 // Captures current state of self
810 let old_len = self.list.len;
811 let old_index = self.index.unwrap();
812 let prev = (*node_ptr).prev;
813
814 // What self will become
815 let new_len = old_len - old_index;
816 let new_head = self.cursor;
817 let new_index = Some(0);
818
819 // What the output will become
820 let output_len = old_len - new_len;
821 let output_head = self.list.head;
822 let output_tail = prev;
823
824 // If the cursor is NOT at a ghost node,
825 // break pointer links at split:
826 // - cursor_next is the new list's head
827 // - node_ptr is the origial list's tail
828 if let Some(prev) = prev {
829 (*node_ptr).prev = None;
830 (*prev).next = None;
831 }
832
833 // Modify self
834 self.list.len = new_len;
835 self.list.head = new_head;
836 self.index = new_index;
837
838 // Return the new list
839 LinkedList {
840 head: output_head,
841 tail: output_tail,
842 len: output_len,
843 //_marker: PhantomData,
844 }
845 }
846
847 // Case 2) The cursor is on the ghost node;
848 // replace self with an empty list, return the original list
849 // EDIT: replace self with None, return the original list
850 } else {
851 //std::mem::replace(self.list, LinkedList::new())
852 std::mem::take(self.list)
853 }
854 }
855
856 /// Returns a new list that includes all nodes after the cursor,
857 /// modifying self to become all nodes before (and including) the cursor
858 ///
859 /// Precondition:
860 ///
861 /// ```text
862 /// self.head -> A <-> B <-> C <-> D <- self.tail
863 /// ^
864 /// cursor
865 /// ```
866 ///
867 /// Postcondition:
868 ///
869 /// ```text
870 /// self.head -> A <-> B <- self.tail
871 /// ^
872 /// cursor
873 ///
874 /// return.head -> C <-> D <- return.tail
875 /// ```
876 pub fn split_after(&mut self) -> LinkedList<T> {
877 // Case 1) The cursor is not on the ghost node
878 if let Some(node_ptr) = self.cursor {
879 unsafe {
880 // Captures current state of self
881 let old_len = self.list.len;
882 let old_index = self.index.unwrap();
883 let cursor_next = (*node_ptr).next;
884
885 // What self will become
886 let new_len = old_index + 1;
887 let new_tail = self.cursor;
888 let new_index = Some(old_index);
889
890 // What the output will become
891 let output_len = old_len - new_len;
892 let output_head = cursor_next;
893 let output_tail = self.list.tail;
894
895 // If the cursor is NOT at the end of the list,
896 // break pointer links at split:
897 // - cursor_next is the new list's head
898 // - node_ptr is the origial list's tail
899 if let Some(next_ptr_unwrapped) = cursor_next {
900 (*node_ptr).next = None;
901 (*next_ptr_unwrapped).prev = None;
902 }
903
904 // Modify self
905 self.list.len = new_len;
906 self.list.tail = new_tail;
907 self.index = new_index;
908
909 // Return the new list
910 LinkedList {
911 head: output_head,
912 tail: output_tail,
913 len: output_len,
914 //_marker: PhantomData,
915 }
916 }
917
918 // Case 2) The cursor is on the ghost node;
919 // replace self with an empty list, return the original list
920 // EDIT: replace self with None, return the original list
921 } else {
922 //std::mem::replace(self.list, LinkedList::new())
923 std::mem::take(self.list)
924 }
925 }
926
927 /// Splices in a new list between the cursor node and the previous node
928 ///
929 /// Precondition:
930 ///
931 /// ```text
932 /// self.head -> A <-> B <-> C <- self.tail
933 /// ^
934 /// cursor
935 ///
936 /// input.head -> 1 <-> 2 <- input.tail
937 /// ```
938 ///
939 /// Postcondition:
940 ///
941 /// ```text
942 /// self.head -> A <-> 1 <-> 2 <-> B <-> C <- self.back
943 /// ^
944 /// cursor
945 /// ```
946 pub fn splice_before(&mut self, mut input: LinkedList<T>) {
947 unsafe {
948 // Case 1) Input list is empty; do nothing. Easy!
949 if input.is_empty() {
950 }
951 // Case 2) Self is non-empty
952 else if let Some(cur) = self.cursor {
953 // Per the Too Many Linked LinkedLists Book:
954 // We can either `take` the input's pointers or `mem::forget`
955 // it [sic]. Using `take` is more responsible in case we ever
956 // do custom allocators or something that also needs to be
957 // cleaned up!
958 let input_head = input.head.take().unwrap();
959 let input_tail = input.tail.take().unwrap();
960
961 // 2.1) Cursor is somewhere inside a non-empty self;
962 // puttin a list inside another list
963 if let Some(prev) = (*cur).prev {
964 (*prev).next = Some(input_head);
965 (*input_head).prev = Some(prev);
966 (*cur).prev = Some(input_tail);
967 (*input_tail).next = Some(cur);
968
969 // 2.2) Cursor is at self.head, prepend self with input list
970 } else {
971 (*cur).prev = Some(input_tail);
972 (*input_tail).next = Some(cur);
973 self.list.head = Some(input_head);
974 }
975 // Index moves forward by input length
976 *self.index.as_mut().unwrap() += input.len;
977
978 // Case 3) Cursor is on the ghost node for a non-empty list,
979 // prepend self with input
980 } else if let Some(_back) = self.list.tail {
981 let input_head = input.head.take().unwrap();
982 let input_tail = input.tail.take().unwrap();
983 self.list.head = Some(input_head);
984 self.list.tail = Some(input_tail);
985 } else {
986 // Self is empty, swap in the input list, remain on the ghost
987 std::mem::swap(self.list, &mut input);
988 }
989
990 self.list.len += input.len;
991 // Not necessary but Polite To Do
992 input.len = 0; // Input dropped at end of block
993 }
994 }
995
996 /// Splices in a new list between the cursor node and the next node
997 ///
998 /// Precondition
999 ///
1000 /// ```text
1001 /// self.head -> A <-> B <-> C <- self.tail
1002 /// ^
1003 /// cursor
1004 ///
1005 /// input.head -> 1 <-> 2 <- input.tail
1006 /// ```
1007 ///
1008 /// Postcondition
1009 ///
1010 /// ```text
1011 /// self.head -> A <-> B <-> 1 <-> 2 <-> C <- self.tail
1012 /// ^
1013 /// cursor
1014 /// ```
1015 pub fn splice_after(&mut self, mut input: LinkedList<T>) {
1016 unsafe {
1017 // Case 1) Input list is empty, do nothing! Easy.
1018 if input.is_empty() {
1019 }
1020 // Case 2) Self is non-empty
1021 else if let Some(cur) = self.cursor {
1022 // From the Too Many Linked LinkedList book:
1023 // We can either `take` the input's pointers or `mem::forget`
1024 // it [sic]. Using `take` is more responsible in case we ever
1025 // do custom allocators or something that also needs to be
1026 // cleaned up!
1027 let input_head = input.head.take().unwrap();
1028 let input_tail = input.tail.take().unwrap();
1029
1030 // 2.1) Cursor is somewhere in a non-empty list; swap pointers ;)
1031 if let Some(next) = (*cur).next {
1032 (*next).prev = Some(input_tail);
1033 (*input_tail).next = Some(next);
1034 (*cur).next = Some(input_head);
1035 (*input_head).prev = Some(cur);
1036
1037 // 2.2) Cursor is at tail, append self
1038 } else {
1039 (*cur).next = Some(input_head);
1040 (*input_head).prev = Some(cur);
1041 self.list.tail = Some(input_tail);
1042 }
1043
1044 // Case 3) Cursor is at the ghost node in a non-empty self, prepend self
1045 } else if let Some(head) = self.list.head {
1046 let input_head = input.head.take().unwrap();
1047 let input_tail = input.tail.take().unwrap();
1048
1049 (*head).next = Some(input_tail);
1050 (*input_tail).prev = Some(head);
1051 self.list.head = Some(input_head);
1052
1053 // Case 4) Cursor is at the ghost node for an empty self, do a swaperoo
1054 } else {
1055 std::mem::swap(self.list, &mut input);
1056 }
1057 // Increase the list's lenth value
1058 self.list.len += input.len;
1059 }
1060 }
1061}
1062
1063#[cfg(test)]
1064#[allow(clippy::items_after_test_module)] // Example runner comes after tests
1065mod list_tests {
1066 use super::*;
1067
1068 #[test]
1069 fn list_test() {
1070 use crate::sequences::doubly_linked_list::{CursorMut, LinkedList};
1071
1072 // Operational tests
1073 // Creates a new doubly-linked list
1074 // and pushes some elements to it
1075 let mut list = LinkedList::new();
1076 assert!(list.is_empty()); // New list is empty
1077 list.push_head("a");
1078 list.push_head("b");
1079 list.push_head("c"); // Postcondition: [c, b, a]
1080 assert!(!list.is_empty()); // LinkedList now has stuff
1081
1082 // Tests the cursor which starts at a non-existant "ghost" node
1083 // Remember: only one mutable reference at a time!
1084 let mut cur: CursorMut<'_, &str> = list.cursor_mut();
1085 cur.move_next(); // 0
1086 cur.move_next(); // 1
1087 cur.move_next(); // 2
1088 //assert_eq!(cur.index(), Some(2));
1089 assert_eq!(cur.current(), Some(&mut "a"));
1090
1091 // Tests the pop operations
1092 let mut popped_head: &str = list.pop_head().unwrap();
1093 assert_eq!(popped_head, "c");
1094 popped_head = list.pop_head().unwrap();
1095 assert_eq!(popped_head, "b");
1096 // Postcondition: [a]
1097
1098 list.push_head("b");
1099 list.push_head("c");
1100 // Postcondition: [c, b, a]
1101
1102 assert_eq!(list.len, 3);
1103
1104 let mut popped_tail: &str = list.pop_tail().unwrap();
1105 assert_eq!(popped_tail, "a");
1106 popped_tail = list.pop_tail().unwrap();
1107 assert_eq!(popped_tail, "b");
1108 // Postcondition: [c]
1109
1110 assert_eq!(list.len(), 1);
1111
1112 // Adds some elements for the pointer tests
1113 list.push_tail("b");
1114 list.push_tail("a");
1115 // Postcondition: [c, b, a]
1116
1117 assert_eq!(list.len(), 3);
1118
1119 // Creates a new doubly-linked list
1120 // and pushes some elements to it
1121 let mut list = LinkedList::new();
1122 list.push_head("a");
1123 list.push_head("b");
1124 list.push_head("c"); // Postcondition: [c, b, a]
1125
1126 // Checks that head -> c
1127 let head_ptr: *mut Node<&str> = list.head.unwrap();
1128 let head: &str = unsafe { (*head_ptr).data }; // Unsafe deref
1129 assert_eq!(head, "c");
1130
1131 // Checks that head.next -> b
1132 let next_ptr: *mut Node<&str> = unsafe { (*list.head.unwrap()).next.unwrap() };
1133 let next: &str = unsafe { (*next_ptr).data }; // Unsafe deref
1134 assert_eq!(next, "b");
1135
1136 // Checks that head.prev -> None
1137 let prev_ptr: Option<*mut Node<&str>> = unsafe { (*list.head.unwrap()).prev };
1138 assert!(prev_ptr.is_none());
1139
1140 // Checks that b.prev -> head
1141 let prev_ptr: *mut Node<&str> = unsafe { (*next_ptr).prev.unwrap() };
1142 let prev: &str = unsafe { (*prev_ptr).data }; // Unsafe deref
1143 assert_eq!(prev, "c");
1144
1145 // Checks that tail -> a
1146 let tail_ptr: *mut Node<&str> = list.tail.unwrap();
1147 let tail: &str = unsafe { (*tail_ptr).data }; // Unsafe deref
1148 assert_eq!(tail, "a");
1149
1150 // Checks that tail.prev -> b
1151 let prev_ptr: *mut Node<&str> = unsafe { (*tail_ptr).prev.unwrap() };
1152 let prev: &str = unsafe { (*prev_ptr).data }; // Unsafe deref
1153 assert_eq!(prev, "b");
1154
1155 // Checks that tail.next -> None
1156 let next_ptr: Option<*mut Node<&str>> = unsafe { (*list.tail.unwrap()).next };
1157 assert!(next_ptr.is_none());
1158
1159 // Clears list and checks that its empty
1160 list.clear();
1161 assert!(list.is_empty());
1162 assert_eq!(list.len(), 0);
1163 }
1164
1165 #[test]
1166 fn cursor_test() {
1167 use crate::sequences::doubly_linked_list::{CursorMut, LinkedList};
1168
1169 // Creates a new doubly-linked list
1170 // and pushes some elements to it
1171 let mut list = LinkedList::new();
1172 assert!(list.is_empty()); // New list is empty
1173 list.push_head("a");
1174 list.push_head("b");
1175 list.push_head("c"); // Postcondition: [c, b, a]
1176 assert!(!list.is_empty()); // LinkedList now has stuff
1177
1178 // Tests the cursor which starts at a non-existant "ghost" node
1179 // Remember: only one mutable reference at a time!
1180 let mut cur: CursorMut<'_, &str> = list.cursor_mut();
1181 cur.move_next(); // 0
1182 cur.move_next(); // 1
1183 cur.move_next(); // 2
1184 assert_eq!(cur._index(), Some(2));
1185 assert_eq!(cur.current(), Some(&mut "a"));
1186
1187 cur.move_prev(); // 1
1188 cur.move_prev(); // 0
1189 assert_eq!(cur._index(), Some(0));
1190 assert_eq!(cur.current(), Some(&mut "c"));
1191
1192 // Moves beyond the list.head to the ghost node
1193 cur.move_prev(); // Boo! 👻
1194 assert_eq!(cur._index(), None);
1195 assert_eq!(cur.current(), None);
1196
1197 // Wraps back around!
1198 cur.move_prev(); // 2
1199 assert_eq!(cur._index(), Some(2));
1200 assert_eq!(cur.current(), Some(&mut "a"));
1201
1202 // Next is the ghost, but peek doesn't change the current position
1203 let peek = cur.peek_next();
1204 assert_eq!(peek, None);
1205 assert_eq!(cur._index(), Some(2));
1206 assert_eq!(cur.current(), Some(&mut "a"));
1207
1208 let peek = cur.peek_prev();
1209 assert_eq!(peek, Some(&mut "b"));
1210 assert_eq!(cur._index(), Some(2));
1211 assert_eq!(cur.current(), Some(&mut "a"));
1212 }
1213
1214 #[test]
1215 fn split_after() {
1216 use crate::sequences::doubly_linked_list::LinkedList;
1217
1218 // Creates a new doubly-linked list
1219 // and pushes some elements to it
1220 let mut list = LinkedList::new();
1221 list.push_head("a");
1222 list.push_head("b");
1223 list.push_head("c");
1224 list.push_head("d");
1225 list.push_head("e"); // Postcondition: [e, d, c, b, a]
1226
1227 let mut cur = list.cursor_mut();
1228 cur.move_next(); // 0
1229 cur.move_next(); // 1
1230 cur.move_next(); // 2
1231
1232 // Split the list!
1233 let mut a = cur.split_after();
1234
1235 // The new list's head is now b
1236 let tail = a.pop_head().unwrap();
1237 assert_eq!(tail, "b");
1238
1239 // The original list's tail is now c
1240 let tail = list.pop_tail().unwrap();
1241 assert_eq!(tail, "c");
1242 }
1243
1244 #[test]
1245 fn split_before() {
1246 use crate::sequences::doubly_linked_list::LinkedList;
1247
1248 // Creates a new doubly-linked list
1249 // and pushes some elements to it
1250 let mut list = LinkedList::new();
1251 list.push_head("a");
1252 list.push_head("b");
1253 list.push_head("c");
1254 list.push_head("d");
1255 list.push_head("e"); // Postcondition: [e, d, c, b, a]
1256
1257 let mut cur = list.cursor_mut();
1258 cur.move_next(); // 0
1259 cur.move_next(); // 1
1260 cur.move_next(); // 2
1261
1262 // Split the list!
1263 let mut new = cur.split_before();
1264
1265 // The new list's head is now b
1266 let tail = new.pop_tail().unwrap();
1267 assert_eq!(tail, "d");
1268
1269 // The original list's tail is now c
1270 let tail = list.pop_head().unwrap();
1271 assert_eq!(tail, "c");
1272 }
1273
1274 #[test]
1275 fn splice_before() {
1276 use crate::sequences::doubly_linked_list::LinkedList;
1277
1278 // Creates a new doubly-linked list
1279 // and pushes some elements to it
1280 let mut list = LinkedList::<&str>::new();
1281 list.push_tail("a");
1282 list.push_tail("b");
1283 list.push_tail("c"); // Postcondition: [a, b, c]
1284
1285 let mut cur = list.cursor_mut();
1286 cur.move_next(); // a
1287 cur.move_next(); // b
1288 cur.move_next(); // c
1289
1290 let mut new_list = LinkedList::<&str>::new();
1291 new_list.push_tail("1");
1292 new_list.push_tail("2"); // Postcondition: [1, 2]
1293
1294 // Splice the list!
1295 cur.splice_before(new_list); // Postcondition: [a, b, 1, 2, c]
1296
1297 let mut tail = list.pop_tail();
1298 assert_eq!(tail, Some("c"));
1299 tail = list.pop_tail();
1300 assert_eq!(tail, Some("2"));
1301 tail = list.pop_tail();
1302 assert_eq!(tail, Some("1"));
1303 tail = list.pop_tail();
1304 assert_eq!(tail, Some("b"));
1305 }
1306
1307 #[test]
1308 fn splice_after() {
1309 // Creates a new doubly-linked list
1310 // and pushes some elements to it
1311 let mut list = LinkedList::<&str>::new();
1312 list.push_head("a");
1313 list.push_head("b");
1314 list.push_head("c"); // Postcondition: [c, b, a]
1315
1316 let mut cur = list.cursor_mut();
1317 cur.move_next(); // c
1318 cur.move_next(); // b
1319
1320 let mut new_list = LinkedList::<&str>::new();
1321 new_list.push_head("1");
1322 new_list.push_head("2"); // Postcondition: [2, 1]
1323
1324 // Splice the list!
1325 cur.splice_after(new_list); // Postcondition: [c, b, 2, 1, a]
1326
1327 let mut tail = list.pop_tail();
1328 assert_eq!(tail, Some("a"));
1329 tail = list.pop_tail();
1330 assert_eq!(tail, Some("1"));
1331 tail = list.pop_tail();
1332 assert_eq!(tail, Some("2"));
1333 tail = list.pop_tail();
1334 assert_eq!(tail, Some("b"));
1335 }
1336
1337 #[test]
1338 fn remove_current() {
1339 use crate::sequences::doubly_linked_list::LinkedList;
1340
1341 // Creates a new doubly-linked list
1342 // and pushes some elements to it
1343 let mut list = LinkedList::<&str>::new();
1344 list.push_tail("a");
1345 list.push_tail("b");
1346 list.push_tail("c"); // Postcondition: [a, b, c]
1347 assert_eq!(list.len(), 3);
1348
1349 let mut cur = list.cursor_mut();
1350 cur.move_next(); // a
1351 assert_eq!(cur.index, Some(0));
1352 cur.move_next(); // b
1353 assert_eq!(cur.index, Some(1));
1354
1355 // Remove the node
1356 cur.remove_current(); // Postcondition: [a, c]
1357
1358 // Tests that the remove operation backs
1359 // the cursor up and decrements the list length
1360 assert_eq!(cur.index, Some(0));
1361 assert_eq!(list.len(), 2);
1362
1363 let mut head = list.pop_head();
1364 assert_eq!(head, Some("a"));
1365 head = list.pop_head();
1366 assert_eq!(head, Some("c"));
1367 head = list.pop_head();
1368 assert_eq!(head, None);
1369
1370 // New list test
1371 let mut list = LinkedList::<&str>::new();
1372 list.push_tail("P");
1373 list.push_tail("E");
1374 list.push_tail("T");
1375 list.push_tail("E");
1376 list.push_tail("R"); // Postcondition [P, E, T, E, R]
1377
1378 let mut cur = list.cursor_mut();
1379 cur.move_prev(); // 4
1380 // Removes tail
1381 let r = cur.remove_current().unwrap(); // Postcondition [P, E, T, E]
1382 assert_eq!(r, "R");
1383 cur.move_next(); // boo! 👻
1384 cur.move_next(); // 0
1385 // Removes head
1386 let p = cur.remove_current().unwrap(); // Postcondition [E, T, E]
1387 assert_eq!(p, "P");
1388 assert_eq!(list.peek_head(), Some(&"E"));
1389 assert_eq!(list.peek_tail(), Some(&"E"));
1390 }
1391
1392 #[test]
1393 fn insert_before() {
1394 use crate::sequences::doubly_linked_list::LinkedList;
1395
1396 // Creates a new doubly-linked list
1397 // and pushes some elements to it
1398 let mut list = LinkedList::<&str>::new();
1399 list.push_tail("a");
1400 list.push_tail("c"); // Postcondition: [a, c]
1401 assert_eq!(list.len(), 2);
1402
1403 let mut cur = list.cursor_mut();
1404 cur.move_next(); // a
1405 assert_eq!(cur.index, Some(0));
1406 cur.move_next(); // b
1407 assert_eq!(cur.index, Some(1));
1408
1409 // Insert a node
1410 cur.insert_before("b"); // Postcondition: [a, b, c]
1411
1412 // Tests that the insert operation increments
1413 // the cursor's index and list length
1414 assert_eq!(cur.index, Some(2));
1415 assert_eq!(list.len(), 3);
1416
1417 // Pointer tests
1418 // Checks that head -> a
1419 let head_ptr: *mut Node<&str> = list.head.unwrap();
1420 let head: &str = unsafe { (*head_ptr).data }; // Unsafe deref
1421 assert_eq!(head, "a");
1422
1423 // Checks that head.next -> b
1424 let next_ptr: *mut Node<&str> = unsafe { (*list.head.unwrap()).next.unwrap() };
1425 let next: &str = unsafe { (*next_ptr).data }; // Unsafe deref
1426 assert_eq!(next, "b");
1427
1428 // Checks that b.next -> c
1429 let next_ptr: *mut Node<&str> = unsafe { (*next_ptr).next.unwrap() };
1430 let next: &str = unsafe { (*next_ptr).data }; // Unsafe deref
1431 assert_eq!(next, "c");
1432
1433 // Checks that b.next -> tail
1434 let tail_ptr = list.tail.unwrap();
1435 let tail_data = unsafe { (*tail_ptr).data };
1436 assert_eq!(next, tail_data);
1437
1438 // Functional tests
1439 let mut head = list.pop_head();
1440 assert_eq!(head, Some("a"));
1441 head = list.pop_head();
1442 assert_eq!(head, Some("b"));
1443 head = list.pop_head();
1444 assert_eq!(head, Some("c"));
1445 }
1446
1447 #[test]
1448 fn insert_after() {
1449 use crate::sequences::doubly_linked_list::LinkedList;
1450
1451 // Creates a new doubly-linked list
1452 // and pushes some elements to it
1453 let mut list = LinkedList::<&str>::new();
1454 list.push_tail("a");
1455 list.push_tail("c"); // Postcondition: [a, c]
1456 assert_eq!(list.len(), 2);
1457
1458 let mut cur = list.cursor_mut();
1459 cur.move_next(); // a
1460 assert_eq!(cur.index, Some(0));
1461
1462 // Insert a node
1463 cur.insert_after("b"); // Postcondition: [a, b, c]
1464
1465 // Tests that the insert operation does NOT
1466 // increment the cursor's index, but does increment
1467 // the list length
1468 assert_eq!(cur.index, Some(0));
1469 assert_eq!(list.len(), 3);
1470
1471 // Pointer tests
1472 // Checks that head -> a
1473 let head_ptr: *mut Node<&str> = list.head.unwrap();
1474 let head: &str = unsafe { (*head_ptr).data }; // Unsafe deref
1475 assert_eq!(head, "a");
1476
1477 // Checks that head.next -> b
1478 let next_ptr: *mut Node<&str> = unsafe { (*list.head.unwrap()).next.unwrap() };
1479 let next: &str = unsafe { (*next_ptr).data }; // Unsafe deref
1480 assert_eq!(next, "b");
1481
1482 // Checks that b.next -> c
1483 let next_ptr: *mut Node<&str> = unsafe { (*next_ptr).next.unwrap() };
1484 let next: &str = unsafe { (*next_ptr).data }; // Unsafe deref
1485 assert_eq!(next, "c");
1486
1487 // Checks that b.next -> tail
1488 let tail_ptr = list.tail.unwrap();
1489 let tail_data = unsafe { (*tail_ptr).data };
1490 assert_eq!(next, tail_data);
1491
1492 // Functional tests
1493 let mut head = list.pop_head();
1494 assert_eq!(head, Some("a"));
1495 head = list.pop_head();
1496 assert_eq!(head, Some("b"));
1497 head = list.pop_head();
1498 assert_eq!(head, Some("c"));
1499 }
1500}
1501
1502pub fn example() {
1503 //use super::*;
1504
1505 // First
1506 let mut first = LinkedList::new();
1507 first.push_tail("a");
1508 first.push_tail("b");
1509 first.push_tail("c");
1510
1511 print!("First: [");
1512 for (i, e) in first.iter().enumerate() {
1513 print!("{e}");
1514 if i == first.len() - 1 {
1515 print!("]");
1516 } else {
1517 print!(", ");
1518 }
1519 }
1520 println!();
1521
1522 // Second
1523 let mut second = LinkedList::new();
1524 second.push_tail("1");
1525 second.push_tail("2");
1526 second.push_tail("3");
1527 second.push_tail("4");
1528
1529 print!("Second: [");
1530 for (i, e) in second.iter().enumerate() {
1531 print!("{e}");
1532 if i == second.len() - 1 {
1533 println!("]");
1534 } else {
1535 print!(", ");
1536 }
1537 }
1538
1539 // Spliced
1540 let mut cur = second.cursor_mut();
1541 cur.move_next(); // 0
1542 cur.move_next(); // 1
1543 cur.splice_after(first);
1544 // Postcondition: [1, 2, a, b, c, 3, 4]
1545
1546 print!("Spliced: [");
1547 for (i, e) in second.iter().enumerate() {
1548 print!("{e}");
1549 if i == second.len() - 1 {
1550 println!("]");
1551 } else {
1552 print!(", ");
1553 }
1554 }
1555
1556 // Range split
1557 let mut cur = second.cursor_mut();
1558 cur.move_next(); // 0
1559 cur.move_next(); // 1
1560 let mut new_front = cur.split_after(); // splits after "2"
1561 // Postcondition: [1, 2] [a, b, c, 3, 4]
1562 let mut new_cur = new_front.cursor_mut();
1563 new_cur.move_next(); // 0
1564 new_cur.move_next(); // 1
1565 new_cur.move_next(); // 2
1566 let new_back = new_cur.split_after(); // splits again after "c"
1567 // Postcondition: [1, 2] [a, b, c] [3, 4]
1568 cur.splice_after(new_back); // reassembles the numbers
1569 // Postcondition: [1, 2, 3, 4] [a, b, c]
1570
1571 print!("Split numbers: [");
1572 for (i, e) in second.iter().enumerate() {
1573 print!("{e}");
1574 if i == second.len() - 1 {
1575 println!("]");
1576 } else {
1577 print!(", ");
1578 }
1579 }
1580 print!("Split letters: [");
1581 for (i, e) in new_front.iter().enumerate() {
1582 print!("{e}");
1583 if i == new_front.len() - 1 {
1584 println!("]");
1585 } else {
1586 print!(", ");
1587 }
1588 }
1589
1590 //Interleaved
1591 let mut first = LinkedList::new();
1592 first.push_tail("a");
1593 first.push_tail("b");
1594 first.push_tail("c");
1595
1596 let mut second = LinkedList::new();
1597 second.push_tail("1");
1598 second.push_tail("2");
1599 second.push_tail("3");
1600 second.push_tail("4");
1601 second.push_tail("5");
1602
1603 let max = std::cmp::max(first.len(), second.len());
1604
1605 let mut first_iter = first.iter();
1606 let mut second_iter = second.iter();
1607 print!("Interleaved: [");
1608 for (i, _) in (0..max).enumerate() {
1609 // If the first list has a value, print it
1610 if let Some(s) = second_iter.next() {
1611 print!("{s}");
1612 if i < max - 1 {
1613 print!(", ");
1614 }
1615 }
1616 // If the second list has a value, print it
1617 if let Some(f) = first_iter.next() {
1618 print!("{f}");
1619 if i < max - 1 {
1620 print!(", ");
1621 }
1622 }
1623 }
1624 println!("]");
1625}