ArrayList

public class ArrayList<E> implements List<E> {	// The type parameter E is a placeholder for what kind of data will be stored in this list
    private E[] data = (E[])(new Object[3]);  // The array where the data is stored -- Java doesn't allow generic array creation, so we just create an array of Objects and cast it to E[]
    private int size = 0;   // The number of elements actually stored in the list
    
    // Returns the item stored at the specified list index
    // Big-O: O(1)
    public E get(int index) {
        if (index >= 0 && index < size)
            return data[index];
        else {
            System.out.println("You can't do that!");
            throw new IndexOutOfBoundsException();
        }
    }
    
    // Replaces the item at the specified list index with newValue
    // Big-O: O(1)
    public void set(int index, E newValue) {
        if (index >= 0 && index < size)
            data[index] = newValue;
        else {
            System.out.println("You can't do that!");
            throw new IndexOutOfBoundsException();
        }
    }
    
    // Adds the newValue to the end of the list
    // Big-O: O(1) if an array resize is not needed
    //        O(n) if an array resize is needed
    // If we double the array length every time a resize is needed, then this becomes "amortized constant time"
    //  (basically, "constant time on average")
    public void add(E newValue) {
        if (size == data.length) {    // Array has reached its capacity
            E[] newData = (E[])(new Object[data.length * 2]); // Create a new, larger array
            for (int i = 0; i < data.length; i++)           // Copy the old elements to the new array
                newData[i] = data[i];
            data = newData;                                 // Point data at the new array
        }
        data[size] = newValue;  // Add the newValue at the end of the array
        size++;
    }
    
    // Removes and returns the list item at the specified index
    // Big-O: O(n)
    public E remove(int index) {
        if (index >= 0 && index < size) {
            E thingToReturn = data[index];
            
            for (int i = index; i < size - 1; i++)  // Shift (to the left) all array elements starting from index
                data[i] = data[i+1];
            size--;
            
            return thingToReturn;
        } else {
            System.out.println("You can't do that!");
            throw new IndexOutOfBoundsException();
        }
    }
    
    public void addAll(ArrayList<E> anotherList) {
    		for(int i = 0; i < anotherList.getSize(); i++ ) {
    			add(anotherList.get(i));
    		}	
    }
    
    public ArrayList<E> slice(int beginIndex, int endIndex) {
        ArrayList<E> simplified = new ArrayList<>();
    		if (beginIndex >= 0 && endIndex <= size) {
    			for(int i = beginIndex; i < endIndex; i++) {
    				simplified.add(data[i]);
            }
    			//data = simplified;
        		return simplified;
    		}
        else {
            System.out.println("You can't do that!");
            throw new IndexOutOfBoundsException();
        }
    }
    
    public void trimToSize() {
    		E[] smaller = (E[])(new Object[size]); 
    		for(int i = 0; i < size; i++) {
    			smaller[i] = data[i];
    				
    		}
    		data = smaller; 
    }
    
    public String toString() {
        String r = "ArrayList (size = " + size + ", capacity = " + data.length + "), containing the following:\n";
        for (int i = 0; i < size; i++)
            r += data[i] + "\n";
        return r;
    }
    
    public static void main(String[] args) {
    	// When we create the ArrayList object, replace E with the data type to be
    	//  stored in the list (in this case, String)
        ArrayList<Integer> theList = new ArrayList<>();
        System.out.println(theList);
        theList.add(-3);
        System.out.println(theList);
        theList.add(0);
        System.out.println(theList);
        theList.add(43);
        System.out.println(theList);
        theList.add(812903218);
        System.out.println(theList);
        theList.remove(1);
        System.out.println(theList);
    }
}

LinkedList

public class LinkedList<E> implements List<E> {
	
	// Node is written as a private nested class of LinkedList, since we don't
	//  intend to use Node outside of this class.  This way, LinkedList has
	//  direct access to the instance variables of Node.
	private static class Node<E> {	// "static" means that Node does *not* have access to the instance variables of LinkedList
		private E data;
		private Node<E> next;

		// Constructor (generated automatically through Eclipse)
		public Node(E data, Node<E> next) {
			super();
			this.data = data;
			this.next = next;
		}
	}
	
	private Node<E> head;	// Maintains the location of the head node
	private int size = 0;	// Number of elements in the list

	// Big-O: O(n) due to the call to nodeAt
	@Override
	public E get(int index) {
		return nodeAt(index).data;
	}

	// Big-O: O(n) due to the call to nodeAt
	@Override
	public void set(int index, E newValue) {
		nodeAt(index).data = newValue;
	}

	// Big-O: O(1) if adding to the head of the list, O(n) if adding to the tail
	@Override
	public void add(E newValue) {
		if (size == 0)
			head = new Node<>(newValue, null);
		else
			nodeAt(size - 1).next = new Node<>(newValue, null);
		size++;
	}

	// Big-O: O(1) if removing from the head of the list, O(n) for other locations
	@Override
	public E remove(int index) {
		E temp;
		if (index == 0) {
			temp = head.data;
			head = head.next;
		} else {
			Node<E> nodeBefore = nodeAt(index - 1);
			temp = nodeBefore.next.data;
			nodeBefore.next = nodeBefore.next.next;
		}
		size--;
		return temp;
	}

	// Returns the Node object at the specified index in the list.
	// Throws an IndexOutOfBoundsException if the index is invalid.
	// Big-O: O(n)
	private Node<E> nodeAt(int index) {
		if (index >= 0 && index < size) {
			Node<E> temp = head;
			for (int i = 0; i < index; i++)
				temp = temp.next;
			return temp;
		} else
			throw new IndexOutOfBoundsException();
	}
	
	public E remove(E item) {
		//E delete; 
		for(int i = 0; i < size; i++) {
			if(nodeAt(i).data == item) {
				remove(i);
				size--;
				return item;
			}
		}
		return null;
	}
	
	//Reverses a LinkedList
	public void reverse() {
		Node<E> previous = null;
		Node<E> current = head; 
		Node<E> next = null;
		while(current != null) {
			next = current.next;
			current.next = previous;
			previous = current;
			current = next;
		}
		head = previous;
		
	}
	

	public String toString() {
		String r = "LinkedList (size = " + size + "), containing: head -> ";
		for (Node<E> temp = head; temp != null; temp = temp.next)
			r += temp.data + " -> ";
		r += "null";
		return r;
	}
	
	public static void main(String[] args) {
		LinkedList<String> myList = new LinkedList<>();
		System.out.println(myList);
		myList.add("stuff");
		myList.add("four");
		myList.add("for");
		myList.add("fore");
		myList.add("fo");
		myList.add("faux");
		myList.add("4");
		System.out.println(myList);
		myList.remove(4);
		myList.remove(0);
		myList.remove(1);
		System.out.println(myList);
	}
}

List

public interface List<E> {	// The type parameter E is a placeholder for what kind of data will be stored in this list
    // Returns the item stored at the specified list index
    E get(int index);
    
    // Replaces the item at the specified list index with newValue
    void set(int index, E newValue);
    
    // Adds the newValue to the end of the list
    void add(E newValue);
    
    // Removes and returns the list item at the specified index
    E remove(int index);
}