import java.io.*;


public class bean
       {
		   public static void main(String args[])
		      {
                  linklist  list=new linklist("end");
                  int i,count;
                  String str="",str1="";

                  count=getnumber();
                  for(i=0;i<count;i++)
                  {   System.out.print("請輸入第"+(i+1)+"個字符串:");
                      str=getstring();
					  list.insertatbegin(str);  //向空鏈表中插入用戶希望的字符串數目
				      System.out.println(list.visitallnode());//遍歷顯示各節點

				  }

				  System.out.print("請輸入您希望在哪個字符串后面插入:");
				  str=getstring();
				  System.out.print("請輸入您要插入的字符串:");
				  str1=getstring();
				  list.insertafterid(str1,str);  //在指定位置插入字符串
				  System.out.println(list.visitallnode());//遍歷插入操作過后的各節點
                  list.sort(count);
				  System.out.print("請輸入您將要刪除的字符串:");
				  str=getstring();
				  if(list.removeatid(str))
				          System.out.println(list.visitallnode());

				  else
				          System.out.println("鏈表中不存在這個字符串!"); //刪除字符串

				    list.sortstring(count); //排序
				    //System.out.println(list.visitallnode());
				    System.out.println(list.m_firstnode.getdata());
				     System.out.println(list.visitallnode());

				  list.removeall(); //刪除整個鏈表


			  }

		  public static int getnumber()//取得字符串個數
			  {
				  int count=0;
				  String s;

				  System.out.print("請輸入您將輸入字符串的個數:");

				  try{
					      BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
					 	  s=br.readLine();
					 	  count=Integer.parseInt(s);
					 }catch(IOException e){}

				  return count;

			  }
		 public  static String getstring()//取得字符串
		     {
				 String s="";

				 try{
				 	  BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
				 	  s=br.readLine();
					 }catch(IOException e){}

				 return s;
			 }


	   }




class linklist
	   {
		   Node m_firstnode;

		   linklist()//構造函數
		   		{
					m_firstnode=null;
				 }

		   linklist(String data)
		   		 {
					 m_firstnode=new Node(data);
				 }

		   String visitallnode()//遍歷表中的每個節點
		         {
					 Node next=m_firstnode;
					 String s="";

					 while(next!=null)
					    {
							 s=s+next.getdata()+";  ";
							 next= next.getnext(); //使next指向下一個節點
						}

					 return s;
				 }
			void sortstring(int counta)
			{
				Node now=m_firstnode,now2=m_firstnode;
				int a=0,i,j;

               for(i=counta;i>0;i--)
               	   {
					 now=m_firstnode;
               		for(j=0;j<i;j++)
				      {
						  now2=now.getnext();
						  a=now.comparenode(now2);
				          if(a>0)
				          {
							  insertafterid(now.getdata(),now2.getdata());
				              removeatid(now.getdata());
					      }

				          now=now2;

				      }
			       }
			}//冒泡排序

			void sortstring2(int countb)
			{
				Node now=m_firstnode,now2,temp=m_firstnode;
				int a=0,i,j,k;
				String s;
				for(i=0;i<countb;i++)
				{
					now=m_firstnode;
					for(j=0;j<i;j++)
					  {
						  now2=now.getnext();
						  if(now.comparenode(now2)>0)
						     {
								 insertafterid(now.getdata(),now2.getdata());
								 removeatid(now.getdata());
						     }
						  now=now2;
					  }

				}
	 	    }



		   Node getprenode(Node now)//獲得前一個節點
		         {
					 Node next=m_firstnode;
					 while(next.getnext()!=now)
					 	{
							next=next.getnext();
						}
					 return next;
				 }

			void sort(int countb)
			 {
			     int i;
			     for(i=0;i<777;i++)
			       sortstring(countb);
		     }

			void sort2(int countb)
			 {
			     int i;
			     for(i=0;i<777;i++)
			       sortstring(countb);
		     }


		   void insertatbegin(String data)//插入
		   	     {
					 if(m_firstnode==null)
					 		m_firstnode=new Node(data);
					 else
					 m_firstnode=new Node(data,m_firstnode);
			     }

		  void insertafterid(String data,String id)//插在字符串id的后面
		         {
					 Node next=m_firstnode;

					 if(next==null)
					 		m_firstnode = new Node(data);
					 else
					   {
						   while(next.getnext()!=null&&!(next.getdata().equals(id)))
						       next=next.getnext();
						   next.setnext(new Node(data,next.getnext()));
					   }
				 }

           boolean removeatid(String id) //刪除
                 {
					 Node ahead =m_firstnode;
					 Node follow = ahead;

					 if(ahead==null)
					      return false;
					 else if(ahead.getdata().equals(id))
					       {
							   m_firstnode=m_firstnode.getnext();
							   return true;
						   }
					 else
					      {
							  ahead=ahead.getnext();
							  while(ahead.getdata()!=null)
							      {
									  if(ahead.getdata().equals(id))
									    {
											follow.setnext(ahead.getnext());
											return true;
										}
										follow=ahead;
										ahead=ahead.getnext();
								  }
							   return false;
						  }
				 }

		   void removeall()//刪除所有節點
		         {
					 m_firstnode=null;
				 }



	   }



class queue extends linklist
      {
		  boolean isempty()//判斷隊列是否為空
		     {
				 if(m_firstnode==null)
				   return true;
				 else
				   return false;
			 }

		  void enqueque(String newdata)//加隊操作
		     {
				 Node next=m_firstnode;
				  if(next==null)
				     m_firstnode=new Node(newdata);
				  else
				    {
						while(next.getnext()!=null)
						    next=next.getnext();
						 next.setnext(new Node(newdata));
					}
			 }

		  String dequeue()//減隊操作
		     {
				 String data;
				 if(!isempty())
				   {
					   data=m_firstnode.getdata();
					   m_firstnode=m_firstnode.getnext();
					   return data;
				   }
				  else return null;
			 }
	  }









class Node
      {
		 private String m_string;  //節點保存的數據
		 private Node   m_next;    //節點中的指針屬性,指向下一個node對象的對象引用

		  Node(String data)  //構造函數
		      {
				  m_string = data;
				  m_next = null;

			  }

		  Node(String data,Node next)
		      {
				  m_string=data;
				  m_next=next;
			  }

		 void setdata( String data) //修改數據
		      {
				  m_string=data;
			  }

		 String getdata()   //獲得數據
		      {
				  return m_string;
			  }

		 void setnext(Node next) //修改節點中的指針
		 	  {
				  m_next=next;
			  }

		 Node getnext()  //獲得節點中指針指向的對象引用
		 	  {
				  return m_next;
			  }

		 int comparenode(Node now)
		      {
				  int a;
				  a=m_string.compareTo(now.getdata());
				  return a;
			  }

		 void setnode(Node node)
		      {
				  m_string=node.getdata();
				  m_next=node.getnext();
			  }
		 Node getnumnext(int i)
		 	 {
		 		int j;
		 	    Node now=new Node("");
		 		for(j=0;j<i;j++)
		 		now=m_next.getnext();
		 		return now;

		      }


	  }