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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
