Issue to update links in double link list | Shared_ptr

Question

Hi

Tried to implement link list using shared pointer. I am trying to attach next and prev pointers, but there seems an issue. Could anyone please help me understand issue here?

https://www.sololearn.com/en/compiler-playground/c944JPowPy80
https://sololearn.com/compiler-playground/c944JPowPy80/?ref=app

Answer 1

the main problems are in the <mylist::addToList> function:

- the while loop condition is incorrect: you're checking "while (!b)" but <b> never changes inside the loop, which could lead to an infinite loop or incorrect traversal.

however, there's still a design consideration to note: you're using <std::weak_ptr> for both "next" and "prev" pointers ( it wouldn't work ), which means you don't have any shared ownership of the nodes except through the head pointer. this could potentially lead to nodes being deleted prematurely ( the reference count become zero, and the weak_ptr becomes nullptr ).
if you want a more robust doubly-linked list, you might want to use <std::shared_ptr> for at least the "next" pointer to maintain proper ownership of the nodes throughout the list.

this would make the list more stable and prevent premature deletion of nodes, while still avoiding circular reference problems by keeping the "prev" pointer as a <std::weak_ptr> :

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

in general using smart pointers is risky with low-level data structures. 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 2

Ketan Lalcheta
Interesting idea, but maybe just as an academic exercise.
I was trying to understand your code, so I did some searching.
It's not really practicable.
https://stackoverflow.com/questions/36673391/c-linked-list-using-smart-pointers

But yes, your code still would be a good bug hunting excercise. No solution from me right now, though.

Answer 3

MO ELomari
nice.
I tried to use your test to compare how a dumb pointer based Node Linked List behaves when deleted, compared to a how a smart pointer based Node Linked List destructor behaves.

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

Answer 4

ah, now I understand the issue! the problem is that we need to maintain shared ownership throughout the list for it to work properly. tn the current implementation with <std::shared_ptr> for "next", each node is owned by the previous node (plus head owning the first node), which prevents premature deletion.

if you want to be able to delete nodes in any order while maintaining proper ownership, we should use a different approach, by adding an <unordered_set> to store all nodes and maintain shared ownership and change back both "next" and "prev" to <weak_ptr> :

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

nodes can now be deleted in any order without causing premature deletion of other nodes. meaning when you delete node 3, node 5 won't be deleted until you explicitly delete it or the list is destroyed, because the ownership is maintained by the nodes set rather than through the linked list pointers.

Answer 5

the core problem is the recursive nature of the destruction, each recursive call adds a stack frame ( recursive destruction can be sneaky - it happens implicitly ).

let's see what happens with just 4 nodes: Node1 -> Node2 -> Node3 -> Node4 -> nullptr

now when Node1 is destroyed:

Stack Frame 1: ~Node1() starts
└── Stack Frame 2: ~Node2() starts (because of smart pointer)
└── Stack Frame 3: ~Node3() starts
└── Stack Frame 4: ~Node4() starts
└── Node4 destructor finishes
└── Node3 destructor finishes
└── Node2 destructor finishes
└── Node1 destructor finishes

now imagine instead of 4 nodes, you have 100,000 nodes:

when head is destroyed:
Stack Frame 1: ~Node1()
Stack Frame 2: ~Node2()
Stack Frame 3: ~Node3()
.....
Stack Frame 100000: ~Node100000()

Answer 6

convert to iterative destruction ( the Node has to implement a destructor to erase nodes in a loop, so that recursion won't be invoked ). the iterative approach uses heap memory ( heap can be much larger ) efficiently without stacking up call frames.

Answer 7

here is a visual example of stack frames :

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

Answer 8

Thanks MO ELomari

Answer 9

I got the idea why it is not working 😕

Head is the only one which is holding reference. Rest all are weak pointers. So , head is kept in memory and all other nodes are getting out of scope.

Answer 10

Just to make a point for this smart pointers. I also understand that it is not needed apart from learning purpose.

Here is what I have for single link list using unique_ptr. In case of double linklist, it is a bit difficult
https://sololearn.com/compiler-playground/c8zO2X1L6uv8/?ref=app

Answer 11

Thanks MO ELomari

In your working code example , head is pointing to node 3. Actually, 3->5->7

Head is 3 which can be deleted because it is not refereed any where . Before deleting 3, 5 cannot be deleted as it was refereed by 3 as next pointer.

This way, we delete 3,5,7 in order of head.

Where is stack occupied here in O(n)? Isn't it true to say that stack is used as O(n) if destructor order was reverse and first one to get released was the last farthest node from head?

Answer 12

Can you please elaborate because I don't understand your point.

Answer 13

Observation 1 :

Object print function is printing data as 3->5->7. This indicates that head is node having value 3.

Observation 2:
First destructor call displays "Node with data 3 is deleted". It means node with value 3 is the first to get released.

Conclusion:
By two observations, head node is deleted first by destructor. This ensures that there is no stack frames to traverse till the end of entire list. In other words, first node (stored in head) is deleted first.

So, what is the meaning of your statement "the stack will grow in O(n)"? I thought this statement should be true when last node is deleted first from entire list object. This entire traversal results into stack growth.

I tried to describe my query. In short, why you mentioned "the stack will grow in O(n)"? Let me know if you have any question on my confusion.

Answer 14

stack overflow would happen due to the length of the list ( because it will destruct the nodes recursively instead of in a loop ) unless the compiler just happens to apply TCO ( tail call optimization ) to node's destructor and smart pointer destructor.
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 , the program may run out of stack memory, leading to a stack overflow error or program crash.

a simple test driver could be

int main()
{
mylist<int> obj;
for (int i = 0; i < 1000000; ++i)
{
obj.addToList(i);
};

return 0;
}

and check if it supports large lists

Answer 15

I was still unable to write down my query.

I had no issue with head node (node with value 3) deleted first in your first implementation.

It makes sense to have one of the next or prev to be a shared_ptr to avoid premature deletion.

What I did not understand is your statement below:

"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"

Could you please explain me this stack space and crash issue you had mentioned in your first post?

Answer 16

when using smart pointers in a linkedlist, each node deletion triggers a chain reaction :

let's say you have: Node A --> Node B --> Node C --> Node D.

when deleting A, its destructor calls B's destructor, which calls C's, and so on,each call adds a new frame to the stack memory which creates recursive destruction.

why it's dangerous ? because stack memory is limited (usually a few MB). with a long list (say 100,000 nodes), you need 100,000 stack frames. this can easily exceed stack space and cause stack overflow.
while smart pointers are great for memory safety, they need to be used carefully in recursive data structures to avoid stack overflow issues.

Answer 17

Can I verify this stack frame by putting Some break points ?

I observe three destructor calls and that's needed as we have three nodes.

Answer 18

yes, absolutely! you can verify the stack frames using a debugger. this will help you visualize exactly how deep the recursion goes during destruction. be careful with very large lists though - if you're debugging the stack overflow issue, start with a smaller list (maybe 100 nodes) so you don't crash your debugger!!

Answer 19

I could not verify the recursion depth causing stack frames in the example code you shared

https://www.sololearn.com/en/compiler-playground/ckorttG5D4at/?ref=app

I used above code. I just added empty destructor for mylist class.

I had break point into mylist class destructor and node class destructor.

These are the break point hit:
- Once in mylist class destructor
- node class destructor thrice - once for each node we have

As I don't see more than needed destructor calls, I am unable to understand what it (list implemented using smart pointer) does wrong?

Answer 20

Thanks. Is there any way to get rid off this or it is unavoidable?