Why linklist not working with unique pointer

Question

Hi

Refer code below:
I know I have yet not completed addtotail function, but I am not yet using it also.

However, I still don't see linklist not printed properly. Could anyone help me understand issue here?
https://sololearn.com/compiler-playground/c92Jh6s6PTHl/?ref=app

Answer 1

you need to rewrite the member function "linklist::print" to look like:

void print()
{
// Iteration doesn't own resource, so no unique_ptr here.
auto curr = m_head.get();

while (curr)
{
std::cout << curr->getValue() << " ";
curr = curr->getNext().get();
}
std::cout << std::endl;
}

Answer 2

maybe std::shared_ptr solve the traversing problem but in general using smart pointers is risky with linked lists. the problem comes up when a long list is being destructed, it is being destructed recursively. node destructor calls smart pointer's destructor, which calls node destructor. most likely the stack will grow in O(n). since a list can be longer than the maximum possible stack, the code may run out of stack space and crash.

I would advise against using smart pointers when implementing low-level data structures.

Answer 3

due to the length of the list, unless the compiler just happens to apply TCO ( tail call optimization ) to node's destructor and std::shared_ptr's destructor.

also the shared owndership and circular dependencies for this case are harder to solve than manual memory management.

Answer 4

in the custom list, each node is stored as a std::shared_ptr<Node>, which incurs additional memory overhead due to reference counting and control blocks associated with each shared pointer. this overhead increases the memory consumption of the program, making it more likely to encounter stack overflow errors when the number of elements exceeds a certain threshold. when you increase the number of elements to 1e5, the program may run out of stack memory, leading to a stack overflow error or program crash.

Answer 5

std::shared_ptr means the ownership of an object is unclear. this is not the case for linked lists: every node owns the next. using unique_ptr is easier and more efficient. ( in general i'd say that smart pointers are for casual use, i.e. not for implementing low-level data-structures )

Answer 6

MO ELomari thanks a lot.

I tried below sample code.

Stl list works for 1e8 elements in for loop present at the end of loop. It fails to print final hi if for loop is used for 1e9 elements.

However, custom implemented list works for only 1e4 elements and fails for 1e5 elements.

Got your point now. Thanks a lot again.
https://sololearn.com/compiler-playground/cXKodn8dOs79/?ref=app

Answer 7

Thanks MO ELomari . It must work with this approach. However, I am curious and want to achieve only through smart pointer.

Get() will give us raw pointer , which I would like to avoid. Is there any other way to achieve the print functionality?

Answer 8

You can't use std::unique_ptr for this case ( std::unique_ptrs can't be assigned ).

Answer 9

Is it safe to say that shared_ptr is needed for singly link list when we want to even print the node values like below?

https://sololearn.com/compiler-playground/c7W1FVmvJEL6/?ref=app

Answer 10

I had your point of ownership of nodes in mind. That was the reason I had started with unique pointer.

But when one node is there, both head and tail pointers need to point to same object at same time. This made me think about shared pointer. Still I was not sure and thought that I will have only one pointer head as it is just a single linklist and to add to the end, will traverse the list.

But when I faced challenge to print also a single linkedlist, I feel now that for this case, shared pointer is the best one. Correct or am I missing something?

Answer 11

Thanks MO ELomari

I got your point to prefer raw pointer and it sounds good.

However, I am struggling to understand why stack overflow would happen for a longer list ? Is it due to shared pointer's circular dependency or is it due to length of the list which cause the overflow ?

Answer 12

Sounds great