Add pop(idx) support to both single and double linked list implementations

[kata198]

Hey bud,

This patch adds .pop(idx) to both linked and double-linked list implementation.

This follows the same pattern as the standard python list, where an index can be provided (positive or negative) to the pop function to pop a specific element.

The index is optional, and if not provided defaults to popright (so backwards-compatible, and compatible with base list).

Please consider merging and re-releasing with the addition of this patch.

The primary advantage of a linked-list or double-linked-list versus an array is the ability to work on the middle without rebuilding the entire list. You already have support for inserts in the middle of the list. This adds that benefit with removal (via "pop") to these implementations, and thus allows them to out-perform the base python list for various scenarios.

Thanks, Tim

[kata198]

In my test, this does perform well wiith smaller-sized lists (as in, faster than the python base list)

But still python base list is faster for larger sizes (like around 1 million elements), because the walk time takes so long.

I'm currently looking into implementing a compound linked list. That is a blocked series of linked lists in an array, so for example if you had 500 elements and block size 100, you'd have 5 linked lists in an array. If you requested element 220, you'd start at idx=2 and only have to walk 20 items instead of 220.

I haven't seen such before, I may submit it soon if it solves my needs (beating python list at random-access popping from large sizes)

[kata198]

After my updates today, it performs even better. On a 400 element list with 200 random-index pops, single-linked-list and python base list perform the same, double-linked-list is faster. Below that, the linked list impls are faster, above that python list gets faster (because walk time takes up so much of the time)

[ajakubek]

Hey,

Thanks for the pull request. The code looks good and a generalized pop method can indeed be useful. I'll merge your branch once the problem with last accessed item cache is resolved. Would you like to provide a patch for this issue?

Also, could you update the documentation of the pop method? It's in docs/index.rst, you can build it with make docs.

Thanks, Adam

[ajakubek]

Ok, to sum up the current state of this merge request. There are several things that I like. The pop, index and rindex functions are definitely useful and I'd be happy to merge them. I can also pull the minor fixes and the refactoring into generic LListObject. However, the part which replaces caching of recently accessed item with the middle one is problematic. It causes significant regression in performance for use cases which had been actually documented to be fast. I'm a bit wary to merge such change. I can cherry-pick the other commits into my repository and close this PR next weekend. Or you can resubmit the merge request without the removal of index caching, and then I'll just pull your branch.