|
|
|
|
|
|
|
// Copy first node
fromPtr = otherList.head;
head = new NodeType;
head->component = fromPtr->component;
// Copy remaining nodes
toPtr = head;
fromPtr = fromPtr->link;
while (fromPtr != NULL)
{
// Invariant (prior to test):
// The list from *head through *toPtr is a copy of
// the list from *(otherList.head) through the node
// preceding *fromPtr
toPtr->link = new NodeType;
toPtr = toPtr->link;
toPtr->component = fromPtr->component;
fromPtr = fromPtr->link;
}
toPtr->link = NULL;
} |
|
|
|
|
|
|
|
|
Choice of Data Representation |
|
|
|
|
|
|
|
|
We have looked in detail at two ways of representing lists of components: one where the components are physically next to each other (a direct array representation, as in Figure 18-1), and one where the components are logically next to each other (a linked list). Furthermore, a linked list is an abstraction that can be implemented either by using an array of structs or by using dynamically allocated structs and pointers (a dynamic linked list). |
|
|
|
|
|
|
|
|
Let's compare the array representation with the dynamic linked list representation. (Throughout this discussion, we use array to mean a direct array representation, not an array of structs forming a linked list.) We look at common operations on lists and examine the advantages and disadvantages of each representation on each operation. |
|
|
|
|
|
|
|
|
1. Read the components into an initially empty list. |
|
|
|
|
|
|
|
|
2. Access all the components in the list in sequence. |
|
|
|
|
|
|
|
|
3. Insert or delete the first component in a list. |
|
|
|
|
|
|
|
|
4. Insert or delete the last component in a list. |
|
|
|
|
|