Implement a doubly linked list with insert and delete.
#include <stdlib.h>
typedef struct dnode { int val; struct dnode *prev, *next; } dnode_t;
typedef struct { dnode_t *head, *tail; } dlist_t;
int dlist_push_back(dlist_t *l, int v)
{
dnode_t *n = malloc(sizeof *n);
if (!n) return -1;
n->val = v; n->next = NULL; n->prev = l->tail;
if (l->tail) l->tail->next = n; else l->head = n;
l->tail = n;
return 0;
}
void dlist_remove(dlist_t *l, dnode_t *n) /* O(1) given the node */
{
if (n->prev) n->prev->next = n->next; else l->head = n->next;
if (n->next) n->next->prev = n->prev; else l->tail = n->prev;
free(n);
}
Points: removal is O(1) when you have the node (no search for the predecessor), which is why OS kernels use doubly linked lists for run queues and timers; the cost is an extra pointer per node. Update head/tail in the edge cases.