import java.util.function.Consumer;

public class IntLinkedList implements Cloneable {

	/**
	 * point to the first element of our linked list
	 */
	private IntLinkedNode head;
	/**
	 * point to the last element of our linked list
	 */
	private IntLinkedNode tail;
	/**
	 * number of elements in our list
	 */
	private int size;

	public IntLinkedList() {
		head = null;
		tail = null;
		size = 0;
	}

	public void insertBack(int element) {
		IntLinkedNode n = new IntLinkedNode(element);
		if (empty()) {
			head = n;
		} else {
			tail.setLink(n);
		}
		tail = n;
		++size;
	}

	public void insertFront(int element) {
		head = new IntLinkedNode(element, head);
		if (size == 0) {
			tail = head;
		}
		++size;
	}

	public void insertAfter(int element, IntLinkedNode node) {
		node.setLink(new IntLinkedNode(element, node.getLink()));
		++size;
		if (tail == node) {
			tail = tail.getLink();
		}
	}

	public void addAll(IntLinkedList list) {
		if (list.empty()) {
			return;
		}
		IntLinkedList copy = list.clone();
		if (this.empty()) {
			this.head = copy.head;
			this.tail = copy.tail;
			this.size = copy.size;
			return;
		}
		tail.setLink(copy.head);
		tail = copy.tail;
		size += copy.size;
	}
	
	public void prependAll(IntLinkedList list) {
		if (list.empty()) {
			return;
		}
		IntLinkedList copy = list.clone();
		if (this.empty()) {
			this.head = copy.head;
			this.tail = copy.tail;
			this.size = copy.size;
			return;
		}
		copy.tail.setLink(head);
		head = copy.head;
		size += copy.size;
	}

	public boolean remove(int target) {
		IntLinkedNode prev = null;
		for (IntLinkedNode curr = head; curr != null; curr = curr.getLink()) {
			if (curr.getData() == target) {
				if (prev == null) {
					head = head.getLink();
				} else {
					prev.setLink(curr.getLink());
				}
				if (tail == curr) {
					tail = prev;
				}
				--size;
				return true;
			}
			prev = curr;
		}
		return false;
	}

	public boolean empty() {
		return size() == 0;
	}

	public int size() {
		return size;
	}

	public IntLinkedNode find(int target) {
		return findNthOf(target, 1);
	}

	public IntLinkedNode findNthOf(int target, int expected) {
		int seen = 0;
		for (IntLinkedNode c = head; c != null; c = c.getLink()) {
			if (c.getData() == target) {
				++seen;
				if (seen == expected) {
					return c;
				}
			}
		}
		return null;
	}

	public int countOccurences(int target) {
		Integer count = 0;
		for (IntLinkedNode c = head; c != null; c = c.getLink()) {
			if (c.getData() == target) {
				++count;
			}
		}
		return count;
	}

	public String toString() {
		StringBuilder sb = new StringBuilder("( ");
		forEach (val -> sb.append(val).append(' '));
		return sb.append(')').toString();
	}

	public IntLinkedList clone() {
		try {
			IntLinkedList copy = (IntLinkedList)super.clone();
			copy.head = head.clone();
			IntLinkedNode c = copy.head;
			while (c.getLink() != null) {
				c = c.getLink();
			}
			copy.tail = c;
			return copy;
		} catch (CloneNotSupportedException e) {
			throw new RuntimeException("Nope");
		}
	}
	
	private void forEach (Consumer<Integer> f) {
		for (IntLinkedNode c = head; c != null; c = c.getLink()) {
			f.accept(c.getData());
		}
	}

}