Linked Lists

4 7 16 20 37 38

#

43

18

X

P

Figure 1-4: A Linked List

In Figure 1-4 we have the same values stored in a linked list. Assuming pointers X and P, as

shown in the figure, value 18 may be inserted as follows:

X->Next = P->Next;

P->Next = X;

Insertion and deletion operations are very efficient using linked lists. You may be wondering how pointer P was set in the first place. Well, we had to do a sequential search to find the insertion point X. Although we improved our performance for insertion/deletion, it was done at the expense of search time.