### Chapter 12 Exercise 2

**
2. Based on the sample data in Figure 12.10, write the logic for the code to insert a new element in a linked list.
**

This exercise requires additional programming background, but the logic is straightforward. The level of detail depends on the background abilities of the students.

Base logic:

Store the new data item and get its address. (easy)

Search the existing list to find where the item belongs. (slightly tricky)

Get the “next” link pointer and store it in newItem.Next (easy)

Store the new item address in the priorItem.Next (easy)

The main code is a separate routine to search for the location (assume ascending sort order to simplify, but this can be generalized):

Function SearchKey(startItem, newItem) returns DataItem
DataItem current = startItem
DataItem prior = null
While (prior.KeyValue < newItem.KeyValue) And (current != null)
prior = current
current = current.Next
End While
Return prior;
End Function
DataItem newItem = store it…
DataItem prior = SearchKey(startItem, newItem)
(3, 4)
If (prior = null) // replace the start since nothing comes before new value
newItem.Next = startItem
startItem = newItem
Else
newItem.Next = prior.Next // also works for adding at end: Next = null
prior.Next = newItem
End If