A display routine for a circular list differs from that of a linear list because the end of an unsuccessful search is signaled by a return to the starting point instead of by a NIL pointer:
Additions to a circular list, cList, can take place most easily if the new node is to follow immediately after the node distinguished by the pointer cList, as shown in Figure C.1.
The insertion routine is straightforward:
When a single list identifier, cList, is used, and a node is to be added prior to it, then it is necessary to locate the node that points to cList, say Prior, and then apply InsertAfter(Prior,xNode), as shown in Figure C.2.
The location logic is a simple version of LT (section 3.3.2):
Deletion in the vicinity of cList can take several forms. In particular, the node cList
Some combinations of insertion and deletion operations define formal structures in common use. Of particular interest is the circular queue, discussed in Chapter 5 :
The form taken by DeleteNext is simply:
A deletion procedure such as DeleteBack is awkward unless the pointer Prior is available. Such a pointer can be made available by a change to a two-window system, as shown in Figure C.4.
With the window-pair system, circularity appears to be specious. Nevertheless, circular lists defined with a pair of pointers turn out to be useful when they are maintained in a single array. Routines designed to maintain the single array, specialized to the structure QUEUE, are treated in section 5.3.
Details of the other deletion procedures are left to the exercises.
Exercises immediate applications of the text material
EC.1 When insertion prior to cList is made to an empty list something must be done after the search logic and InsertAfter(cList,xNode) of section 3.7 to properly prepare for later insertions. What is it?
Problems not immediate, but requiring no major extensions of the text material
PC.1 Develop the procedure DeleteOn.
PC.2 Develop the procedure DeleteBack.
PC.3 Develop the procedure DeleteLast.
procedure RoundOut(cList) {O(n)if Empty(cList)
then {deal with this errorelse Display(cList) {PROCESS0p
cList 
.Link {PROCESS0while p
cList doDisplay(p) {PROCESS2p
p .Linkendwhile
endif
end {RoundOut
Figure C.1
procedure InsertAfter(cList,xNode) {O(1)if Empty(cList)
then xNode
.Link xNodecList
xNodeelse xNode
.Link cList .LinkcList
.Link xNodeendif
end {InsertAfter
Figure C.2
Prior
cListif NOT Empty(cList)
then p
cList .Linkwhile p
cList doPrior
pp
p .Linkendwhile
endif
.Link (if it exists) can be readily deleted. So can cList; in Figure C.3 the cList pointer value can move forward or backward relative to the link directions.
Figure C.3
A circular queue: InsertAfter(cList,xNode)
DeleteBack(cList)
procedure DeleteNext(cList) {O(1)if Empty(cList)
then {deal with this errorreturn
endif
if cList
.Link = cListthen cList
NILreturn
else Next
cList .LinkcList
.Link Next .Linkendif
end {DeleteNext
Figure C.4
Exercises
Problems