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 <rajn...@gmail.com> 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.