The superscript "(d)" stands for "difficult". Exercises similar to those marked with "(d)" might appear in candidacy exams, but not in the standard exams of CSE 428.
L1 := cons(1,L) ; L2 := cons(2,L)Note that if two lists have a common sublist, it is always the final part in both of them.
On the other hand, this is the only case of side-effect. If we modify the definition of "tail" by eliminating the instruction "dispose", then the implementation of the "simple lists" becomes "pure", i.e. no side-effects would be possible with the operations of the ADT.
L^.next := LWe could also have different forms of side-effects. For instance, if we create L1 and L2 like above, with the commands:
L1 := cons(1,L) ; L2 := cons(2,L)and then we perform the command
L1^.next^.info := L1^.next^.info + 1this would modify also the content of the field "info" of the second element of L2.