|
Examine the definition of cat from the preceding page.
const List cat(const List A, const List B)
{
if(isEmpty(A))
{
return B;
}
else
{
return cons(head(A), cat(tail(A), B));
}
}
Imagine concatenating x = [2,3] with y = [4,5,6],
yielding result z = [2,3,4,5,6]. Here
are linked list diagrams that show x, y and z.
____ ____
x------>| | | |
| -------->| -----\
|----| |----|
| 2 | | 3 |
|____| |____|
____ ____ ____
y------>| | | | | |
| -------->| ------->| -----\
|----| |----| |----|
-->| 4 | | 5 | | 6 |
| |____| |____| |____|
|
|
------------------------
____ ____ |
z------>| | | | |
| -------->| -------
|----| |----|
| 2 | | 3 |
|____| |____|
Notice that three cells belong to both list y
and to list z. That is called
memory sharing.
Although memory sharing can save both time and memory, it can also lead to difficulties that you need to be aware of.
Since a cell can belong to more than one list, changing anything in the cell potentially changes more than one linked list. For example, if the cell holding 6 is changed to hold 7, then both y and z change in the above picture.
Since a cell can belong to more than one list, you cannot delete it just because you are no longer using it in a particular list. For example, if you are done with list y above, you cannot delete its cells because you might still need list z. That makes it much more difficult decide when to delete a cell.
For a language such as Java, which uses garbage collection, that is not a problem. For a language like C++ where the program is responsible for deleting cells, you typically use reference counts.
If you want to write cat to avoid memory sharing, it is just a matter of copying list B, as shown on the previous page. But the cost, in terms of time and memory, goes up.
Problem linkedlist1-5 asks you to define function prefix(L, n). Does that function make use of memory sharing? Answer
|