public class LinkedList {

	public Node head;
	// public Node tail;
	int count;

	public LinkedList(int length) {
		head = null;

		for (int i = 0; i < length; i++)
			insert(i);

	}

	public LinkedList() {
		head = null;
	}

	public void clear() {
		head = null;
	}

	public void insert(int n) {
		Node cur = new Node(n);

		cur.next = head;

		head = cur;
		count++;
	}

	public void insert(Node n) {
		n.next = head;
		head = n;
		count++;
	}

	public void insert(Node n, int index) {

		if (index == 0)
			insert(n);

		Node prev, cur;

		prev = head;
		cur = head.next;

		while (cur != null && index > 1) {
			cur = cur.next;
			prev = prev.next;
			index--;
		}

		prev.next = n;
		n.next = cur;

		count++;
	}

	// Delete the node at the zero-based index.
	public void remove(int index) {
		int cur;
		Node curnode = head;

		for (cur = index; cur > 1; cur--)
			curnode = curnode.next;

		if (curnode == head)
			head = head.next;
		else
			curnode.next = curnode.next.next;

		count--;
	}

	public Node getNode(int index) {
		Node nnode = new Node(-10);
		nnode.next = head;

		Node cur = head;
		while (cur.next != null && index > 0) {
			cur = cur.next;
			index--;

		}

		return cur;
	}

	public int getVal(int index) {
		int cur;
		Node curnode = head;

		for (cur = index; cur > 0; cur--)
			curnode = curnode.next;

		// curnode should point to the node whose value we want.
		return curnode.getVal();
	}

	public void print() {
		System.out.println();

		head.print();
	}

	private void swap(Node pa, Node a, Node pb, Node b) {
		Node temp = b.next;
		pa.next = b;
		if (a.next != b) {
			b.next = a.next;
			pb.next = a;
		} else
			b.next = a;

		a.next = temp;
	}

	public void selectionSort() {
		Node cur, prev, pos;
		pos = new Node(0);
		pos.next = head;
		head = pos;

		while (pos.next != null) {
			cur = prev = pos.next;

			cur = cur.smallest();
			while (prev.next != cur)
				prev = prev.next;

			// a.smallest();

			if (cur != prev) {
				Node t = pos.next;
				swap(pos, t, prev, cur);
			}

			// System.out.println("****************");
			// head.print();

			pos = pos.next;
		}
		head = head.next; // to lose the initial node.

		// System.out.println("end of sorting, head.print is");
		// head.print();
	}

	public void insertionSort() {
		Node nnode = new Node(-10000000);
		nnode.next = head;

		Node cur, pos, pr = head;

		int index;

		while (pr.next != null) {
			pos = pr.next;

			index = 0;
			cur = nnode;
			while (cur != pos && cur.getVal() < pos.getVal()) {
				index++;
				cur = cur.next;
			}

			if (cur == pos) {
				pr = pos;
			} else {
				pr.next = pos.next;
				insert(pos, index);
			}
			// print();
		}

	}

	public int length2() {
		Node cur = head;
		int c = 0;
		while (cur != null) {
			c++;
			cur = cur.next;
		}
		return c;
	}

	public int length() {
		return count;
	}

	public int sum() {
		Node cur = head;

		int summ = 0;
		while (cur != null) {
			summ += cur.getVal();
			cur = cur.next;
		}

		return summ;
	}

	public void bubbleSort() {
		Node nnode = new Node(-10);
		nnode.next = head;

		Node pa, a, pb, b;

		int size = count, i;


		for (i = 0; i < size; i++) {
			pa = nnode;
			a = head;
			pb = head;
			b = head.next;

			while (b != null) {
				if (a.getVal() > b.getVal()) {
					swap(pa, a, pb, b);
					if (a == head)
						head = b;
					pa = b;
					b = a.next;
				} else {
					pa = pa.next;
					a = a.next;
					pb = pb.next;
					b = b.next;
				}
				// print();
			}
		}

	}

	public String toString() {
		String res = "<LinkedList: ";
		Node cur = head;

		while (cur.next != null) {
			res += cur.getVal() + ", ";
			cur = cur.next;
		}
		res += cur.getVal() + " >";

		return res;
	}
}