public void reverse(int pos1, int pos2){ // If pos1 == pos2, reversing a single list element does nothing // If pos1 > pos2, reversing an empty sublist does nothing if (pos1 >= pos2) { return; }

// If either positions are out of bonds, throw IndexOutOfBoundsException if (pos1 < 0 || pos1 > numItems-1 || pos2 < 0 || pos2 > numItems-1) { throw new IndexOutOfBoundsException(); }

// Find the node in pos1 DblListnode pos1node = items.getNext(); for (int k = 0; k < pos1; k++) { pos1node = pos1node.getNext(); }

// Find the node in pos2 DblListnode pos2node = items.getNext(); for (int j = 0; j < pos2; j++) { pos2node = pos2node.getNext(); }

DblListnode pos1Prev = pos1node.getPrev(); DblListnode pos1Next = pos1node.getNext(); DblListnode pos2Prev = pos2node.getPrev();

// If pos2 is the last node, swap pos1 and pos2 linkages if (pos2 == numItems-1) { if (pos1node.getNext() == pos2node) { pos1node.setNext(null); pos1node.setPrev(pos2node); pos1Prev.setNext(pos2node); pos2node.setPrev(pos1Prev); pos2node.setNext(pos1node); } else { pos1node.setNext(null); pos1node.setPrev(pos2Prev); pos2Prev.setNext(pos1node); pos2node.setPrev(pos1Prev); pos2node.setNext(pos1Next); pos1Prev.setNext(pos2node); pos1Next.setPrev(pos2node); } } // If pos2node isn't the last node, we do the full swamp and linkage for both else { DblListnode pos2Next = pos2node.getNext();

if (pos1node.getNext() == pos2node) { pos1node.setNext(pos2Next); pos1node.setPrev(pos2node); pos1Prev.setNext(pos2node); pos2node.setPrev(pos1Prev); pos2node.setNext(pos1node); pos2Next.setPrev(pos1node); } else { pos1node.setPrev(pos2Prev); pos1node.setNext(pos2Next); pos2Prev.setNext(pos1node); pos2Next.setPrev(pos1node); pos2node.setPrev(pos1Prev); pos2node.setNext(pos1Next); pos1Prev.setNext(pos2node); pos1Next.setPrev(pos2node); } }

// Now recursively reverse remainder of sublist reverse(pos1+1, pos2-1); }

}

2.Give the worst-case time complexity for your method above in terms of N, the list size. Identify what aspect of the method characterizes the problem size. Write a brief justification for the time complexity you give. Include in your justification any assumptions you make about the complexity of any methods that are called by your implementation.