struct List
{
  List *next, *prev;
  int x;
};

Head=1 2 3 4 5 [6] 7 8 9 10 11=Tail
// O(n)
// O(1)
List *pos[N];
List *p = pos[6]
p->next->prev = p->prev;
p->prev->next = p->next;
delete p;