data-structures - 如何在恒定时间复杂度内在排序链表中插入项目？

Question

我在排序链表中遇到问题。我无法在恒定时间内插入项目。如果可能的话，我该如何解决？

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

不可能在恒定时间复杂度内在排序链表中插入项目。但是您可以以 O(log n) 时间复杂度插入项目。

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