Use C++ for DSA, don't use python ! A lot of people say this when starting out DSA, and one big reason for this was always that python "abstracts" away a lot of the work for you.
That is what python is good for, and I also believe the advice would hold good for someone very new to coding and the theories of "analysis of algorithms", writing everything yourself will simply lead to a better understanding of why something works the way it works and you will have a chance to correct your misunderstanings, if any.
Anyways, just a few days back I had the curiosity to look at python's implementation of "Deque" because I could not find anything better to do (even though exams were nearing). Here's a link to it (within the official repo) .
Some takeaways, (might not be too awesome but were for me, looking at such a huge c code after a long time):
Block-Based Storage: The deque is implemented as a series of fixed-size blocks (arrays of pointers). Each block stores a segment of the deque's items. This block-based approach is more memory-efficient than a monolithic array for a large number of elements, especially when elements are frequently added or removed from both ends. see author's note
Doubly Linked List of Blocks: These blocks are linked together in a doubly linked list. This structure allows for constant-time insertions and deletions from both ends of the deque by adding or removing blocks as necessary.
Indexing: While the deque supports indexing, it is not as efficient as with lists. Indexing into a deque involves traversing the linked list of blocks until the appropriate block is found and then indexing into that block. This operation is O(n) in the worst case but is mitigated by the fixed block size, which keeps the number of blocks traversed relatively low for your average deque. see this
What I found most interesting was the implementation of remove (removing element at some index in your deque in constant time). See attached image, the remove function is somewhat of a wrapper to del_item. Anyways, what it does is rotate the array (akin to circular shift), till the element is at the end, pop that element and then rotate in reverse. I would very likely not think of the solution this way, if i was to implement it. Quite the work of art presented in the edge case handling as well in the rotate method itself.
Theres a lot to read, and a lot lot more to understand if you take the time.
