2,861 views
2 votes
2 votes
I am not getting that when head pointer has no information regarding the tail pointer then how is it that circular linked list will have a constant time for its concatenation with another circular linked list , wouldn't it take same time if we perform concatenation on a single or double linked list .

1 Answer

1 votes
1 votes

You can easily concatenate two lists in O(1) time using either a single linked list or a doubly linked list, provided that you have a pointer to the last node in at least one of the lists. (And, of course, pointers to the list heads.)

You can't do it with an array implementation, because you end up having to allocate more memory and copy the new resulting list to it. Even if the array already has memory allocated, you still have to copy all of the new items to it. So it's either O(m+n) or O(n) (where m and n are the lengths of the individual lists, respectively).

With a circularly linked list, you can easily concatenate them in O(1) time. It's just a matter of breaking a link in both lists, and then hooking them together. This assumes, of course, that the order of items isn't especially important.

ref:http://stackoverflow.com/questions/25938499/linked-list-concatenation-in-o1-time

Related questions

0 votes
0 votes
3 answers
1
radha gogia asked Jul 22, 2015
3,972 views
According to me when we perform the above operations we have to traverse the entire list so then why does it all take constant time ?
3 votes
3 votes
1 answer
3
hacker16 asked Nov 14, 2017
21,186 views
In circular singly linked list, insertion of node requires modification of how many pointers?1 pointers2 pointers3 pointers 4 pointers
0 votes
0 votes
1 answer
4