[Updated] how to write the iterator for this linkedlist

[nesteiner]

guys, I am not an English speaker, so forgive my language first
I have make a list with these code

use std::rc::Rc;
use std::cell::RefCell;

struct ListNode<T> {
    value: T,
    pub prev: Option<Rc<RefCell<ListNode<T>>>>,
    pub next: Option<Rc<RefCell<ListNode<T>>>>
}

pub struct List<T> {
    head: Option<Rc<RefCell<ListNode<T>>>>,
    tail: Option<Rc<RefCell<ListNode<T>>>>
}

pub struct ListIter<T> {
    node: Option<Rc<RefCell<ListNode<T>>>>
}

impl <T> ListNode<T> {
    pub fn new(value: T) -> Self {
	Self {
	    value,
	    prev: None,
	    next: None
	}
    }
}

impl <T> List<T> {
    pub fn new() -> Self {
	Self {
	    head: None,
	    tail: None
	}
    }

    pub fn iter(&self) -> ListIter<T> {
	ListIter {
	    node: Option::from(self.head.as_ref().map(|node| {
		Rc::clone(node)
	    }))
	}
    }

    pub fn push(&mut self, value: T) {
	let node = Rc::new(RefCell::new(ListNode::new(value)));
	if self.head.is_none() {
	    self.head = Option::from(Rc::clone(&node));
	    self.tail = Option::from(Rc::clone(&node));
	} else {
	    // node.prev = tail
	    // tail.next = node
	    // tail = tail.next
	    self.tail = self.tail.take().map(|tailnode: Rc<RefCell<ListNode<T>>>| {
		// let mut tailnode = tailnode.borrow_mut();
		// tailnode.next = Option::from(Rc::clone(&node));
		// Rc::clone(&node)

		let mut mut_tailnode = tailnode.borrow_mut();
		mut_tailnode.next = Option::from(Rc::clone(&node));

		let mut mut_node = node.borrow_mut();
		mut_node.prev = Option::from(Rc::clone(&tailnode));
		Rc::clone(&node)
	    });
	}
    }
}

now the most different part is to impl Iterator trait for ListIter, can you help me out ??

---

update

the ListIter is

pub struct ListIter<T> {
    node: Option<Rc<RefCell<ListNode<T>>>>
}

and I found a way to impl Iterator trait, but something wrong with my code

impl <T> Iterator for ListIter<T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
	let result = self.node.map(|node: Rc<RefCell<ListNode<T>>>| {
	    &node.borrow().value
	});

	self.node.map(|node: Rc<RefCell<ListNode<T>>>| {
	    self.node = node.borrow().next
	});

	return result;
    }
}

as you say, I need a lifetime parameters, but that doesn't fit the code, how should I fix it ??

[Yandros]

Hey, I'd personally go for something like the following:

• pub
  fn iter (self: &'_ List<T>)
    -> impl /* 'T + */ Iterator<Item = Rc<RefCell<ListNode<T>>>>
  {
      ::core::iter::successors(
          self.head.as_ref().map(Rc::clone),
          |rc_node| rc_node.borrow().next.as_ref().map(Rc::clone),
      )
  }
  

  • Playground

It will be hard to do anything fancier (e.g., yielding Ts rather than Rc<RefCell<ListNode<T>>>s), since the external iteration API of Iterator does not allow for that level of control, unless you started going through some very convoluted hoops (would require owned Rc<Ref<…>> self-referential guards being accumulated in the iterator's state ).

One thing you could do, however, is, using that fn iter() I've showcased, to feature a .for_each() kind of API for internal iteration :

• pub
  fn for_each (self: &'_ List<T>, mut f: impl FnMut(&T))
  {
      self.iter().for_each(|rc_node| f(&rc_node.borrow().value))
  }
  

Finally, if the list are not too long, you could even feature a .for_each() kind of API which does not clone the Rcs, at the cost of accumulating a stack of cell::Ref guards (from recursive .borrow()s:

• pub
  fn for_each_no_clone (self: &'_ List<T>, f: impl FnMut(&T))
  {
      if let Some(head) = &self.head {
          for_each(&*head.borrow(), f);
      }
      // where
      fn for_each<T> (it: &'_ ListNode<T>, mut f: impl FnMut(&T))
      {
          f(&it.value);
          if let Some(next) = &it.next {
              for_each(&*next.borrow(), f)
          }
      }
  }
  

Playground

[alice]

You can do this:

impl<T> Iterator for ListIter<T> {
    type Item = Rc<RefCell<ListNode<T>>>;
    
    fn next(&mut self) -> Option<Self::Item> {
        let next = self.node.as_ref().and_then(|node| node.borrow().next.clone());
        
        // This is equivalent to this, but without the clone:
        // let ret = self.node.clone();
        // self.node = next;
        // ret
        std::mem::replace(&mut self.node, next)
    }
}

Returning references to the actual values is not possible because they're behind a RefCell.

[nesteiner]

sorry, why the return value is not the type of Option<Self::Item> ?

[alice]

It is, I just made a mistake.

[nesteiner]

so can you provide correct code

[alice]

I modified it. I think it should work now.