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

Question

Я работаю над заданием, которое подсказывает мне, что у меня есть односвязный список с заголовком и хвостовыми узлами. Он хочет, чтобы я вставил элемент y перед позицией p. Кто-нибудь может, пожалуйста, просмотреть мой код и сказать мне, если я на правильном пути? Если нет, можете ли вы дать мне какие-либо советы или указатели (не каламбур)?

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

Я думаю, что могу ошибаться, потому что я вообще не использую заголовочные и хвостовые узлы, даже если они специально упомянуты в описании проблемы. Я думал о создании цикла while для обхода списка, пока он не найдет p и не решит проблему таким образом, но это не будет постоянным временем, не так ли?

Answer 1

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

// 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.

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

Answer 2

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

Answer 3

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

Answer 4

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

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

Answer 5

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

Answer 6

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

Answer 7

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

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