/*
 * 不带头节点的
 */
public class Doublelinkedlist<T> {
    class node<T> {
        T data;
        node<T> pre;
        node<T> next;

        public node() {
        }

        public node(T data) {
            this.data = data;
        }
    }

    private node<T> head;// 头节点
    private node<T> tail;// 尾节点
    private int length;

    public Doublelinkedlist() {
        head = null;
        tail = head;
        length = 0;
    }

    boolean isEmpty() {
        return length == 0 ? true : false;
    }

    void addFirst(T data) {
        node<T> teamNode = new node(data);
        if (isEmpty()) {
            head = teamNode;
            tail = teamNode;

        } else {
            teamNode.next = head;
            head = teamNode;
        }
        length++;
    }

    void add(T data)// 默认尾节点插入
    {
        node<T> teamNode = new node(data);
        if (isEmpty()) {
            head = teamNode;
            tail = teamNode;
        } else {
            tail.next = teamNode;
            teamNode.pre = tail;
            tail = teamNode;
        }
        length++;
    }

    int length() {
        return length;
    }

    T getElum(int index)// 为了简单统一从头找
    {
        node<T> team = head;
        for (int i = 0; i < index; i++)// 不带头节点 遍历次数-1
        {
            team = team.next;
        }
        return team.data;
    }

    void add(int index, T data)// 编号插入
    {
        if (index == 0) {
            addFirst(data);
        } else if (index == length) {
            add(data);
        } else {// 重头戏
            node teampre = head;// 为插入的前驱
            // 无头节点，index-1位置找到前驱节点
            for (int i = 0; i < index - 1; i++) {
                teampre = teampre.next;
            }

            node<T> team = new node(data);// a c 中插入B 找打a
            team.next = teampre.next;// B.next=c
            teampre.next.pre = team;// c.pre=B
            team.pre = teampre;// 关联a B
            teampre.next = team;
            length++;
        }
    }

    void deleteFirst()// 头部删除
    {
        if (length == 1)// 只有一个元素
        {
            head = null;
            tail = head;
            length--;
        } else {
            head = head.next;
            length--;
        }
    }

    void deleteLast() {
        if (length == 1) {
            head = null;
            tail = head;
            length--;
        } else {

            tail.pre.next = null;
            tail = tail.pre;
            length--;

        }
    }

    void delete(int index) {
        if (index == 0)
            deleteFirst();
        else if (index == length - 1) {
            deleteLast();
        } else {// 删除 为了理解统一从头找那个节点
            node<T> team = head;
            for (int i = 0; i < index - 1; i++) {
                team = team.next;
            }
            // team 此时为要删除的前节点 a c 插入B a为team
            team.next.next.pre = team;// c的前驱变成a
            team.next = team.next.next;// a的后驱变成c
            length--;
        }
    }

    void set(int index, T data) {
        node<T> team = head;
        for (int i = 0; i < index - 1; i++) {
            team = team.next;
        }
        team.data = data;
    }

    @Override
    public String toString() {
        node<T> team = head;
        String vaString = "";
        while (team != null) {
            vaString += team.data + " ";
            team = team.next;
        }
        return vaString;
    }

    public static void main(String[] args) {
        Doublelinkedlist<Integer> list = new Doublelinkedlist<Integer>();
        list.add(10);
        list.addFirst(20);
        list.add(1, 101);
        list.add(-10);
        list.add(30);
        list.addFirst(40);
        System.out.println(list.toString() + "length " + list.length());
        list.deleteFirst();
        System.out.println(list.toString() + "length " + list.length());
        list.delete(1);
        System.out.println(list.toString() + "length " + list.length());
        list.delete(1);
        System.out.println(list.toString() + "length " + list.length());
        list.deleteLast();
        System.out.println(list.toString() + "length " + list.length());
        list.deleteLast();
        System.out.println(list.toString() + "length " + list.length());
    }
}

40 20 101 10 -10 30 length 6
20 101 10 -10 30 length 5
20 10 -10 30 length 4
20 -10 30 length 3
20 -10 length 2
20 length 1