6
Orionss
7y

Last year, I made an application of A* maze-solving algorithm in class. I used a linked list and my friends used arrays. Their algorithms were way faster than mine (I remade it later :p).

OK I understand that accessing memory by address if way faster than accessing by iterations, but I also see that python lists or C# lists are really fast. How is it possible to make a list performance-proof like this? Do the python interpreter make a realloc each time you append or pop a value?

Comments
  • 0
    Not every push/pop. A specific size is allocated (initially e.g. 4) and whenever this size gets surpassed, the array gets allocated with 2*size.

    Analog shrinking could be triggered when the actual size < 4*allocated size.

    You can check the standard arraylist implementation in the corresponding language, most should be open source.
Add Comment