sal is performedotherwise normal forward traversal is used if the target is found during the iteration of the appropriate loopthe function is terminated and true is returned otherwisethe loop will terminate after exhausting all possible nodes or stopping early when it' determined the target cannot possibly be in the list in either casefalse is returned as the last operation of the function we can add quick test to determine if the target value cannot possibly be in the list this is done by comparing the target to the first and last nodes in the list if the target is smaller than the first item or larger than the lastwe know the search will ultimately fail since the target is not in the list this step can be omitted as the same results can be achieved by the search traversal followbut it can help to improve the search time on large lists the search operationwhich maintains and uses third external reference variablecan improve the search time for large number of sequential searches performed on large lists but in the worst caseit remains linear time operation since complete traversal may have to be performed adding nodes adding new nodes to sorted doubly linked list is done similar to that for the singly linked list the only difference is we do not need to keep track of the preceding node once the position for the new node is locatedwe can access its predecessor using the appropriate prev field consider figure which illustrates inserting new node into the middle of sorted doubly linked list the location of the new node is found by positioning single temporary external reference variable to point to the node containing the first value larger than the new value after this position is foundthe new node can be linked into the list using the various prev and next node fields as illustrated the resulting list after inserting the new node is illustrated in figure on the next page head curnode tail newnode figure linked modifications required to insert value into the doubly linked list as with singly linked listinserting node into non-empty sorted doubly linked list can occur in one of three placesat the frontat the endor somewhere in the middle inserting new node into the middle of list was illustrated above