CODEWITHSUNDEEP
data-structures
Abdullah Babu Kalam
Abdullah Babu Kalam

Reputation: 519

How to insert a item in sorted linked list within constant time complexity?

I have a problem in sorted linked list .I can't insert an item in constant time. If it possible than how can i solve it?

And this function time complexity is 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++;
}

Upvotes: 5

Views: 254

Answers (4)

user2138149
user2138149

Reputation: 17170

The answers are all correct, however there is some nuance to this.

You can insert into a list in constant time, provided you already have a hold of the node where you want to perform the insert.

See also this question: Why do we say linked list inserts are constant time?

I came across this question because I was similarly confused after reading in Scott Meyers Effective STL that inserting into a list is a constant time operation. (This is a C++ text, but the principles apply to other languages such as Java.)

It is, at least the inserting part is constant time, but for an insert to be useful you usually have to search for the node where you want to perform the insert. (Usually just before or after that node.)

Finding, or searching might be a linear O(N) operation if your find algorithm simply searches the list from the begining to the end looking for the node of interest. Hence one may think it is an O(N) operation. Other algorithms may give better average performance than O(N).

The other answers are not wrong per-se, it just depends what you consider to be part of the "inserting" operation. Strictly speaking it is contant time - but usually that isn't very helpful, since a number of inserts is usually combined with at least one find operation, or something of that nature.

Upvotes: 0

user4949763
user4949763

Reputation:

It is not possible to inset a item in sorted linked list with O(1) time complexity. You can only insert an item in unsorted linked list with time complexity O(1). You can know more about time complixity from this link http://bigocheatsheet.com/

Upvotes: 2

Richard Ayoade
Richard Ayoade

Reputation: 29

Actually it's not possible in sorted linked list but you can insert an item in unsorted linked list with constant time that is Big-O(1).

and also see this ...
https://www.youtube.com/watch?v=tta6BIiIIFI

Upvotes: 0

Yeahia Md Arif
Yeahia Md Arif

Reputation: 7946

It is not possible to inset a item in sorted linked list within constant time complexity. But you can insert item in O(log n) time complexity.

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

Upvotes: 2

Related Questions