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