//Garth Bruen
//10.09.02

public class LL22{


	private Node head;
	private Node next;
	private Node previous;

	class Node{
		int data;
		Node next = null;
		Node previous = null;
	}//end Node()


	public void addTo(int data){

		Node newNode = new Node();
		newNode.previous = null;		
		newNode.data = data;
		newNode.next = head;
		head = newNode;

	}//end addFirst()

	public Node backlink(){

		Node current = head;
		Node prev = null;		
		while(current.next != null){
			prev = current;
			current = current.next;
			
			if(current != null){
			current.previous = prev;
			
			}
		}

	return current;
	}//end

	public void printList(){
		Node current = head;

		while(current != null){
			System.out.print(current.data);
			if(current.previous != null){
				System.out.print(current.previous.data);
			}
			current = current.next;

		}
		
		System.out.println();

	}//end printList()
	
	LL22 moveToFront(int i){
		Node current = head;

		while(current != null){
			if(current.data == i){
				
				LL22 temp = new LL22();

				temp.addTo(i);
				current = head;
				//current = current.next;
				while(current != null){
					if(current.data != i){
					temp.addTo(current.data);
					}
					current = current.next;
					
				}
				temp.backlink();
				temp.printList();
				return temp;			
			}else{
			current = current.next;
			}
		}
		return this;
	}
	




	public static void main(String args[]) throws Exception
	{
		LL22 unsorted = new LL22();
		unsorted.addTo(1);
		unsorted.addTo(2);
		unsorted.addTo(3);
		unsorted.addTo(4);
		unsorted.addTo(5);
		unsorted.addTo(6);
		unsorted.addTo(7);
		unsorted.addTo(8);
		unsorted.addTo(9);
		unsorted.backlink();
		unsorted.printList();
		unsorted = unsorted.moveToFront(3);
		unsorted.printList();
		
	}//End main
}