Imagine keeping baseball cards in order by team and name. Finding a card becomes less of a hunt, but each new card must be put in the right place. A sorted list follows the same rule: its elements stay in a defined order as the collection changes. section 3.2 section 6.13
For a linked list, insertion is the operation that must change. Scan until you find where the new element belongs, then insert it there. If the list is ordered from smallest to largest, its smallest element is always at the head. section 6.13 section 10.5
Sorting a linked list does not give it the search advantage of a sorted array. An array can access its middle element directly, letting binary search discard half the remaining candidates. Reaching the middle of a linked list requires traversing earlier elements, so searching it generally cannot beat linear search. section 6.13 section 4.15
A priority queue
Keep a singly linked list ordered from highest priority at the head to lowest at the tail. To insert, scan for the new element’s place. The highest-priority element is then at the front, where it can be retrieved or removed quickly. A sorted array can also provide fast access to the top element, but its highest-priority element belongs at the end so removal does not shift every other entry. section 10.5
Table 10.1 An initial comparison of various implementations of a priority queue (view table figure)
| insert() |
top() |
Dynamic size |
|
|---|---|---|---|
| Sorted static array |
O(n) |
O(1) |
No |
| Unsorted static array |
O(1) |
O(n) |
No |
| Sorted linked list |
O(n) |
O(1) |
Yes |
| Unsorted linked list |
O(1) |
O(n) |
Yes |
Compare the costs of inserting and accessing the top element in sorted and unsorted static arrays and linked lists. The table also shows which choices have dynamic size. section 10.7
Choose the order to suit the operation you need most. Keeping a linked list sorted costs O(n) insertion, but puts an end-of-order element at the head for O(1) access. If fast search is the goal instead, a sorted array offers binary search—at the price of more work to maintain its order. section 10.7 section 3.8
