|
|
|
|
|
|
|
Copying a Dynamic Linked List |
|
|
|
|
|
|
|
|
When working with linked lists, we sometimes need to create a duplicate copy (a clone) of a linked list. For example, in Chapter 18, we wrote a copyconstructor for the OrdList class. This copy-constructor creates a new class object to be a clone of another class object, including its dynamic linked list. |
|
|
|
|
|
|
|
|
Suppose that we want to write a value-returning function that receives the external pointer to a linked list (head), makes a clone of the linked list, and returns the external pointer to the new list as the function value. A typical call to the function would be the following: |
|
|
|
|
|
|
|
|
NodePtr head;
NodePtr newListHead;
.
.
.
newListHead = PtrToClone(head); |
|
|
|
|
|
|
|
|
Using iteration to copy a linked list is rather complicated. The following algorithm is essentially the same as the one used in the OrdList copyconstructor. |
|
|
|
|
|
|
|
|
PtrToClone (In: head) // Iterative algorithm Out: Function value |
|
|
|
|
|
|
|
|
IF head is NULL
Return NULL
// Copy first node
Set fromPtr = head
Set cloneHead = new NodeType
Set cloneHead->component = fromPtr->component
// Copy remaining nodes
Set toPtr = cloneHead
Set fromPtr = fromPtr->link
WHILE fromPtr is not NULL
Set toPtr->link = new NodeType
Set toPtr= toPtr->link
Set toPtr->component = fromPtr->component
Set fromPtr = fromPtr->link
Set toPtr->link = NULL
Return cloneHead |
|
|
|
|
|
|
|
|
|
A recursive solution to this problem is far simpler, but it requires us to think recursively. To clone the first node of the original list, we can allocate a |
|
|
|
|
|