It's been a while since I coded in C and I'm confused as to how you made a double linked list that can read in O(1) time. Wikipedia has a page in it but even that says it takes O(n) time, does anyone have an example or tutorial on how this is implemented?
"All of these lists were doubly-linked to make it possible to add and remove elements from the list in constant time — O(1) — without the necessity to traverse the list looking for the element to remove — O(N)."
It seems the implication is that one is parsing over the list already. When parsing over the list, if you do a comparison that indicates the node should be removed (i.e. if the unit's health is below 0), you do not have to traverse back through the list again from the beginning to get the relevant pointer from the node before the current element in the list, since you already have the pointer to the previous node in the current node. Likewise for insertion.
But I don't think, strictly speaking, it's possible to have a linked list that actually has a lookup time of O(n) .
