CODEWITHSUNDEEP
algorithmdata-structureslinked-listtime-complexity
Jon Sillick
Jon Sillick

Reputation: 21

Time complexity to insert a node at the end of circular linked list?

Time complexity to insert a node at the end of circular singly linked list containing N elements ? Suppose I have pointer to the first node.

I think that it is O(N) as I have to parse the LL to the node before the new node to modify its next field.

Have I got it right ?

Upvotes: 1

Views: 7930

Answers (1)

Will Epperson
Will Epperson

Reputation: 51

Adding to the end of a circular singly linked list can be done in O(1) time.

  1. Create a new node and insert it after your head node.
  2. Copy your data from head into this new node.
  3. Add your new data into the old head node.
  4. Re-assign head.

As these are all constant time operations, this procedure is O(1).

Upvotes: 2

Related Questions