Sams Teach Yourself C in 21 Days

Pointers: Beyond the Basics 421

15

Adding an Element to the Middle of the List

When you’re working with a linked list, most of the time you will be adding elements

somewhere in the middle of the list. Exactly where the new element is placed depends on

how you’re keeping the list—for example, if it is sorted on one or more data elements.

This process, then, requires that you first locate the position in the list where the new ele-

ment will go, and then add it. Here are the steps to follow:

1. In the list, locate the existing element that the new element will be placed after.
   Let’s call this the marker element.


2. Create an instance of your structure, allocating memory space using malloc().


3. Set the next pointer of the marker element to point to the new element (whose
   address is returned by malloc()).


4. Set the next pointer of the new element to point to the element that the marker ele-
   ment used to point to.
   Here’s how the code might look:
   person marker;
   / Code here to set marker to point to the desired list location. */
   ...
   new = (LINK)malloc(sizeof(PERSON));
   new->next = marker->next;
   marker->next = new;
   Figure 15.12 illustrates this process.

FIGURE15.11

Adding a new element

to the end of a linked

list.

Before addition

data

next pointer

data

next pointer

data

next pointer

new data

NULL

head

data

next pointer

data

next pointer

data

NULL

new data

NULL

head

After addition

25 448201x-CH15 8/13/02 11:13 AM Page 421