小编Abd*_*lam的帖子

我在排序链表中有问题.我无法在常量时间插入项目.如果有可能我怎么解决呢？

而这个函数的时间复杂度是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; …