用Java实现双向链表

Question

用Java实现双向链表，并完成以下操作
1.insertBefore(p,d):将值d插入到列表中p之前的位置，并返回插入数据的位置
2.insertAfter(p, d):将值d插入到列表中p之后的位置，并返回插入数据的位置
3.insertFirst(d):将值d插入到列表的第一个位置，并返回插入数据的位置
4.insertLast(d):将值d插入到列表的最后一个位置，并返回插入数据的位置
5.remove (p):从列表中删除位置p，并返回存储在其中的数据

Answer 1

/**
 * 节点类
 */
class Node{
    public String value;
    public Node next;
    public Node pre;
    //构造器
    public Node(String value) {
        this.value = value;
    }
    @Override
    public String toString() {
        return "DoublePersonNode [value=" + value + "]";
    }
}
/**
 * 链表的关键部分，封装了增删改查的方法类
 */
class DoubleLink{
    //先创建一个头节点
    Node head = new Node("");
    //将值d插入到列表中p之前的位置
    public int insertBefore(Node d, String p) {
        int index = 0;
        //辅助变量
        Node temp = head;
        //遍历到链表的尾部
        while(true) {
            if(p.equals(temp.next.value)) {
                //temp已经找到了要插入的位置
                break;
            }
            //后移
            temp = temp.next;
            index ++;
        }
        //开始加入节点
        d.next = temp.next;
        temp.next.pre = d;
        temp.next = d;
        d.pre = temp;
        return index;
    }
    //将值d插入到列表中p之后的位置
    public int insertAfter(Node d, String p) {
        int index = 0;
        //需要一个临时变量
        Node temp = head;
        //遍历到链表的尾部
        while(true) {
            if(p.equals(temp.value)) {
                //temp已经找到了要插入的位置
                break;
            }
            //后移
            temp = temp.next;
            index ++;
        }
        //开始加入节点
        temp.next = d;
        d.pre = temp;
        return index;
    }
    
    //增加在链表第一个位置
    public int insertFirst(Node d) {
        if(head.next != null) {
            head.next.pre = d;
            d.next = head.next;
            head.next = d;
            d.pre = head;
        }else {
            head.next = d;
            d.pre = head;
        }    
        return 0;
    }
    
    //增加在链表最后一个位置
    public int insertLast(Node d) {
        int index = 0;
        //需要一个临时变量
        Node temp = head;
        //遍历到链表的尾部
        while(true) {
            if(temp.next == null) {
                //temp已经指到链表尾部
                break;
            }
            //后移
            temp = temp.next;
            index ++;
        }
        //开始加入节点
        temp.next = d;
        d.pre = temp;
        return index;
    }
    //删除位置p的节点
    public String remove(int p) {
        int index = 0;
        //需要一个临时变量
        Node temp = head.next;
        //需要一个变量来判断是否找到删除的位置
        boolean flag = false;
        for(int i=0; i<p; i++) {
            temp = temp.next;
        }
        temp.pre.next = temp.next;
        if(temp.next != null) {
            temp.next.pre = temp.pre;
        }
        return temp.value;
    }
    //查询显示节点
    public void show() {
        if(head.next == null) {
            //为空提示
            System.out.println("链表为空");
        }else {
            //需要一个临时变量
            Node temp = head.next;
            while(true) {
                if(temp == null) {
                    break;
                }
                //输出
                System.out.print(temp);
                //后移
                temp = temp.next;
            }
        }
    }
    //测试运行
    public static void main(String args[]) {
        DoubleLink doubleLink = new DoubleLink();
        int aIndex = doubleLink.insertFirst(new Node("a"));
        System.out.println("在第"+ aIndex +"个位置插入一个节点");
        int bIndex = doubleLink.insertAfter(new Node("b"), "a");
        System.out.println("在第"+ bIndex +"个位置插入一个节点");
        int cIndex = doubleLink.insertBefore(new Node("c"), "b");
        System.out.println("在第"+ cIndex +"个位置插入一个节点");
        int dIndex = doubleLink.insertLast(new Node("d"));
        System.out.println("在第"+ dIndex +"个位置插入一个节点");
        String removeValue = doubleLink.remove(3);
        System.out.println("删除的节点值为：" + removeValue);
        doubleLink.show();
    }
}