/** Insert the given element at the beginning of the list, returning * the new position; O(1) time */ public Position insertFirst(Object element) { numElts++; DNode newNode = new DNode(header, header.getNext(), element); header.getNext().setPrev(newNode); header.setNext(newNode); return newNode; } /**Remove the given position from the list; O(1) time */ public Object remove(Position p) throws InvalidPositionException { DNode v = checkPosition(p); numElts--; DNode vPrev = v.getPrev(); DNode vNext = v.getNext(); vPrev.setNext(vNext); vNext.setPrev(vPrev); Object vElem = v.element(); // unlink the position from the list and make it invalid v.setNext(null); v.setPrev(null); return vElem; } /** Replace the element at the given position with the new element * and return the old element; O(1) time */ public Object replace(Position p, Object element) throws InvalidPositionException { DNode v = checkPosition(p); Object oldElt = v.element(); v.setElement(element); return oldElt; }