Сессионная школа (Вектор-37)

Односвязный вариант

struct Node {
    Node *next;
    int value;

    Node(int v):
            value(v),
            next(0) {
    }
};

Node* insert_after(Node* i,value) {
    Node* t = new Node(value);
    t->next = i->next;
    i->next = t;
    return t;
}

// Можно использовать только для вставки в начало списка
Node* insert_before(Node* i, value) {
    Node* t = new Node(value);
    t->next = i;
    return t;
}

Двусвязный вариант

struct Node {
    Node *next;
    Node *prev;
    int value;

    Node(int v):
            value(v),
            next(0),
            prev(0) {
    }
};

Node* insert_after(Node* i,value) {
    Node* t = new Node(value);
    t->next = i->next;
    if (t->next)
        t->next->prev = t;
    i->next = t;
    t->prev = i;
    return t;
}

// Можно использовать для вставки в любое место списка, благодаря двусвязности
Node* insert_before(Node* i, value) {
    Node* t = new Node(value);
    t->prev = i->prev;
    if (t->prev)
        t->prev->next = t;
    i->prev = t;
    t->next = i;
    return t;
}