A call for community

code review
1

Hi all! The short of it is that I've been spending nights and weekends teaching myself how to code by working through a couple introductory DSA books in Java (and C). The plan is to implement some version of the ADTs as I progress, translating elements to Rust as I go. I'm really just starting, despite months of effort gaining (vague) familiarity with each of the languages involved.

I've managed to write what appears to be a quasi-functional doubly-linked list. In submitting this for review I'm hoping to gain feedback on correctness, stylistic (idiomatic) approaches, and real-world reasoning behind your feedback. This series is mostly intended to be an academic exercise.

Thank you!

1 Like
2

A few points, without having read all of the code in detail:

  • in the singly linked list code, it seems to me the special case handling of "inserting at the head" need not be a special case, and both can be handled uniformly quite easily
  • I don't see any Drop implementation, and the compiler-generated handling of a Box-based linked list will easily result in stack overflows for long lists. Consider adding a test for that, and see of you can fix it, if you'd like to support longer lists.
  • for the doubly linked list code, I see you have some example/test cases, which can be a good way to check for any oversights of tricky pointer semantics by running these through miri. So make sure to do this, if you haven't already.
  • I don't see any Drop implementation, so your code likely leaks memory (also something miri would catch)
  • the doubly linked list code presents raw pointers as public fields. This means that users can change these pointers if they like; which they could do without using unsafe. Your APIs, such as insert or iter are also not unsafe and dereference those pointers. So the overall API is not sound.
  • the doubly linked list uses Option<*mut Node>. Be aware that in Rust, raw pointers *mut Node are[1] already nullable, so in particular this option cannot benefit from any niche optimization. You could consider using null pointers instead of Option::None or using Option<NonNull<Node>>.

  1. perhaps unfortunately so ↩ī¸Ž

3 Likes
3

This is exactly the kind of direction I was looking for. Thank you!

4

Not a bad way to start - but also not the typical choice in rust.

In case you didn't stumble on it already:

5

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.