package code;

class Node
{
    Node next;
    int data;
    public Node(int data)
    {
        this.data=data;
    }
    
}
class LinkList
{
    Node first;
    //头部
    public LinkList()
    {
        this.first=null;
    }
    public void addNode(Node no)
    {
        no.next=first;
        first=no;//在头部添加
    }
    public void delectNode()
    {
        Node n=first.next;
        first=null;
        first=n;//在头部删除
    }
    //删除指定位置
    public int Number()
    {
        int count=1;
        //查看有多少元素
        Node nd=first;
        while(nd.next!=null)
        {
            nd=nd.next;
            count++;
        }
        return count;
    }
    public void delectExact(int n)
    {
        //删除指定位置
        if(n>1)
        {
            int count=1;
            Node de=first;
            while(count<n-1)
            {
                de=de.next;
                count++;
                
            }
            de.next=de.next.next;
        }
        else
            first=first.next;
        
    }
    public void addExact(int n,Node nd)
    {
        if(n>1)//添加指定位置
        {
            int count=1;
            Node de=first;
            while(count<n-1)
            {
                de=de.next;
                count++;
                
            }
            nd.next=de.next;
            de.next=nd;

        }
        else
            first=first.next;
    }
    public int  findNode(int n)
    {
        int count=1;//查找一个数对应的位置
        Node de=first;
        while(de.data!=n)
        {
            de=de.next;
            count++;
            if(de==null)
            {
                return -1;
            }
        }
        return count;
    }
    public void print()
    {
        Node no=first;//打印所有
        while(no!=null)
        {
            System.out.println(no.data);
            no=no.next;
        }
    }
}
public class TextNode
{
    public static void main(String[] args)
    {
        LinkList ll=new LinkList();
        ll.addNode(new Node(12));
        ll.addNode(new Node(15));
        ll.addNode(new Node(18));
        ll.addNode(new Node(19));
        ll.addNode(new Node(20));
        /*System.out.println(ll.first.data);

        ll.delectNode();
        System.out.println(ll.first.data);*/
        System.out.println(ll.Number());
        ll.delectExact(3);
        ll.addExact(3, new Node(100));
        System.out.println(ll.Number());
//        ll.print();
        System.out.println(ll.findNode(112));
        
    }
}

public class DoubleLink
{
    public static void main(String[]args)
    {
        Node2 no=new Node2(5);
        no.addLeft(new Node2(6));
        no.addRight(new Node2(7));
        /*no.print();
        no.print2();*/
        no.addExact2(1, new Node2(8));
        no.print();
        System.out.println("--------------");
        no.print2();
    }
}
class Node2
{
    public Node2 first;
    public Node2 end;
    public Node2 left;
    public Node2 right;
    int data=0;
    public Node2(int n)
    {
        
        first=this;
        end=this;
        
        first.data=n;
    }
    //从头部添加
    public void addLeft(Node2 before)
    {
        first.left=before;
        before.right=first;
        first=before;
    }
    //从尾部添加
    public void addRight(Node2 after)
    {
        end.right=after;
        after.left=end;
        end=after;
    }
    //插入正数(第三声)的第几个
    public void addExact(int n,Node2 no)
    {
        int count=0;
        if(n==0)
        {
            addLeft(no);
        }
        else
        {    
            Node2 f=first;
            while(true)
            {
                f=f.right;
                count++;
                if(count==n)
                {
                    //此处为四个指针的指向的变化
                    no.left=f.left;
                    f.left.right=no;
    //                first.left=no;
                    no.right=f;
                    f.left=no;
                    break;
                }
    
            }
        }
    }
    //插入倒数的第几个
    public void addExact2(int n,Node2 no)
    {
        int count=0;
        if(n==0)
        {
            addRight(no);
        }
        else
        {
            Node2 f=end;
            while(true)
            {
                f=f.left;
                count++;
                if(count==n)
                {
                    
                    no.left=f;
                    no.right=f.right;
                    f.right.left=no;
                    f.right=no;
                    break;
                    
                }
            }
        }
    }
    //正序遍历
    public void print()
    {
        System.out.println(first.data);
        while(first.right!=null)
        {
            System.out.println(first.right.data);
            first=first.right;
        }
//        System.out.println(end.data);
    }
    //倒序遍历
    public void print2()
    {
        System.out.println(end.data);
        while(end.left!=null)
        {
            System.out.println(end.left.data);
            end=end.left;
        }
    }
    

}
/*值得注意的是，每一次插入一个新的对象的时候，需要注意指针指向的改变。
首先是这个新的对象两边的指向（左和右），其次是时左边的对象向右的指向
和右边对象向左的指向。
这四个指针的指向必须正确，否则可能导致正序或者倒序遍历无法实现。
*/
/*对比单链表，单链表只能从一个方向遍历，因为只有一个头，而双向链表，有头和尾，可以从
 * 头遍历，也可以从尾遍历，而且其中一个对象因为有两个方向的指针，所以他可以获得左边的
 * 对象也可以获得右边的对象。
 * 但是单链表的话，因为只有一个方向，所以只能向左或右。添加对象的时候，双向也可以从头添加，也可以从尾添加。
 * 如果单链表要实现两个方向添加比较难得，或者说不行，因为他只有向左或向右的一个方向的指针
 * 而双向链表每个对象都有两个方向的指针没这样更灵活，但是这同样有缺点，因为这样的话每个对象
 * 都会包含两个指针，这同样内存会消耗更多。
 * 
 * */