aalhour/C-Sharp-Algorithms

Removing 0 from SkipList<int> breaks enumeration

Mabar16 opened this issue · 1 comments

Describe the bug
Attempting to enumerate a SkipList<int> whose head node has been removed leads to the program running indefinitely. The head can be removed by calling Remove(0), the defualt value for int, whilst the list contains a negative int.

To Reproduce
Reproducing this bug can be done as follows:

  1. Instantiate a new SkipList<int>
    var list = new SkipList<int>();
  2. Add any negative integer to the list
    list.Add(-23);
  3. Attempt to remove 0 (the head node) from the list
    list.Remove(0);
  4. Perform (almost) any operation that enumerates the skip list
    list.Contains(2);

Expected behavior
list.Remove(0); should not modify the list unless 0 has been added explicitly.

Environment
OS: Windows 10 Home (Version 10.0.18362 Build 18362)
.NET Version: .NET Core v3.1.101
IDE: Microsoft Visual Studio Community 2019 - Version 16.4.5

Additional context

  • The bug can only be reproduced if the SkipList<int> contains at least one negative integer.

  • The bug will not occur if the value 0 has been added to (and not removed from) the SkipList<int>.

  • Step 4 in To Reproduce can be replaced by any function that iterates over the skip list: Contains, Find, Remove, for-each looping over the list, etc.

  • NB: Contains and Find will function as intended if you search for an int that exists in the list (list.Contains(-23); in the case of the example would still work).

Thanks for supporting the development of C# Algorithms with your first issue! We look forward to handling it.