Insert node at beginning of circular linked list

Circular linked list, last node next pointer are not NULL. That are contain the reference of first node of linked list. That is difference of single and circular linked list. Basically we can choose two variant to make a circular single linked list. First only one head pointer. And another is two pointers head and tail.

First Approach : That is very simple and similar to single linked list. And inserting a new node to beginning of this linked list this are need O(1) time. But the properties of circular linked list, always last node next pointer hold the address of first node of linked list.

So finding last node and provide next pointer reference to new head this process are tack O(n) time. So overall time complexity of first approach is O(n).

For example, suppose we are inserted the following (8,7,6,5,4,3,2,1) node in a sequence.

Circular linked list

Here given code implementation process.

Second approach: Using of two pointers head and tail to hold the references of first and last linked list node. this process are no need to find last node so time complexity of this approach is O(1).

Insert Circular linked list Node


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved