Concatenating two linked lists?

I was hoping to get some help on how to concatenate two linked lists in my doubly-linked list class. Specifically, how to properly call, from the driver file, a concatenate function located in the implementation file, including the correct way to pass the lists to the function. I already have a working doubly-linked list that includes operations such as insert, remove, etc. I decided not to include the entire code here because of the size. Also, I am hoping I have provided enough info to get help.

So far, I have in the implementation file:

Code:

template <class T>
void dlist<T>::concatenate(dlist<T> &list1, dlist<T> &list2) {
     if( list1.Tail == NULL )
       list1.Head = list2.Head;

     else
       list1.Tail->next = list2.Head;

     if( list2.Head != NULL )
       list1.Tail = list2.Tail;
}

Head and Tail are privately defined in the header file.


In the header file:

Code:

void concatenate(dlist<T> &list1, dlist<T> &list2);

And in the driver file where I am testing concatenate with two lists of integers:

Code:

dlist<int> list1, list2;

Since concatenate is a member function, I am fuzzy on how to call it, then dispay the newly appended list in the driver file.


Is a call like this suppose to work?

Code:

list2.concatenate(list1, list2);

I attempt to display the appended list, but it prints a loop of garbage. Any help would be greatly appreciated.

>>void concatenate(dlist<T> &list1, dlist<T> &list2);

That would be the parameter list syntax I'd use if I wanted to make concatenate a friend function of the dlist class. This is the form I'd use for a member function:

void concatenate(dlist<T> & dlist2);

where I intended to concatenate dlist2 onto the back of dlist1 and the call would be:

dlist1.concatenate(dlist2);

The concatenation process could be done several ways depending on your needs. Unfortunately, the quick and easy way is likely to lead you into problems. That is, if you assign dlist2.Head to dlist1.Tail.next and you assign dlist1.Tail to dlist2.Head.prior (this assumes prior is the pointer to the previous node in a doubly linked list) you have successfully concatenated dlist2 onto dlist1. However, dlist2 still exists as a stand alone entity and the memory that is in dlist2 is also in dlist1. Therefore, if you now delete the memory in dlist2 you have also deleted the same memory in dlist1 and created a problem. If you change data in any node in dlist2 you will also change the data in the corresponding node in dlist1, which may or may not have been your intentions, and is therefore at least a potential problem. So, the other approach is to copy the data from dlist2 into dlist1, but not the memory. This amounts to adding new nodes to the end of dlist1 one at a time, and copying the data from each successive node in dlist2 into dlist1, declaring new memory for each node as needed. Now you can change data in dlist2, delete the memory in dlist2, whatever, and it won't affect dlist1 at all. The former approach is called shallow copy and the latter deep copy, if you haven't already come across those terms.