Doubly linked list in Cython I am implementing a BVH (Bounding volume hierarchy) in Cython and thought of using a doubly linked list to hold reference of the volumes that still need to be split and push new volumes at one end while popping others on the other side in a recursive manner.

But I am not sure if I got the code right, it gets confusing to me really fast.

Here AABB stands for Axis Aligned Bounding Box, the kind of bounding volume I want to use in my BVH.

    cdef struct AABB:
        double min_x, max_x
        double min_y, max_y
        double min_z, max_z
        AABB* next
        AABB* children
        int id

    cdef struct AABBListItem:
        AABB* box
        AABBListItem* next
        AABBListItem* prev

    cdef AABBList* aabb_list_create(AABB* start):
        cdef AABBList* lst = &lt;AABBList *&gt; malloc(sizeof(AABBList))
        cdef AABBListItem* item = &lt;AABBListItem *&gt; malloc(sizeof(AABBListItem))
        item.next = NULL
        item.prev = NULL
        item.box = start
        lst.first = item
        lst.last = item
        lst.length = 1
        return lst

    cdef void aabb_list_free(AABBList* lst):
        cdef AABBListItem* item = lst.first
        cdef AABBListItem* next
        while not item == NULL:
            next = item.next
            free(item)
            item = next
        free(lst)

    cdef void aabb_list_push_last(AABBList* lst, AABB* box):
        cdef AABBListItem* item = &lt;AABBListItem *&gt; malloc(sizeof(AABBListItem))
        item.box = box
        item.prev = lst.last
        item.next = NULL
        lst.last.next = item
        lst.last = item
        lst.length += 1

    cdef void aabb_list_push_first(AABBList* lst, AABB* box):
        cdef AABBListItem* item = &lt;AABBListItem *&gt; malloc(sizeof(AABBListItem))
        item.box = box
        item.next = lst.first
        item.prev = NULL
        lst.first.prev = item
        lst.first = item
        lst.length += 1

    cdef AABB* aabb_list_pop_first(AABBList* lst):
        cdef AABBListItem* item = lst.first
        cdef AABB* box = item.box
        lst.first = item.next
        lst.first.prev = NULL
        free(item)
        lst.length -= 1
        return box

    cdef AABB* aabb_list_pop_last(AABBList* lst):
        cdef AABBListItem* item = lst.last
        cdef AABB* box = item.box
        lst.last = item.prev
        lst.last.next = NULL
        free(item)
        lst.length -= 1
        return box

```
Empty Constraint

You do not allow to create an empty list.


cdef AABBList* aabb_list_create(AABB* start):



However, the pop methods don't check against the empty constraint. In fact, when popping the sole node, you end up with an error.

For instance,


 cdef AABB* aabb_list_pop_first(AABBList* lst):
        cdef AABBListItem* item = lst.first
        cdef AABB* box = item.box
        lst.first = item.next     // &lt;- if item.next is NULL
        lst.first.prev = NULL     // &lt;- lst.first will be NULL, and .prev is an error
        free(item)
        lst.length -= 1
        return box



Single Remaining Item after Pop

Furthermore, when after pop a single item remains, it should be set as both first and last on the list.