链表实现系列（二）——双向链表Java实现

双向链表原理见博客：数据结构 | 双向链表简单实现及图示

（注：我采用的是范式实现，如需实现具体链表，只需将Type改为具体类型即可。）

实现的操作包括：

1. 在头节点之前插入节点；
2. 在尾节点之后插入节点；
3. 删除包含指定数据的节点；
4. 删除尾节点；
5. 查找包含指定数据的节点；
6. 获取链表的长度；

辅助操作包括：

1. 清空链表；
2. 判断链表是否为空。

下面是双向链表节点的代码(DoubleNode)

public class DoubleNode<Type> {
    /**
     * data : 节点的数据
     * next : 节点的后继节点
     * prev : 节点的前驱节点
     */
    private Type data;
    private DoubleNode next;
    private DoubleNode prev;

    /**
     * 各种构造方法
     */
    public DoubleNode(){
        this.data = null;
        this.next = null;
        this.prev = null;
    }

    public DoubleNode(Type data){
        this.data = data;
        this.next = null;
        this.prev = null;
    }

    public DoubleNode(Type data, DoubleNode next, DoubleNode prev){
        this.data = data;
        this.next = next;
        this.prev = prev;
    }

    /**
     * 三种属性的 get() 方法
     */
    public Type getData(){
        return this.data;
    }

    public DoubleNode getNext(){
        return this.next;
    }

    public DoubleNode getPrev(){
        return this.prev;
    }

    /**
     * 三种属性的 set() 方法
     */
    public void setData(Type data){
        this.data = data;
    }

    public void setNext(DoubleNode next){
        this.next = next;
    }

    public void setPrev(DoubleNode prev){
        this.prev = prev;
    }
}

下面是双向链表实现的代码(DoubleList)

public class DoubleList<Type> {
    /**
     * 两个属性：头节点 head 和尾节点 tail
     */
    private DoubleNode head;
    private DoubleNode tail;

    /**
     * 三种构造方法
     */
    public DoubleList(){//第一种：空构造方法
        this.head = this.tail = null;
    }

    public DoubleList(DoubleNode node){//第二种：给定一个节点的构造方法
        this.head = this.tail = node;
//        this.head.setNext(this.tail);
//        this.tail.setPrev(this.head);
//        如果这样写，会导致死循环，做成循环链表
    }

    public DoubleList(DoubleNode head, DoubleNode tail){//第三种：给定两个节点的构造方法
        this.head = head;
        this.tail = tail;
        this.head.setNext(this.tail);
        this.tail.setPrev(this.head);
    }

    /**
     * 在头节点之前加入数据
     * @param data：新增节点的数据
     * @return ：插入成功与否
     */
    public boolean addNodeBeforeHead(Type data){
        DoubleNode node = new DoubleNode(data);
        boolean result = true;
        try {
            if (this.head == null) {//链表是空链表，将节点 node 设置为头节点和尾节点
                head = tail = node;
            } else {//链表不是空链表，就把头节点设置为节点 node
                node.setNext(head);//将 node 的后继节点设置为 head
                head.setPrev(node);//将 head 的前驱节点设置为 node
                head = node;//将 head 设置为 node
            }
        }catch (Exception e){
            result = false;
        }
        return result;
    }

    /**
     * 在尾节点之后加入数据
     * @param data：插入的数据
     * @return ：插入成功与否
     */
    public boolean addNodeAfterTail(Type data){
        DoubleNode node = new DoubleNode(data);
        boolean result = true;
        try {
            if (this.tail == null) {//链表是空链表，将节点 node 设置为头节点和尾节点
                this.head = this.tail = node;
            } else {//链表不是空链表，就把头节点设置为节点 node
                node.setPrev(tail);//将 node 的前驱节点设置为 tail
                tail.setNext(node);//将 tail 的后继节点设置为 node
                tail = node;//将 tail 设置为 node
            }
        }catch (Exception e){
            result = false;
        }
        return result;
    }

    /**
     * 根据数据删除节点
     * 遍历时从头节点开始
     * 仅删除离头节点最近的满足要求的节点
     * @param data：需要删除的数据
     * @return ：删除的节点信息
     */
    public int removeNodeByData(Type data){
        int count = 0;
        DoubleNode before = head;
        while ((before != null) && (before.getNext() != null)){
            if (before.getNext().getData().equals(data)){//current 节点的数据即为需要删除的数据
                before.setNext(before.getNext().getNext());
                before.getNext().setPrev(before);
                //这里不用before.getNext().getNext()的原因：已经在语句
                //      before.setNext(before.getNext().getNext());
                //将 before 节点的后继节点设置为了 before.getNext().getNext()，即下下个节点
                return count;
            }else {
                before = before.getNext();
                count++;
            }
        }
        return -1;
    }

    /**
     * 从头节点开始查找数据
     * @param data：需要查找的数据
     * @return 查找到的节点，不存在则返回空
     */
    public int findNodeByDataFromHead(Type data){
        DoubleNode current = head;
        int count = 0;
        while (current != null){
            if (current.getData().equals(data)) //current 节点的数据即为要查找的数据
                return count;
            else {
                current = current.getNext();
                count ++;
            }
        }
        return -1;
    }

    /**
     * 从尾节点开始查找数据
     * @param data ：需要查找的数据
     * @return 查找到的节点，不存在则返回空
     */
    public int findNodeByDataFromTail(Type data){
        DoubleNode current = tail;
        int count = 0;
        while (current != null){
            if (current.getData().equals(data)){
                return count;
            }else {
                current = current.getPrev();
                count++;
            }
        }
        return -1;
    }

    /**
     * 从头节点开始，计算链表的长度（即节点个数）
     * @return 链表长度
     */
    public int getListLength(){
        int length = 0;
        DoubleNode current = head;
        if (head == null)//链表为空
            return -1;
        while (current != null) {
            current = current.getNext();
            length++;
        }
        return length;
    }

    /**
     * 从头节点开始，打印双向链表里的数据
     * 仅用于测试
     */
    public void displayFromHead(){
        DoubleNode current = head;
        System.out.print("    从头节点开始打印：");
        while (current != null){
            System.out.print(" " + current.getData());
            current = current.getNext();
        }
        System.out.println();
    }

    /**
     * 从尾节点开始，打印双向链表里的数据
     * 仅用于测试
     */
    public void displayFromTail(){
        DoubleNode current = tail;
        System.out.print("    从尾节点开始打印：");
        while (current != null){
            System.out.print(" " + current.getData());
            current = current.getPrev();
        }
        System.out.println("\n");
    }

}

下面是测试代码(DoubleTest) 

public class DoubleTest {

    private DoubleList<Integer> list = new DoubleList(new DoubleNode(1));
    private static final int INIT = 5;
    private static final int MULTI = 5;
    private static final String STR = "    ";
    private int data;

    public static void main(String[] args) {
        DoubleTest d = new DoubleTest();
        d.run();
    }

    public void run(){
        testAddNodeBeforeHead();
        testAddNodeAfterTail();
        testRemoveNodeByData();
        testFindNodeByDataFromHead();
        testFindNodeByDataFromTail();
        testGetListLength();
    }

    public void testAddNodeBeforeHead(){
        System.out.println("--初始化双向链表：使用addNodeBeforeHead()方法--");
        System.out.println();
        for (int i = 1; i < INIT; i++) {
            if(!list.addNodeBeforeHead( i*MULTI) )
                System.out.println(STR + "加入数据失败！");
        }
        display();
    }

    public void testAddNodeAfterTail(){
        data = 50;
        System.out.println(STR + "从尾部添加数据：" + data);
        if(!list.addNodeAfterTail( data) )
            System.out.println(STR + "加入数据失败！");
        display();
    }

    public void testRemoveNodeByData(){
        data = 5;
        System.out.println(STR + "删除数据：" + data);
        int loc = list.removeNodeByData(data);
        if (loc == -1){
            System.out.println(STR + "数据：" + data + " 不存在！");
        }else {
            System.out.println(STR + "删除数据成功！数据：" + data + " 位于从头到尾第 " + loc + " 个节点。");
        }
        display();
    }

    public void testFindNodeByDataFromHead(){
        data = 20;
        int loc = list.findNodeByDataFromHead(data);
        if (loc == -1){
            System.out.println("    数据：" + data + " 不存在！");
        }else {
            System.out.println("    数据：" + data + " 位于双向链表从头到尾的第 " + loc + " 个节点。");
        }
        display();
    }

    public void testFindNodeByDataFromTail(){
        data = 20;
        int loc = list.findNodeByDataFromTail(data);
        if (loc == -1){
            System.out.println("    数据：" + data + " 不存在！");
        }else {
            System.out.println("    数据：" + data + " 位于双向链表从尾到头的第 " + loc + " 个节点。");
        }
        display();
    }

    public void testGetListLength(){
        int length = list.getListLength();
        if (length == -1)
            System.out.println(STR + "链表为空！");
        else
            System.out.println(STR + "链表长度为：" + length);
    }

    public void display(){
        list.displayFromHead();
        list.displayFromTail();
    }

}

代码不够规范，还望多多包涵~/bq