Stuff

import java.util.*; 
 
public class myDLList <T> {
	protected myDLNode<T> head;
	protected myDLNode<T> tail;
	int size;
	
public myDLList() {
	size = 0;
	head = new myDLNode<T>(null, null, null);
	tail = new myDLNode<T>(null, null, null);
	head.setNext(tail);
	tail.setPrevious(head);
}// – creates a new doubly linked list

public int size() {
	return (size);
}// – returns the size of the linked list; O(1)

public boolean isEmpty() {
	return (head.getNext() == head);
}// – returns true is the linked list is empty (returns false otherwise); O(1)

public void insertFirst(T e) throws InvalidPositionException {
 	if((e == null) || (e == head)) {
 		throw new InvalidPositionException("insertFirst.");
 	}
 	myDLNode<T> newNode = new myDLNode<T>(null, null, null);
 	newNode.setElement(e); 
    if (isEmpty()) {
    	tail = newNode; 
    } else {
    	head.prev = newNode; 
    	newNode.next = head; 
    	head = newNode;
    	size++;
    } 	
}// throws InvalidPositionException – insert the element as the first element in the list; O(1)

public void insertLast(T e) throws InvalidPositionException {
 	if((e == null) || (e == tail)) {
 		throw new InvalidPositionException("insertLast.");
 	}
 	myDLNode<T> newNode = new myDLNode<T>(null, null, null);
 	newNode.setElement(e);
    if (isEmpty()) {
    	head = newNode; 
    } else {
    	tail.next = newNode; 
    	newNode.prev = tail; 
    	tail = newNode;
    	size++;	
    }    
}// throws InvalidPositionException – insert the element as the last element in the list; O(1)

public myDLNode<T> getFirst() throws InvalidPositionException {
	if(head == null) {
 		throw new InvalidPositionException("getFirst.");
 	}
	return (head);
}// throws InvalidPositionException – returns first element in the list; O(1)

public myDLNode<T> getLast() throws InvalidPositionException {
	if(tail == null) {
 		throw new InvalidPositionException("getLast.");
 	}
	return (tail);
}// throws InvalidPositionException – returns the last element in the list.; O(1)

public T delete(myDLNode<T> p) throws InvalidPositionException {
	if(p == null) {
 		throw new InvalidPositionException("delete.");
 	}
 	p.getPrevious().setNext(p.getNext());
 	p.getNext().setPrevious(p.getPrevious());
 	p.setNext(null);
 	p.setPrevious(null);
 	size--;
 	return (p.getElement()); 		
}// throws InvalidPositionTxception – deletes nodes p from the list. It returns the element; O(1)

public T deleteFirst() throws InvalidPositionException {
	myDLNode<T> temp = head;
	T newElement;
	if(head.next == tail) {
 		throw new InvalidPositionException("deleteFirst.");
 	}
    if (head.next == null) 
      tail = null; 
    else
    head.next.prev = null;
    newElement = head.getElement();
    head = head.next; 
 	size--;
 	return newElement;	
}// throws InvalidPositionTxception – deletes the first element in the list. It returns the element; O(1)

public T deleteLast() throws InvalidPositionException {
	myDLNode<T> temp = tail;
	T newElement;
	if(tail.prev == head) {
 		throw new InvalidPositionException("deleteFirst.");
 	}
    if (head.next == null) 
      head = null; 
    else
    tail.prev.next = null;
    newElement = tail.getElement();
    tail = tail.prev; 
 	size--;
 	return newElement;
}// throws InvalidPositionTxception – deletes the last element in the list. It returns the element; O(1)

public myDLNode <T> search(T e) {
	myDLNode<T> index; 
    boolean found;
	index = head;   
    found = false;   
	while(index != null && !found) { 
    	if(index.getElement() == e) {  
        	found = true;
        } else {
            index = index.next; 
        }
	}                         
return index;	
}// – searches for the first occurrence of element e in the linked list. It returns the corresponding node in the list; O(n)

public myDLNode <T> searchAfter(myDLNode <T> p, T e) throws InvalidPositionException {	
	if((p == null) || (p == tail)) {
 		throw new InvalidPositionException("searchAfter.");
 	}
	myDLNode<T> index; 
    boolean found;
	index = tail;   
    found = false;	
	while(index != p && !found) { 
    	if(index.getElement() == e) {  
        	found = true;
        } else {
            index = index.prev; 
        }
	}                         
return index;
}// throws InvalidPositionException – searches for the first occurrence of element e after node p (not including node p). It returns the corresponding node in the list

public myDLNode <T> searchBefore(myDLNode <T> p, T e) throws InvalidPositionException {
	if((p == null) || (p == head)) {
 		throw new InvalidPositionException("searchBefore.");
 	}
	myDLNode<T> index; 
    boolean found;
	index = head;   
    found = false;	
	while(index != p && !found) { 
    	if(index.getElement() == e) {  
        	found = true;
        } else {
            index = index.next; 
        }
	}                         
return index;
}// throws InvalidPositionException – searches for the first occurrence of element e before node p (not including node p). It returns the corresponding node in the list.

public myDLNode<T> searchAfter(myDLNode <T> p, T e, int i) throws InvalidPositionException {
	if((p == null) || (p == tail)) {
 		throw new InvalidPositionException("searchAfter.");
 	}
	myDLNode<T> index; 
    int found;
	index = tail;   
    found = 0;	
	while(index != p && found != i) { 
    	if(index.getElement() == e) {  
        	found++;
        } else {
            index = index.prev; 
        }
	}                         
return index;	
}// - searches for the ith occurrence of element e in the linked list after node p and not including p. It returns the corresponding node in the list.
    
}