Вставить узел в связанный список в постоянное время?

Просто запишите это, если вы застряли с алгоритмом:

// First we have a pointer to a node containing element (elm) 
// with possible a next element.
// Graphically drawn as:
// p -> [elm] -> ???

tmp = new Node();
// A new node is created. Variable tmp points to the new node which 
// currently has no value.
// p   -> [elm] -> ???
// tmp -> [?]

tmp.element = p.element;

// The new node now has the same element as the original.
// p   -> [elm] -> ???
// tmp -> [elm]

tmp.next = p.next;

// The new node now has the same next node as the original.
// p   -> [elm] -> ???
// tmp -> [elm] -> ???

p.element = y;

// The original node now contains the element y.
// p   -> [y] -> ???
// tmp -> [elm] -> ???

p.next = tmp;

// The new node is now the next node from the following.
// p   -> [y] -> [elm] -> ???
// tmp -> [elm] -> ???

У вас есть необходимый эффект, но он может быть более эффективным, и я уверен, что теперь вы можете выяснить это сами.

Понятнее написать что-то вроде:

tmp = new Node();
tmp.element = y;
tmp.next = p;
p = tmp;

Что, конечно, не работает, если p неизменяемый. Но ваш алгоритм не работает, если p == NULL.

Но я хотел сказать, что если у вас есть проблемы с алгоритмом, просто запишите эффекты. Особенно с деревьями и связанными списками, вы должны быть уверены, что все указатели указывают в правильном направлении, иначе вы получите большой беспорядок.

Намекать: вставка в связанный список постоянна только тогда, когда позиция п = 0 или заголовок списка. В противном случае сложность наихудшего случая равна На). Это не означает, что вы не можете создать достаточно эффективный алгоритм, но он всегда будет иметь линейную сложность по меньшей мере.

Чего вы не делаете, так это связывания элемента, который был до p до вставки y в y. Итак, пока y вставляется перед p, никто сейчас не указывает на y (по крайней мере, не в фрагменте кода, который вы показали).

Вы можете вставить в постоянное время, только если знаете позиции элементов, между которыми вам нужно вставить y. Если вам нужно искать эту позицию, вы никогда не сможете вставить постоянное время в один список ссылок.

Как насчет использования кода, который уже есть? LinkedHashMap, LinkedList, LinkedHashSet. Вы также можете проверить код и извлечь из него уроки.

create a node ptr
ptr->info = item //item is the element to be inserted...
ptr->next = NULL
if (start == NULL) //insertion at the end...
    start = ptr
else
    temp = ptr
    while (temp->next != NULL)
        temp = temp->next
    end while 
end if
if (start == NULL) //insertion at the beginning...
    start = ptr
else
    temp = start
    ptr->info = item
    ptr->next = start
    start = ptr
end if
temp = start //insertion at specified location...
for (i = 1; i < pos-1; i++)
    if (start == NULL)
        start = ptr
    else
        t = temp
        temp = temp->next
    end if
end for
t->next = ptr->next
t->next = ptr

Причина, по которой узел заголовка и хвоста задается в вопросе, заключается в обновлении ссылки заголовка и хвоста, если создаваемый вами замещающий узел становится заголовком или хвостом. Другими словами, данный предыдущий узел является либо заголовком, либо хвостом.

В отдельном LinkedList только добавление узла в начало списка или создание списка только с одним узлом потребует O (1). ИЛИ, поскольку они предоставили TailNode, также для вставки узла в конец списка потребуется O (1).

каждая другая операция вставки займет O (n).