Menu Introduction Bibliography

Basics Arrays Linked Lists Timing Estimates Summary

Sorting Insertion Sort Shell Sort Quick Sort Comparison External Sorts

Dictionaries Hash Tables Binary Trees Red-Black Trees Skip Lists Comparison

Linked Lists

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 has been at the expense of search time.

Figure 1-4: A Linked List