/*
    LinkedList.java
    CIS 260
    2014-03-11
    David Klick

    Implementation of a linked list with generics.

    Modified: 2016-03-28 to include addFront(T), addBack(T),
        removeFront(), removeBack(), and change toString()
*/
import java.util.NoSuchElementException;

public class LinkedList<T> {
    private class Node<T> {
        T data;
        Node<T> next;
    }
    private Node<T> head;
    
    public LinkedList() { head = null; }
    
    public int length() {
        int count = 0;
        Node<T> p = head;
        while (p != null) {
            count++;
            p = p.next;
        }
        return count;
    }

    @Override public String toString() {
        StringBuilder sb = new StringBuilder();
        Node<T> p = head;
        while (p != null) {
            if (sb.length() > 0) sb.append(", ");
            sb.append(p.data);
            p = p.next;
        }
        return sb.toString();
    }

    public T front() {
        if (head == null) throw new NoSuchElementException();
        return head.data;
    }

    public T back() {
        Node<T> current = head;
        if (head == null) throw new NoSuchElementException();
        while (current.next != null) current = current.next;
        return current.data;
    }

    public T get(int ndx) {
        if (ndx < 0) throw new NoSuchElementException();
        int temp = 0;
        Node<T> current = head;
        while (temp < ndx) {
            if (current == null) throw new NoSuchElementException();
            if (ndx == temp) return current.data;
            current = current.next;
            temp++;
        }
        if (current == null) throw new NoSuchElementException();
        return current.data;
    }

    public boolean isEmpty() { return (head == null); }

    public LinkedList<T> addBack(T data) {
        Node<T> current = head;
        Node<T> p = new Node<T>();
        p.data = data;
        p.next = null;
        if (head == null) {
            head = p;
        } else {
            while (current.next != null) current = current.next;
            current.next = p;
        }
        return this;
    }

    public LinkedList<T> addFront(T data) {
        Node<T> current = head;
        Node<T> p = new Node<T>();
        p.data = data;
        p.next = head;
        head = p;
        return this;
    }

    public LinkedList<T> add(T data) {
        addBack(data);
        return this;
    }

    public T removeFront() {
        if (head == null) throw new NoSuchElementException();
        Node<T> hold = head;
        head = head.next;
        return hold.data;
    }
    
    public T removeBack() {
        if (head == null) throw new NoSuchElementException();
        Node<T> curr = head;
        Node<T> prev = null;
        while (curr.next != null) {
            prev = curr;
            curr = curr.next;
        }
        if (prev == null) {
            head = null;
        } else {
            prev.next = null;
        }
        
        return curr.data;
    }
    
    public boolean remove(T data) {
        if (head == null) return false;
        if (head.data.equals(data)) {
            head = head.next;
            return true;
        }
        Node<T> prev = head;
        Node<T> curr = prev.next;
        while (curr != null) {
            if (curr.data.equals(data)) {
                prev.next = curr.next;
                return true;
            } else {
                prev = curr;
                curr = prev.next;
            }
        }
        return false;
    }
}