Linked List

import java.util.Collection;
import java.util.Iterator;


public class linkedLists{
    public static void main(String[] args){
        //Create 10 names stored in a linked list
        //test each method 
        //methods to test
        //add, remove, indexOf, get, lastIndexOf, set, isEmpty, addFirst, addLast, getLast, removeFirst, removeLast
        MyLinkedList<String> list = new MyLinkedList<>();
        list.add("Dog");
        for (String e: list){
            System.out.println("1");
        }
    }
}


//lets make the myList interface and then we will use it to build the linked list class
//start by writing down all the methods, then go back later to implement when designing linked list class
interface myList<E> extends Collection<E>{


    //add it onto this specific index, the current element at this index is shifted to the right of the list(index +1)
    public void add(int index, E e);

    //value at certain index
    public E get(int index);

    //first matching index of e
    //-1 if not there
    public int indexOf(Object e);

    //return the last index seen of E
    //Run and use logic: if ele == e, int = index, return int at end
    //how do we know we've reached the end? while list.next != null 
    //-1 if not there
    public int lastIndexOf(E e);

    //traverse index times, remove it. Update pointer of last dude, or do we just let it point?
    //return the removed item
    public E remove(int index);

    //traverse index times, update value
    //return the new Object
    public E set(int index, E e);

    @Override //add something to the end, while next not null, keep going. when next is null add to end, modify pointer
    public default boolean add(E e){
        add(size(), e);
        return true;
    }

    @Override 
    public default boolean isEmpty(){
        return size()==0;
    }

    @Override
    public default boolean remove(Object e){
        if (indexOf(e) >= 0){
            remove(indexOf(e));
            return true;
        }
        else
        return false;
    }

    

}


class MyLinkedList<E> implements myList<E>{
    
    //What is Node? A self-defined class to help us keep track of who we are and who is next. 
    //By default Node<E>.next is null until we link them with our implemented methods
    private static class Node<E> {
		E element;
		Node<E> next;

		public Node(E e) {
			this.element = e;
		}
	}
    private Node<E> head, tail;
    private int size = 0;

    public MyLinkedList(){
        //this is just a list with nodes both head and tail with values Null
    }

    public MyLinkedList(E[] objects){
        for(int i = 0; i < objects.length; i++){
            add(objects[i]);
        }
    }

    public E getFirst(){
        if (size() == 0){
            return null;
        }
        else
            return head.element;
    }

    public E getLast(){
        if (size() == 0){
            return null;
        }
        else
            return tail.element;
    }

    public void addFirst(E e){
        Node<E> newNode = new Node<>(e);
        //this spawns a new node, lets connect it to our current list by making this the head Node 
        //and our newNode.next to be the previous head, then increase the size
        newNode.next = head;
        head = newNode;
        size++;

        //what if we only have one element? We can tell if this the last one when tail is null
        //then we set 
        if (tail == null){
            tail = head;
            head.next = null;
        }


    }
    
    public void addLast(E e){
        Node<E> newNode = new Node<>(e);
        //we get the end.next and set it to newNode. How do we get to end?
        //we are constantly tracking the end with tail. Tail's .next always should point to null
        //so lets assign tail.next to newNode and then update tail to newNode
        //Once tail = newNode, it's .next won't be defined anymore and is null

        //if the list we're adding to is empty
        if (tail == null){
            head = tail = newNode;
        }
        else{
            tail.next = newNode;
            tail = newNode;
        }
        size++; //dont forget the size
    }

    public E removeFirst(){
        //to remove, we have to set head to head.next and decrement size
        if (size() == 0){
            return null;
        }else{
        Node<E> newNode = head;
        head = head.next;
        size--;
        if (head == null){
            tail = null;
        }//if our operation results in an empty list lets delete relationships
        return newNode.element;
        }
    }

    public E removeLast(){
        //we have to know what comes before tail, so we need traversal
        if (size() == 0){
            return null;
        }else if(size == 1){
            Node<E> newNode = head;
            head = null;
            tail = head;
            size = 0;
            return newNode.element;
        }else{
            Node<E> current = head;
            for (int i = 0; i < size()-2; i++){
                current = current.next;
            }
            tail = current;
            tail.next = null;
            size--;
            return current.element;
        }
    }



    //Benearth are all of the need to be implemented methods
    @Override 
    public String toString(){
        StringBuilder result = new StringBuilder("[");

        Node<E> current = head;
        for (int i = 0; i < size; i++){
            result.append(current.element);
        
            if (current != null){
                result.append(", ");
            }
            else{
                result.append("]");
            }
        }
        return result.toString();
    }
    @Override
    public int size() {
        // TODO Auto-generated method stub
        return size;
    }

    @Override
    public boolean contains(Object o) {
        //edge cases?
        if (size() == 0){
            return false;
        }
        Node<E> current = head;
        while(current != null){
            if (current.element == o){
                return true;
            }
        }
        return false;
    }

    @Override
    public Iterator<E> iterator() {
        // TODO Auto-generated method stub
        return new LinkedListIterator();
    }

    private class LinkedListIterator implements java.util.Iterator<E>{
        Node<E> current = head;
        @Override
        public boolean hasNext() {

            return (current != null);
        }

        @Override
        public E next() {
            E e = current.element;
            current = current.next;
            return e;
        }

        @Override
        public void remove(){
            current = current.next;
            size--;
        }
        
    }

    @Override
    public Object[] toArray() {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public <T> T[] toArray(T[] a) {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public void clear() {
        //empty everything
        size = 0;
        head = tail = null;
        //by setting head tail and size to 0 we have eliminated a wa
    }

    @Override
    public void add(int index, E e) {
        //how do we add? Well lets think about edge cases. 
        //If we have no elements, lets do a simple add(e)
        //If we want to add to the front, lets addFirst(e)
        //if we want to add to the end, lets do addLast(e)
        //addlast handles issues for empty list, but we specify an index
        if (index == 0){
            addFirst(e);
        }
        else if(index >= size()){
            addLast(e);
        }

        //we shall start at the head and move .next until we get to our specified index
        //take note of our location our location's .next will be held temporarily
        //We set our location's next to e, then we set e's next to temp
        Node<E> current = head;
        for (int i = 0; i < index; i++){
            current=current.next;
        }
        Node<E> temp = current.next;
        current.next = new Node<>(e);
        current.next.next = temp;

        size++; //increase size the ocky way
        
    }


    @Override
    public E get(int index) {
        //traverse to index, return element
        if(index > size()){
            return null;
        }
        Node<E> current = head;
        for (int i = 0; i < index; i++){
            current = current.next;
        }
        return current.element;
    }

    @Override
    public int indexOf(Object e) {
        // return index of occurance of e
        // return -1 if not found
        Node<E> current = head;
        for(int i = 0; i < size(); i++){
            if (current.element == e){
                return i;
            }
        }
        return -1;

    }

    @Override
    public int lastIndexOf(E e) {
        Node<E> current = head;
        int idx = -1;
        for(int i = 0; i < size(); i++){
            if (current.element == e){
                idx = i;
            }
            current = current.next;
        }
        return idx;
    }

    @Override
    public E remove(int index) {
        //traverse to an index while keeping track of previous 
        //edge cases like removing from empty list or removing from index > size handled by removeLast()
        if (index == 0){
            return removeFirst();
        }
        if (index == size()-1){
            return removeLast();
        }
        Node<E> prev = head; //how we start at the top
        for (int i=0; i < index; i ++){
            prev = prev.next;
        }
        //after arriving at the element, we shall link to to nextnext instead
        //we need to know what curr is to return it
        Node<E> current = prev.next;
        prev.next = prev.next.next;
        size--;
        return current.element;
    }



    @Override
    public E set(int index, E e) {
        if (index >= size()){
            return null;
        }
        //traversal code
        Node<E> current = head;
        for (int i = 0; i < index; i++){
            current = current.next;
        }
        current.element = e;
        return current.element;
    }
    
}