doubly linked list implementation in this sectionwe present complete implementation of positionallist class using doubly linked list that satisfies the following important proposition proposition each method of the positional list adt runs in worst-case ( time when implemented with doubly linked list we rely on the doublylinkedbase class from section for our low-level representationthe primary responsibility of our new class is to provide public interface in accordance with the positional list adt we begin our class definition in code fragment with the definition of the public position classnested within our positionallist class position instances will be used to represent the locations of elements within the list our various positionallist methods may end up creating redundant position instances that reference the same underlying node (for examplewhen first and last are the samefor that reasonour position class defines the eq and ne special methods so that test such as = evaluates to true when two positions refer to the same node validating positions each time method of the positionallist class accepts position as parameterwe want to verify that the position is validand if soto determine the underlying node associated with the position this functionality is implemented by nonpublic method named validate internallya position maintains reference to the associated node of the linked listand also reference to the list instance that contains the specified node with the container referencewe can robustly detect when caller sends position instance that does not belong to the indicated list we are also able to detect position instance that belongs to the listbut that refers to node that is no longer part of that list recall that the delete node of the base class sets the previous and next references of deleted node to nonewe can recognize that condition to detect deprecated node access and update methods the access methods of the positionallist class are given in code fragment and the update methods are given in code fragment all of these methods trivially adapt the underlying doubly linked list implementation to support the public interface of the positional list adt those methods rely on the validate utility to "unwrapany position that is sent they also rely on make position utility to "wrapnodes as position instances to return to the usermaking sure never to return position referencing sentinel for conveniencewe have overridden the inherited insert between utility method so that ours returns position associated with the newly created node (whereas the inherited version returns the node itself