The Gateway to Computer Science Excellence
+1 vote
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 .
in Programming by | 1k views

1 Answer

+1 vote

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.


I am not getting that how come the head pointer in the circular linked list has a pointer to its tail node , when it is not a double linked list then how come we have the prev pointers to a node , we will have only the tail pointer pointing to head but head has no info regarding tail so then how come this is done in O(1) time ?
You can always maintain a special variable "last"  (just as you have start variable) which points to last element of list.
the right answer is suppose to be circular doubly linked list. since then it would have a pointer to the last node using the 'prev' of the first node.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,375 questions
60,583 answers
95,404 users