@Mayur: Hey for concatenation of 2 circular lists you don't need last
pointer or doubly linked lists. Actually I should've mentioned that there's
no last pointer and its a singly linked list. It can be done by rearranging
the pointers.
void concatenate(NODE *list1,NODE *list2)
{
NODE *p;
if(list2==NULL)
return;
if(list1==NULL)
{
list1=list2;
return;
}
p=list1->next;
list1->next=list->next;
list2->next=p;
list1=list2;
}
Start reading the list from where p points to. As you can read circular list
in any order, this can be done.
Freeing also can be done by rearranging in some way without traversal, I may
not able to figure out how?
On Fri, Jun 11, 2010 at 9:38 PM, Mayur <[email protected]> wrote:
> Concatenation of two lists without traversing even one of the lists
> completely requires a pointer to the last element of the first list (first,
> as in the one that is to be attached in front of the other list). This is
> only possible if either, there's a *last *pointer for the lists, or the
> list is a double-linked list (besides being a circular list) where each node
> stores pointers to both the previous and the next nodes.
>
> Concatenation in a doubly-linked circular list is a simple exchange of
> pointers as illustrated below
>
> list Concat(list1, list2)
> {
> last1 = list1.head.prev
> last2 = list2.head.prev
> last1.next = list2.head
> last2.next = list1.head
> list1.head.prev = last2
> list2.head.prev = last1
> return list1
> }
>
> Depending upon your implementation, there would have to be checks for NULL
> pointers. Also, one may use pointer swapping to achieve the effect in, for
> example, a C implementation.
>
>
> Freeing up a list on the other hand requires a full traversal, no matter
> what kind of list it is. That's because each node was allocated separately
> (that would be the whole point of having a dynamically created list).
>
> thanks,
> mayur
>
>
>
> On Fri, Jun 11, 2010 at 1:23 PM, Raj N <[email protected]> wrote:
>
>> Hi,
>> I came across this statement that using circular lists, concatenation
>> can be done without traversing either list. The same case with freeing
>> the entire list.
>> Can someone elaborate on this ?
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
