今天复习到双链表了。

今天看了《你的名字》，棒棒的，推荐推荐~
不过为什么陨石总是会落在坑里呢？
先不想这么复杂的问题了，来看双链表。

双链表就是在单链表的基础上作出了一点小小的改进，单链表每个节点都有一个指针变量指向下一个节点，而双链表则多了一个指针变量，指向上一节点。
此外还多了一个尾节点，指向最后一个变量。
这样的好处是查询的时候既可以从头到尾也可以从尾到头，最显而易见比如尾插法就不需要while循环到最后一个节点才能插入了。

---

Java代码实现

依旧是

国际惯例

public class DoubleLinkedList{
    public static void main(String[] args){

    }
}

这次的Data类比上次多了一个名为last的属性，用于指向上一节点。

private class Data{
    int num;
    Data last = null; // 用于存放前一个变量
    Data next = null;
    public Data(int num){
        this.num = num;
    }
}

然后给DoubleLinkedList类创建成员变量head和tail，在构造函数中让它们互相连接，形成一个空的双链表。

空的双链表

// 构造函数
// 初始化链表时头尾节点相互连接
public DoubleLinkedList(){
    this.head.next = this.tail;
    this.tail.last = this.head;
}
Data head = new Data(0);
Data tail = new Data(0);

补充一下基本知识，所谓构造函数就是在使用类创建对象的时候一定会运行的函数，用于对象的初始化。
在main函数中创建链表的时候，一定会执行上面那个构造函数的方法，然后把头尾节点相互连在一起。

节点插入

//  插入新节点..头插法和尾插法
public void insertP(int num){
    Data data = new Data(num);
    head.next.last = data;
    data.next = head.next;
    data.last = head;
    head.next = data;
}

public void insertE(int num){
    Data data = new Data(num);
    tail.last.next = data;
    data.last = tail.last;
    data.next = tail;
    tail.last = data;
}

节点删除

//  从头部或尾部删除一个节点
public void deleteP(){
    // 当且仅当链表不为空的时候删除节点，下同
    if(head.next != tail){
        head.next.next.last = head;
        head.next = head.next.next;
    }
}

public void deleteE(){
    if(tail.last != head){
        tail.last.last.next = tail;
        tail.last = tail.last.last;
    }
}

//  删除第一个匹配成功的节点（从头开始）
public void removeOne(int num){
    Data cur = head.next;
    while(cur != tail){
        if(cur.num == num){
            cur.last.next = cur.next;
            cur.next.last = cur.last;
            return; // 直接返回，不再判断后面有没有符合要求的
        }
        cur = cur.next;
    }
}

//  删除所有符合要求的节点
public void remove(int num){
    Data cur = head.next;
    while(cur != tail){
        if(cur.num == num){
            cur.last.next = cur.next;
            cur.next.last = cur.last;
        }
        cur = cur.next;
    }
}

节点查找

//  查找结点
public Object find(int num){
    Data cur = head.next;
    while(cur != tail){
        if(cur.num == num){
            return cur.num;
        }
        cur = cur.next;
    }

    System.out.println("并没有找到元素 "+num);
    return null;
}

打印链表

然后还需要一个打印链表的方法

//  打印链表内容
public void display(){
    Data cur = head.next;
    while(cur != tail){
        System.out.print(cur.num + "   ");
        cur = cur.next;
    }
    System.out.println("\n");
}

测试环节

然后就完成啦，测试一下吧~
在main方法里通过DoubleLinkedList dll = new DoubleLinkedList();就可以创建一个空的双链表，然后可以进行各种操作。

public static void main(String[] args){
    DoubleLinkedList dll = new DoubleLinkedList();
    System.out.println("尾插法插入 5 6 7 8 9");
    dll.insertE(5);
    dll.insertE(6);
    dll.insertE(7);
    dll.insertE(8);
    dll.insertE(9);
    dll.display();
    System.out.println("头插法插入 5 6 7 8 9");
    dll.insertP(5);
    dll.insertP(6);
    dll.insertP(7);
    dll.insertP(8);
    dll.insertP(9);
    dll.display();
    System.out.println("从尾部删除节点");
    dll.deleteE();
    dll.display();
    System.out.println("从头部删除两个节点");
    dll.deleteP();
    dll.deleteP();
    dll.display();
    System.out.println("删除一个 5");
    dll.removeOne(5);
    dll.display();
    System.out.println("删除所有 6");
    dll.remove(6);
    dll.display();
    if(dll.find(9)!=null) System.out.println(dll.find(9) + " 被找到");
    if(dll.find(7)!=null) System.out.println(dll.find(7) + " 被找到");
}

输出结果

尾插法插入 5 6 7 8 9 5 6 7 8 9

头插法插入 5 6 7 8 9 9 8 7 6 5 5 6 7 8 9

从尾部删除节点 9 8 7 6 5 5 6 7 8

从头部删除两个节点 7 6 5 5 6 7 8

删除一个 5 7 6 5 6 7 8

删除所有 6 7 5 7 8

并没有找到元素 9 7 被找到

到这里，单链表的基础功能就实现了~真是令人愉悦呢。

这里是CATT-L，在现代魔法的道路中上下求索着。

以上 : )

---

完整代码

public class DoubleLinkedList{


    private class Data{
        int num;
        Data last = null; // 用于存放前一个变量
        Data next = null;
        public Data(int num){
            this.num = num;
        }
    }

    // 构造函数
    // 初始化链表时头尾节点相互连接
    public DoubleLinkedList(){
        this.head.next = this.tail;
        this.tail.last = this.head;
    }
    Data head = new Data(0);
    Data tail = new Data(0);

    //  插入新节点..头插法和尾插法
    public void insertP(int num){
        Data data = new Data(num);
        head.next.last = data;
        data.next = head.next;
        data.last = head;
        head.next = data;
    }

    public void insertE(int num){
        Data data = new Data(num);
        tail.last.next = data;
        data.last = tail.last;
        data.next = tail;
        tail.last = data;
    }

    //  从头部或尾部删除一个节点
    public void deleteP(){
        // 当且仅当链表不为空的时候删除节点，下同
        if(head.next != tail){
            head.next.next.last = head;
            head.next = head.next.next;
        }
    }

    public void deleteE(){
        if(tail.last != head){
            tail.last.last.next = tail;
            tail.last = tail.last.last;
        }
    }

    //  删除第一个匹配成功的节点（从头开始）
    public void removeOne(int num){
        Data cur = head.next;
        while(cur != tail){
            if(cur.num == num){
                cur.last.next = cur.next;
                cur.next.last = cur.last;
                return; // 直接返回，不再判断后面有没有符合要求的
            }
            cur = cur.next;
        }
    }

    //  删除所有符合要求的节点
    public void remove(int num){
        Data cur = head.next;
        while(cur != tail){
            if(cur.num == num){
                cur.last.next = cur.next;
                cur.next.last = cur.last;
            }
            cur = cur.next;
        }
    }

    //  查找结点
    public Object find(int num){
        Data cur = head.next;
        while(cur != tail){
            if(cur.num == num){
                return cur.num;
            }
            cur = cur.next;
        }

        System.out.println("并没有找到元素 "+num);
        return null;
    }

    //  打印链表内容
    public void display(){
        Data cur = head.next;
        while(cur != tail){
            System.out.print(cur.num + "   ");
            cur = cur.next;
        }
        System.out.println("\n");
    }

    public static void main(String[] args){
        DoubleLinkedList dll = new DoubleLinkedList();
        System.out.println("尾插法插入 5 6 7 8 9");
        dll.insertE(5);
        dll.insertE(6);
        dll.insertE(7);
        dll.insertE(8);
        dll.insertE(9);
        dll.display();
        System.out.println("头插法插入 5 6 7 8 9");
        dll.insertP(5);
        dll.insertP(6);
        dll.insertP(7);
        dll.insertP(8);
        dll.insertP(9);
        dll.display();
        System.out.println("从尾部删除节点");
        dll.deleteE();
        dll.display();
        System.out.println("从头部删除两个节点");
        dll.deleteP();
        dll.deleteP();
        dll.display();
        System.out.println("删除一个 5");
        dll.removeOne(5);
        dll.display();
        System.out.println("删除所有 6");
        dll.remove(6);
        dll.display();
        if(dll.find(9)!=null) System.out.println(dll.find(9) + " 被找到");
        if(dll.find(7)!=null) System.out.println(dll.find(7) + " 被找到");
    }
}