On 2016-07-17 08:19, Chris Angelico wrote:
> Why do you need a linked list? That's an implementation detail; why
> not simply use a regular list?
>
> Not trolling, genuinely asking. Is there something that you
> specifically need those exact structures for?
I know there have been times I want known performance
characteristics.
My main reason for wanting linked lists is usually for stacks/queues
with O(1) push/pop, and I understand that a deque handles most of
that fairly efficiently ("approximately the same O(1) performance in
either direction").
The bisect and heapq modules also help with some of my usual
use-cases for BSTs (presuming "BST" unpacks as "binary search tree"),
while nested arrays/dicts usually serve for most of the rest of my
other tree/trie needs.
So usually I'm less concerned with the actual algorithm name than I
am with the "I want to {push,pop,search,insert,delete} in O(f) time"
where O(f) is usually either O(1) or O(N log N), instead of the
alternatives which might use O(N), O(N**k), or worse, O(k**N).
For anything beyond those basic CS data-structures, there's usually
something conveniently in PyPI.
-tkc
--
https://mail.python.org/mailman/listinfo/python-list
