Circular doubly linked list implementation in Cython

Question

This is a follow-up from my previous question. In summary, I am trying to implement a BVH module with Cython and need a way to keep track of the volumes during the construction of the hierarchy.

I was going to use a Doubly linked list for that purpose as it allows for efficiently inserting and popping items from either side, but a user pointed that many APIs use a circular version of the list to avoid problems.

I decided to implement such a list, also tried to make it more general so it can be useful for further projects.

cdef struct CDLinkedList:
 ListNode* head
 int length
cdef struct ListNode:
 ListNode** links #[0] = previous, [1] = next or vice versa, doesn't matter.
 void* data
cdef ListNode* list_node_create(void* data) nogil:
 cdef ListNode* n = <ListNode *> malloc(sizeof(ListNode))
 n.links = <ListNode **> malloc(sizeof(ListNode*) * 2)
 n.data = data
 return n
cdef void list_node_free(ListNode* node) nogil:
 free(node.links)
 free(node)
cdef CDLinkedList* list_create() nogil:
 cdef CDLinkedList* lst = <CDLinkedList *> malloc(sizeof(CDLinkedList))
 lst.head = list_node_create(NULL)
 lst.head.links[0] = lst.head
 lst.head.links[1] = lst.head
 lst.length = 0
 return lst
cdef void list_free(CDLinkedList* lst) nogil:
 while lst.length > 0:
 list_pop(lst, 0)
 list_node_free(lst.head)
 free(lst)
cdef void list_insert(CDLinkedList* lst, void* data, int link_side) nogil:
 cdef:
 int next = link_side
 int prev = 1 - link_side
 ListNode* next_node = lst.head.links[next]
 ListNode* new_node = list_node_create(data)
 next_node.links[prev] = new_node
 lst.head.links[next] = new_node
 new_node.links[prev] = lst.head
 new_node.links[next] = next_node
 lst.length += 1
cdef void* list_pop(CDLinkedList* lst, int link_side) nogil:
 if lst.length <= 0:
 return NULL
 cdef:
 int next = link_side
 int prev = 1 - link_side
 ListNode* next_node = lst.head.links[next]
 ListNode* next_next_node = next_node.links[next]
 void* data = next_node.data
 lst.head.links[next] = next_next_node
 next_next_node.links[prev] = lst.head
 list_node_free(next_node)
 lst.length -= 1
 return data

• dfhwze: What an interesting coincidence: I just answered this one (circular singly linked list in Java): codereview.stackexchange.com/questions/133210/…. I might have a look at your question later.
• greybeard: I miss imports. Why a ** for links instead of an array?