</>EmbeddedInterview

Implement a doubly linked list with insert and delete.

Easy"Coding: Linked Lists, Stacks & Queues"
#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.