Deque extended to cover doubly linked list

Ideas
#1

I recently needed a doubly-linked list structure so implemented one in an array of (value, previous_ptr, next_ptr) tuples. It worked.

A little later and I re-solved my problem with a queue so used collections.deque. That worked too, and then read and was reminded that deque internals are based on a doubly-linked list it is just access is only given at each end.

That got me thinking. If new deque.start() and deque.end() returned DequePointer objects and that if ptr is of that type; ptr.next() and ptr.last() could return appropriate new DequePointer objects or None at the ends of the list.

ptr.value() could return the data at that location. There might also be a convenience function of ptr.items() returning a (ptr.value(), ptr.last(), ptr.next()) tuple.

Of course the normal identities would hold:

my_deque.start().value() == my_deque[0] if len(my_deque) > 0
my_deque.start().next().value() == my_deque[1] if len(my_deque) > 1
…
my_deque.end().value() == my_deque[-1] if len(my_deque) > 0
my_deque.end().last().value() == my_deque[-2] if len(my_deque) > 1
…

It might be better to have a separate class with the new functionality, but faster than Python execution based on the C-code for deque.

Useful to others? Too much bloat? these and other comments please.

#2

Hi Paddy,

How did you implement the pointers in Python and why did you need to put
the nodes in a list?

Can you explain a little more about your use-case? What problem are you
trying to solve that a plain old list doesn’t help and you need a linked
list?

Paddy: “That got me thinking. If new deque.start() and deque.end() returned
DequePointer objects”

What’s a DequePointer object?

Paddy: "Of course the normal identities would hold:
my_deque.start().value() == my_deque[0] if len(my_deque) > 0
my_deque.start().next().value() == my_deque[1] if len(my_deque) > 1
"

What’s the purpose here of having next() and last() (previous?) methods
on the nodes if you are going to put the nodes in a deque? To traverse
the linked list, you can just iterate over the deque.

Normally low-level languages use linked lists to make insertions in the
middle very fast, but if you use a deque, I understand that insertions
at the end is fast but insertions in the middle are slow. Without trying
it, I would expect that inserting into the middle of a list would be
faster. Let’s try it:

[steve ~]$ python3.9 -m timeit -s "a = list(range(100000))" 
"a.insert(50000, None)"
10000 loops, best of 5: 31.3 usec per loop

[steve ~]$ python3.9 -m timeit -s "from collections import deque" 
-s "a = deque(range(100000))" "a.insert(50000, None)"
10000 loops, best of 5: 37.3 usec per loop

Ah, not as big a difference as I imagined. But a list is still faster.

#3

Hi Stephen. Thanks for your interest.
On my blog post: Go deh!: The "Balls in a row" challenge function discard_LL is one of an initial three that solve the same problem and is fastest by eliminating repeated deletions of a list in the other two.
I follow it up with the fastest version here: https://paddy3118.blogspot.com/2021/01/balls-in-row-someone-on-reddit.html that uses a stack via deque… .
discard_LL used the next and last pointers to traverse the doubly linked list datastructure and to delete nodes. (I also realise I probably need more methods to safely modify a linked list structure)

#4

for collections of >300 items I had thought that del my_deque[30] would have similar poor timing as del my_list[30]… There is also the timings of the deletion of ranges: del my_deque[100:200] vs del my_list[100:200].

If a deque is modelled on a doubly linked list internally, with a list-like layer on top, then I would like to get at the underlying linked list structure with pointers, next, prev, insertions and deletions at pointers, … array access of a linked list means traversing from the beginning wheras linked list algoriths depend on fast “pointer” accesses
to adjacent nodes. (Sorry Steven, I don’t mean to speak down to you in any way - its been a long day :slight_smile:

#5

A deque allows efficient access at its two ends. I don’t understand why it should provide efficient removal of elements in the middle.
For your use case, you probably should use some variant of linked list – but that doesn’t mean thad deque should become a linked list. Use a different tool; don’t wish your existing tool was different.
You’ll need to find (or write) an implemenation of linked list first – but that would be true even if you wanted to deque to use it.

Unless, of course, some variant of linked list is better than deque in all its existing use cases. But that seems unlikely.

#6

Hi Petr, I can see how it may look like that, but I was only using it as a common base. I really liked that deque has a C-code implementation, but a doubly linked list has

  • The ability to store pointers to items of the list and traverse the list from them, (without having to first traverse from one of the ends).
  • An ability to quickly del nodes between two such pointers without having to traverse the list.
  • An ability to make the list circular.

I went further and developed an all Python Doubly Linked List implementation that would have worked for me - and needed the ability to do a lot of deletions in the middle of the datastructure, so the deque would not be ideal. I failed to find many uses for it out in the wild though when I searched, so held off adding to this idea post. I had a need, but my need wasn’t very often, and I failed to find (many), other needs for a doubly linked list.

They are different, as stated.

Thanks Petr :slight_smile:

#7

Raymond Hettinger has previously rejected proposals to allow insertion and deletion in the interior of a deque. He has gone over the C code multiple times to optimize it for what it now does. I believe that this has included tuning the size of the blocks of multiple entries to processor cache line sizes (rather than to disk block sizes).

1 Like