Does cloning the head of linked list clones the entire list?

help
1

In the below code, I clone the head of an already existing linked list.
I change the value of the next node using the cloned head. Why is the original list unchanged.
I assume since next here is a pointer, changing next should affect current clone as well as original. Both the cloned head and original head should be pointing to the same next no ??

#[derive(Debug, Clone)]
pub struct List {
    pub head: Option<Box<ListNode>>
}

#[derive(Debug, Clone)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>
}

fn main() {
    let mut list = List::new();
    list.push(5);
    list.push(4);
    list.push(3);
    list.push(2);
    list.push(1);
    list.push(0);

    let mut clist = list.clone();
    // modified first node
    clist.head.as_mut().unwrap().val = 111; 
    // modified second node
    clist.head.as_mut().unwrap().next.as_mut().unwrap().val = 123;     

    println!("{:?}", list);

}

Actual output

List { head: Some(ListNode { val: 0, next: Some(ListNode { val: 1, next: Some(ListNode { val: 2, next: Some(ListNode { val: 3, next: Some(ListNode { val: 4, next: Some(ListNode { val: 5, next: None }) }) }) }) }) }) }

Expected output

List { head: Some(ListNode { val: 0, next: Some(ListNode { val: 123, next: Some(ListNode { val: 2, next: Some(ListNode { val: 3, next: Some(ListNode { val: 4, next: Some(ListNode { val: 5, next: None }) }) }) }) }) }) }

2

You're explicitly calling list.clone(). Not list.head.clone(). Why do you expect it not to clone the whole list?

3

Does calling list.head.clone() clones only the head node or everything from head till the end?

My guess is it clones everything till the end since doing this didn't change the original list.

    ...
    ...
    let mut chead = list.head.clone();
    chead.as_mut().unwrap().val = 123;
    chead.as_mut().unwrap().next.as_mut().unwrap().val = 321;

    println!("{:?}\n", list);
5

Well, ListNode contains next as Box<Option<ListNode>>, therefore to clone node you have to clone node.next. And cloning the Box clones its contents, so you have to clone the ListNode stored in next, if any. Therefore, in this case the whole list will be cloned, too.

1 Like
6

That's the nature of Box. It's owning pointer and there can not be any other owner.

If you would use Rc instead of Box then only head would be cloned. Because Rc is designed for that. With Rc you can have two owning pointers to the same node.

1 Like
7

Ohh I didn't no that. That would be a really expensive operation if the original list is very long.

I was of the opinion that cloning a node only clones its current contents retaining the next node value which is basically an address.

8

It's just an address but it's unique owning pointer. That's the semantic of Box. It's analogue of std::unique_ptr in C++.

Arc is analogue of std::shared_ptr which means it can do what you expect. And Rc is single-thread shared_ptr (C++ doesn't have anything like that because it's too dangerous in C++) thus it can do, too.

But it's forbidden for two Box'es to share the content which means clone have no choice. If it's implemented at all (and it's implemented) then it has to clone content.

1 Like
9

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.