package datastructure;

 public class Node {

     private Object data;

     private Node next;

     public Node() {

         this(null,null);

     }

     public Node(Object data) {

         this(data,null);

     }

     public Node(Object data, Node next) {

         this.data = data;

         this.next = next;

     }

     public Object getData() {

         return data;

     }

     public void setData(Object data) {

         this.data = data;

     }

     public Node getNext() {

         return next;

     }

     public void setNext(Node next) {

         this.next = next;

     }

 }

 package datastructure;

 import java.util.Scanner;

 public class LinkList implements IList {

     private Node head;  //单链表的头指针

     public LinkList(){

         head=new Node(); //初始化头指针

     }

     public LinkList(int n,boolean Order) throws Exception{

         this();

         if(Order)

             create1(n); // 尾插法

         else

             create2(n); // 头插法

     }

     private void create1(int n) throws Exception {

         Scanner sc=new Scanner(System.in);

         for(int j=0;j<n;j++)

             insert(0,sc.next());

     }

     private void create2(int n) throws Exception {

         Scanner sc=new Scanner(System.in);

         for(int j=0;j<n;j++)

             insert(length(),sc.next());

     }

     public void clear() {

         head.setData(null);

         head.setNext(null);

     }

     public boolean isEmpty() {

         return head.getNext()==null;

     }

     public int length() {

         Node p=head.getNext();

         int length=0;

         while(p!=null){

             p=p.getNext();

             length++;

         }

         return length;

     }

     public Object get(int i) throws Exception {

         Node p=head.getNext();

         int j=0;

         while(p!=null&&j<i){

             p=p.getNext();

             j++;

         }

         if(j>i||p==null){

             throw new Exception("第i个元素不存在");

         }

         return p.getData();

     }

     public void insert(int i, Object x) throws Exception {

         Node p =head;

         int j=-1;

         while(p!=null&&j<i-1){

             p=p.getNext();

             j++;

         }

         if(p==null||j>i-1){

             throw new Exception("插入位置不合法");

         }

         Node s=new Node(x);

         s.setNext(p.getNext());

         p.setNext(s);

     }

     public void remove(int i) throws Exception {

         Node p=head;

         int j=-1;

         while(p.getNext()!=null&&j<i-1){

             p=p.getNext();

             j++;

         }

         if(j>i-1||p.getNext()==null)

             throw new Exception("删除位置不合法");

         p.setNext(p.getNext().getNext());

     }

     public int indexOf(Object x) {

         Node p=head.getNext();

         int j=0;

         while(p!=null&&!p.getData().equals(x)){

             p=p.getNext();

             j++;

         }

         if(p==null)

             return -1;

         else

             return j;

     }

     public void display() {

         Node node =head.getNext();

         while(node!=null){

             System.out.println(node.getData()+" ");

             node=node.getNext();

         }

         System.out.println();

     }

 }