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

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 == NULL.

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

Answer 2

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

Answer 3

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

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

Answer 4

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

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

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

Answer 7

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

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