kodecocodes / swift-algorithm-club

Algorithms and data structures in Swift, with explanations!
MIT License
28.85k stars 5k forks source link

LinkedList`s removeAll method and default deinit may cause stack overflow #996

Open NickMeepo opened 2 years ago

NickMeepo commented 2 years ago

When triggering removeAll or deinit of very long LinkedList ( like 1...10000000 integers storage),you will get stack overflow. The reason is nodes` recursive releasing.

image

From the image above you will see recursive node deinit pushing into the stack accumulatively and this will cause crash with size increasing.

I suggest to fix this issue by rewriting removeAll, not simply 'self.head = nil', but using a while-loop to releasing each node, and calling removeAll in LinkedList deinit.