3 ms·

I recently learned about deques in Python (other languages may have it too) which is like a linked list but it keeps pointers for the first and last elements. T

I recently learned about deques in Python (other languages may have it too) which is like a linked list but it keeps pointers for the first and last elements. This allows you to insert/read/remove elements from the beginning or end of the list in constant time. I’ve never used it, but I could imagine it being useful in certain situations. https://docs.python.org/3/library/collections.html https://docs.python.org/3/library/collections.html

sgtnoodle 4y ago
A deque may be implemented as a linked list, but it's actually more common to be implemented on top of arrays. Python in particular uses arrays under the hood for almost everything because modern computer hardware is so blazingly fast manipulating them.
- foolswisdom 4y ago
  Arrays aren't efficient when you want to add/remove to the head. Deque in python exists so there is a data structure with constant time pop/push to the head. And it is in fact implemented as a doubly linked list, with various optimizations: https://github.com/python/cpython/blob/v3.8.1/Modules/_collectionsmodule.c#L33-L78 https://github.com/python/cpython/blob/v3.8.1/Modules/_colle....
  - sgtnoodle 4y ago
    Neat, it's always best to look at the source. To be clear, a deque can be implemented on top of an array and still have constant time operations on the head.
    - sicp-enjoyer 4y ago
      If it's not constant time on both ends, it's not a deque. You can already insert items at any index in an array with linear cost.
      - sgtnoodle 4y ago
        I invite you to think about the problem for a while, and try to think of a way to implement a performant deque on top of a resize-able array. I promise you it's possible.
        eru 4y ago
        I don't think the comment you replied to disagreed with that.
  - moonchild 4y ago
    It is not commonly done, but there is no reason why you can't have an array with amortised constant-time insertion at both the head and the tail.
    - sgtnoodle 4y ago
      I think it's more common than not to implement deques on top of arrays. There's a meaningful performance difference at the hardware level due to the spatial locality in memory. Linked lists in general cause the CPU to jump all over the place in memory, causing pressure on the cache and whatnot. I believe the standard C++ deque implementation consists of a vector of vectors. The purpose of the two layers is at least two-fold. It guarantees that elements stored within the deque remain at a stable memory location at all times, even during a reallocation. Also, the memory getting shifted around during a reallocation consists of relatively tiny vector metadata rather than the application data. To speculate, I suspect the reason it's a linked list in python is due to the age of the module. It was likely written relatively early on in python's development, and the linked list implementation was simple and elegant. Now enough stuff uses it that it would be painful to change. Dicts are hashmaps in python rather than binary trees for similar performance reasons. You can't even find any binary tree based containers in python's standard library. You can find containers with the same performance characteristics and semantics of binary trees, but under the hood they're implemented on top of arrays because it better maps to hardware.

sgtnoodle 4y ago

A deque may be implemented as a linked list, but it's actually more common to be implemented on top of arrays. Python in particular uses arrays under the hood for almost everything because modern computer hardware is so blazingly fast manipulating them.

foolswisdom 4y ago
Arrays aren't efficient when you want to add/remove to the head. Deque in python exists so there is a data structure with constant time pop/push to the head. And it is in fact implemented as a doubly linked list, with various optimizations: https://github.com/python/cpython/blob/v3.8.1/Modules/_collectionsmodule.c#L33-L78 https://github.com/python/cpython/blob/v3.8.1/Modules/_colle....
- sgtnoodle 4y ago
  Neat, it's always best to look at the source. To be clear, a deque can be implemented on top of an array and still have constant time operations on the head.
  - sicp-enjoyer 4y ago
    If it's not constant time on both ends, it's not a deque. You can already insert items at any index in an array with linear cost.
    - sgtnoodle 4y ago
      I invite you to think about the problem for a while, and try to think of a way to implement a performant deque on top of a resize-able array. I promise you it's possible.
      - eru 4y ago
        I don't think the comment you replied to disagreed with that.
- moonchild 4y ago
  It is not commonly done, but there is no reason why you can't have an array with amortised constant-time insertion at both the head and the tail.
  - sgtnoodle 4y ago
    I think it's more common than not to implement deques on top of arrays. There's a meaningful performance difference at the hardware level due to the spatial locality in memory. Linked lists in general cause the CPU to jump all over the place in memory, causing pressure on the cache and whatnot. I believe the standard C++ deque implementation consists of a vector of vectors. The purpose of the two layers is at least two-fold. It guarantees that elements stored within the deque remain at a stable memory location at all times, even during a reallocation. Also, the memory getting shifted around during a reallocation consists of relatively tiny vector metadata rather than the application data. To speculate, I suspect the reason it's a linked list in python is due to the age of the module. It was likely written relatively early on in python's development, and the linked list implementation was simple and elegant. Now enough stuff uses it that it would be painful to change. Dicts are hashmaps in python rather than binary trees for similar performance reasons. You can't even find any binary tree based containers in python's standard library. You can find containers with the same performance characteristics and semantics of binary trees, but under the hood they're implemented on top of arrays because it better maps to hardware.