Linked Lists

If you’ve ever had to visit a hospital emergency room, you’ll know that waiting in a
queue is one of the defining features of the experience unless you were either very lucky
or very unlucky. If you were lucky, the queue will have been empty and you will not
have had to wait. Alternatively, if you were unlucky, your condition may have been
sufficiently perilous that you got to jump to the head of the queue.
In medical emergencies, a triage system will be in place to work out where each arriving
patient should go in the queue. A similar pattern crops up in other scenarios—frequent
fliers with gold cards may be allocated standby seats at the last minute even though
others have been waiting for hours; celebrities might be able to walk right into a res-
taurant for which the rest of us have to book a table weeks in advance.
The LinkList class is able to model these sorts of scenarios. At its simplest, you
could use it like a Queue—call AddLast to add an item to the back of the queue (as
Enqueue would), and RemoveFirst to take the item off the head of the queue (like
Dequeue would). But you can also add an item to the front of the queue with
AddFirst. Or you can add items anywhere you like in the queue with the AddBefore and
AddAfter methods. Example 9-13 uses this to place new patients into the queue.

Example 9-13. Triage in action

private LinkedList waitingPatients = new LinkedList();
...
LinkedListNode current = waitingPatients.First;
312 | Chapter 9: Collection Classeswhile (current != null)
{
if (current.Value.AtImminentRiskOfDeath)
{
current = current.Next;
}
else
{
break;
}
}
if (current == null)
{
waitingPatients.AddLast(newPatient);
}
else
{
waitingPatients.AddBefore(current, newPatient);
}

This code adds the new patient after all those patients in the queue whose lives appear
to be at immediate risk, but ahead of all other patients—the patient is presumably either
quite unwell or a generous hospital benefactor. (Real triage is a little more complex, of
course, but you still insert items into the list in the same way, no matter how you go
about choosing the insertion point.)
Note the use of LinkedListNode—this is how LinkedList presents the queue’s
contents. It allows us not only to see the item in the queue, but also to navigate back
and forth through the queue with the Next and Previous properties.