package linkedlist;

import java.util.*;

public class LinkedList
implements Iterable<String> {
	
	// private inner class Node
	private class Node {

		private String data;
		private Node next;

		public Node(String data, Node next) {
			this.data = data;
			this.next = next;
		}
		
		public String getData() {
			return this.data;
		}
		
		public Node getNext() {
			return this.next;
		}
		
		public void setNext(Node next) {
			this.next = next;
		}

	}
	
	private class MyIterator implements Iterator<String> {
		
		private Node current;
		
		private MyIterator() {
			current = head;
		}
		
		public boolean hasNext() {
			if (current != null)
				return true;
			return false;
		}
		
		public String next() {
			// return the data and advance current to the next element
			String s = current.getData();
			current = current.getNext();
			return s;
			
		}
		
		public void remove() {
			// not implemented
		}
		
	}
	
	private Node head; // the first node in the linked list
	
	private int size;
	
	// create an empty linked list
	public LinkedList() {
		this.head = null;
		this.size = 0;
	}
	
	public Iterator<String> iterator() {
		
		// create a new MyIterator object and return it
		// the new MyIterator would be primed to start at the beginning of the list
		return new MyIterator();
		
	}
	
	// add nodes to the head of the list
	// take the data string, package it into a node, and add it as the new head of the list
	public void addToHead(String data) {
	
		// the following block is correct, but does the same as the thing at the end
//		// first case: the list is initially empty
//		if (this.head == null) {
//			// package the data in a new Node
//			// set that node's next pointer to null
//			// set the head to the new node
//			Node n = new Node(data,null);
//			this.head = n;
//		}
//		else { // the list is not initially empty
//			// package the data in a new Node
//			// set that node's next pointer to the old (existing) head node
//			// set the head to the new node
//			Node n = new Node(data,this.head);
//			this.head = n;
//		}
		
		Node n = new Node(data,this.head);
		this.head = n;
		this.size = this.size + 1;
		
	}
	
	// add data to index i
	// the old index i goes to index i+1
	public void add(String data, int i) {
		
		// we already handled the case of adding to the head
		if (i == 0) {
			addToHead(data);
		}
		else {
			// the first thing to do is to package the data into a node
			Node n = new Node(data,getNode(i));
			
			// the second thing to do is insert this node into the list
			// get the node at i-1 to point to n as its next node
			Node previous = getNode(i-1);
			if (previous != null) {
				previous.setNext(n);
				//previous.next = n;
				this.size = this.size + 1;
			}
		}
	}
	
	public void addToEnd(String data) {
		this.add(data,this.size());
	}
	
	public void deleteFromHead() {
		
		if (this.head != null) {
			this.head = this.head.getNext();
			this.size = this.size - 1;
		}
		
	}
	
	public void delete(int i) {
		
		
		if (i == 0) {
			deleteFromHead();
		}
		else {
			Node previous = getNode(i-1);
			Node nodeToDelete = getNode(i);
			
			if ((previous != null) && (nodeToDelete != null)) {
				previous.setNext(nodeToDelete.getNext());
				this.size = this.size - 1;
			}
		}
		
		
	}
	
	public void deleteFromEnd() {
		this.delete(this.size()-1);
	}
	
	// returns the size of the linked list
	public int size() {
//		Node current = head; // current is the "current position" in my count
//		int i = 0;
//		// keep following next pointers until current == null
//		while (current != null) {
//			current = current.getNext();
//			i = i + 1;
//		}
//		
//		return i;
		
		return this.size;
		
	}
	
	// return data from index i
	public String getData(int i) {
		
		Node current = getNode(i);
		if (current != null) {
			return current.getData();
		}
		return null;
	}
	
	private Node getNode(int i) {
		// traverse the list to node i
		// return a reference to that node
		// if the reference doesn't exist, return null
		Node current = this.head;
		for (int j = 0; (j < i)&&(current != null); j++) {
			current = current.getNext();
		}
		return current;

	}

}