Ordered singly linked list

[kpishere]

I have a linked list here with tests in it. It is a mutable singly linked list. I've modified it slightly and added a rank to the node. I want this linked list to be ordered putting the lower ranked item first. So, on the push() operation I simply want it to crawl the list and insert the node in the right spot.

This ALMOST works but when it attempts to push the third item, the iterator exits after the 2nd item.

playground

Am I assigning the 2nd item improperly somehow?

 // Push will insert according to rank - rank is ordered lowest first
    pub fn push(&mut self, elem: T, rank: i32) {
        if Option::is_none(&self.head) {
            let new_node = Box::new(Node {
                rank,
                elem, 
                next: None,
            });
            self.head = Some(new_node); // First node written here
        } else {
            for ranked_node in self.head.iter_mut() {
                if let Some(ref next) = ranked_node.next {
                    if next.rank >= rank {
                        // If the next is larger, add here
                        let new_node = Box::new(Node {
                            rank,
                            elem, 
                            // New node points to next
                            next: Option::take(&mut ranked_node.next),
                        });
                        // set current node to our new noded
                        ranked_node.next = Some(new_node);
                        break;   
                    }
                    // Else iterate to next ** after first loop, exists and never loops to the second one
                } else {
                    // There is no higher next node, add at end
                    let new_node = Box::new(Node {
                        rank,
                        elem, 
                        next: None,
                    });
                    ranked_node.next = Some(new_node); // second node written here
                    break;
                }
            }
        }
    }

[kpreid]

In List::push(), you have

for ranked_node in self.head.iter_mut() {

This calls Option::iter_mut() which iterates over at most one item. That is probably not what you meant. Perhaps you meant to call your own List::iter_mut(), but if you do that, you won't have access to the Nodes, so you'll need to do something else.

[quinedot]

You also have a logic error; if head is Some, you never add before head. If you add a new minimum element, you're going to add it after head.

Here's one take. The only testing I did on top of what you have is to add a minimum element in basics.

I assume this is all for practice, but be aware linked lists are a poor fit for Rust.

[abdavis]

I don't know the details of what you're trying to do, but You may want to use a btree map instead. You can iterate over elements in order, but inserting and deleting is faster than a linked list.

The downside is you can only have one value for each key, but there are ways you could work around that.

Or if you are trying to build a priority queue and you only insert each element once and need to quickly remove the highest priority element, you can use a binary heap

[kpishere]

Thanks for the help! Yes, I was getting my iterators confused, between a List one and an Option one.

As for WHY I'd want this, it is for low-level no_std and no operating system environment. That is what Rust is supposed to be good for right? The rank will be an event time of when to execute the a callback function .. a Reactor pattern.

Key parts are now:

impl<T> Node<T> {
    fn look_forward_node_rank(&mut self) -> Option<i32> {
        self.next.as_ref().map(|node| {
            node.rank
        })
    }
}

impl<T> List<T> {
    pub fn push(&mut self, elem: T, rank: i32) {
        if self.head.is_none() {
            // A new list, push first node
            let new_node = Box::new(Node {
                rank,
                elem,
                next: self.head.take(),
            });

            self.head = Some(new_node);
        } else {
            let mut find_node = self.iter_mut();
            loop {
                let curr_node = find_node.ptr.as_deref_mut();
                match curr_node {
                    Some(node) => {     
                        match node.look_forward_node_rank() {
                            Some(next_rank) =>  {            
                                if next_rank > rank {
                                    let new_node = Box::new(Node {
                                        rank,
                                        elem,
                                        next:  Option::take(&mut node.next),
                                    });
                                    node.next = Some(new_node);
                                    break;  
                                }    
                            },
                            _ => {
                                // At the end of the list
                                let new_node = Box::new(Node {
                                    rank,
                                    elem,
                                    next: None,
                                });
                    
                                node.next = Some(new_node);
                                break;                    
                            }                            
                        }
                    },
                    _ => { panic!("iter_mut()") } // Should not get here
                }
                find_node.next(); // want side effect if incrementing ptr                
            }
        }
    }
}

Here is the final working code in its full with tests playground link