listing removing node from linked list given the head referenceremove target from linked list prednode none curnode head while curnode is not none and curnode data !target prednode curnode curnode curnode next if curnode is not none if curnode is head head curnode next else prednode next curnode next if the target is elsewhere in the listwe simply adjust the link field of the node referenced by prednode to point to the node following the one referenced by curnode this step is performed in the else clause of the condition as shown in line of listing if the last node is being removedthe same code can be used because the next field of the node pointed to by prednode will be set to none since curnode will be null removing node from linked list requires (ntime since the node could be at the end of the listin which case complete traversal is required to locate the node the bag adt revisited to illustrate the use of the linked list structurewe implement new version of the bag adtwhich we originally defined in section the new implementation is shown in listing on the next page linked list implementation we begin our discussion of the linked list implementation of the bag adt with the constructor firstthe head field will store the head pointer of the linked list the reference is initialized to none to represent an empty bag the size field is used to keep track of the number of items stored in the bag that is needed by the len method technicallythis field is not needed but it does prevent us from having to traverse the list to count the number of nodes each time the length is needed notice we only define head pointer as data field in the object temporary references such as the curnode reference used to traverse the list are not defined as attributesbut instead as local variables within the individual methods as needed sample instance of the new bag class is illustrated in figure the contains(method is simple search of the linked list as described earlier in the the add(method simply implements the prepend operationthough we must also increment the item counter sizeas new items are added the baglistnode classused to represent the individual nodesis also defined