Page 59 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes
Figure 2.9: (a) Lists before Concatenation and (b) List after Concatenation

p NULL

q NULL

(a)
Temp

p

q
NULL

(b)

The function to achieve this is given below:
Concatenate (struct node *p, struct node *q)
{
struct node *temp;
temp = p;
if (p == NULL)// If first list is NULL then Concatenated
p = q; // List will be only Second List and will be
else //pointed by p;
{
temp = p;
while (temp -> link ! = NULL)
temp = temp -> link;
temp -> link = q;
}
}

2.13 Summary

The foremost advantage of linked lists in dynamic storage is fl exibility advantages
Overflow is no problem until the computer memory is actually exhausted. Especially when

the individual entries are quite large, it may be difficult to determine the overfl ow amount

of contiguous static storage that might be needed for the required arrays while keeping
enough free for other needs. With dynamic allocation, there is no need to attempt to make
such decisions in advance.
Changes, especially insertions and deletions, can be made in the middle of a changes linked
list more quickly than in the middle of a contiguous list. If the structures are large, then it is
much quicker to change the values of a few pointers than to copy the structures themselves
from one location to another disadvantages.

The first drawback of linked lists is that the links themselves take space that might otherwise
be needed for additional data. In most systems, a pointer requires the same amount of
storage (one word) as does an integer. Thus a list of integers will require double the space
in linked storage that it would require in contiguous storage.

54 LOVELY PROFESSIONAL UNIVERSITY