Come inserire un elemento in una lista concatenata ordinata con una complessità a tempo costante?

Question

Ho un problema in elenco collegato ordinato. Non riesco a inserire un oggetto in tempo costante. Se possibile, come posso risolverlo?

E questa volta funzione di complessità è Big-O (N)

template <class ItemType> 
void SortedType<ItemType>::InsertItem(ItemType item) 
{ 
    NodeType<ItemType>* newNode; 
    NodeType<ItemType>* predLoc; 
    NodeType<ItemType>* location; 
    bool moreToSearch; 

    location = listData; 
    predLoc = NULL; 
    moreToSearch = (location != NULL); 
    while (moreToSearch) 
    { 
    if (location->info < item) 
    { 
     predLoc = location; 
     location = location->next; 
     moreToSearch = (location != NULL); 
    } 
    else moreToSearch = false; 
    } 
    newNode = new NodeType<ItemType>; 
    newNode->info = item; 

    if (predLoc == NULL) 
    { 
    newNode->next = listData; 
    listData = newNode; 
    } 
    else 
    { 
    newNode->next = location; 
    predLoc->next = newNode; 
    } 
    length++; 
} 

Answer 1

Non è possibile inserto un elemento nella lista collegata ordinato entro complessità costante di tempo. Ma puoi inserire l'elemento in O (log n) complessità temporale.

how to apply binary search O(log n) on a sorted linked list?

Answer 2

In realtà non è possibile nella lista collegata ordinato, ma si può inserire un elemento in lista collegata non differenziati con il tempo costante che è Big-O (1).

e anche vedere questo ...
https://www.youtube.com/watch?v=tta6BIiIIFI

Answer 3

Non è possibile inserto un elemento nella lista collegata ordinato con O (1) tempo di complessità. È possibile inserire un elemento solo in un elenco collegato non ordinato con complessità temporale O (1). Puoi saperne di più sulla compresenza temporale da questo link http://bigocheatsheet.com/