【数据结构与算法】双向链表(添加节点、更新节点、删除节点、打印链表)

1. 单向链表的缺点

前面我们学习了单向链表。虽然有了单向链表，但在解决某些实际问题时，单向链表的执行效率并不高

例如，若实际问题中需要频繁地查找某个节点的前驱节点，使用单向链表存储数据显然没有优势

因为单向链表的强项是从前往后查找目标元素，不擅长从后往前查找元素。所以就有了双向链表

2. 双向链表的介绍

双向链表是一种复杂类型的链表，它的节点包含指向数列中前一个节点和下一个节点的指针

双向链表每个节点包含data域、pre域(指向上一个节点)、next域(指向下一个节点)。所以双向链表可以向前或向后查找

双向链表可以双向遍历，既可以从头遍历到尾，也可以从尾遍历到头，有效解决了单向链表的缺点

实际开发中双向链表应用比单向链表多，但是实现较困难。我们下面来看下双向链表的简单实现

3. 带head头的双向链表实现

实现对双向链表的增加节点、删除节点、修改节点、查询节点操作

双向链表各方法说明：

• add：向双向链表最后添加一个节点。添加方式和单向链表的区别在于，需要将新节点的pre指向双向链表最后的节点
• show：遍历显示链表所有节点的数据。遍历方式和单向链表一样
• update：通过新节点的id，去更新双向链表中对应id的节点的数据。更新方式和单向链表一样
• deleteById：根据id删除双向链表中的节点。和单向链表删除节点相比，除了修改删除节点前一个节点的next，还要修改删除节点后一个节点的pre

双向链表的实现：

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

        // 先创建节点
        Node node1 = new Node(1, "node1");
        Node node2 = new Node(2, "node2");

        // 创建双向链表
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        // 添加节点到双向链表
        doubleLinkedList.add(node1);
        doubleLinkedList.add(node2);

        // 更新id = 2的节点
        Node newNode2 = new Node(2, "newNode2");
        doubleLinkedList.update(newNode2);

        // 删除id = 1的节点
        doubleLinkedList.deleteById(1);

        // 查看双向链表所有节点数据
        doubleLinkedList.show();


    }
}

class DoubleLinkedList {

    // 初始化一个head节点
    private Node headNode = new Node(0, "");


    // 先找到双向链表的最后一个节点(最后一个节点的next为null)，然后将next指向新节点，新节点的pre指向最后一个节点
    public void add(Node node) {
        Node tmpNode = this.headNode;

        while (true) {
            // 如果找到最后一个节点，则添加新节点
            if (tmpNode.next == null) {
                // 形成双向链表
                tmpNode.next = node;
                node.pre = tmpNode;
                break;
            } else {
                // 如果没有找到最后一个节点，则循环处理后面的节点
                tmpNode = tmpNode.next;
            }
        }
    }


    // 通过新节点的id，去更新双向链表中对应id的节点的数据
    public void update(Node node) {

        Node tmpNode = this.headNode;
        while (true) {
            // 如果没有下一个节点，则表示未找到，不能更新
            if (tmpNode.next == null) {
                System.out.println("双向链表没有该节点的id，不能更新");
                break;
                // 如果找到了，则进行更新
            } else if (tmpNode.next.id == node.id) {
                tmpNode.next.name = node.name;
                break;
                // 否则，循环处理下一个节点
            } else {
                tmpNode = tmpNode.next;
            }
        }
    }

    // 根据id删除双向链表中的节点
    public void deleteById(int id) {
        Node tmpNode = this.headNode;
        while (true) {
            // 如果没有下一个节点，则表示为找到要删除的节点
            if (tmpNode.next == null) {
                System.out.println("未找到要删除的节点");
                break;
                // 如果找到要删除的节点，则进行删除
            } else if (tmpNode.next.id == id) {
                //被删除的节点没有被引用，会被自动垃圾回收
                tmpNode.next = tmpNode.next.next;
                // 可能删除的是最后一个节点，此时的tmpNode.next为null
                if (tmpNode.next != null) {
                    tmpNode.next.pre = tmpNode;
                }
                break;
                // 否则，循环处理后面的节点
            } else {
                tmpNode = tmpNode.next;
            }
        }
    }

    // 遍历显示链表的数据
    public void show() {
        if (this.headNode.next == null) {
            System.out.println("链表为空, 不能显示数据");
            return;
        }

        // 定义一个临时变量，指向当前要显示数据的节点
        Node tempNode = this.headNode.next;
        while (true) {
            // 如果为null，则跳出循环
            if (tempNode == null) {
                break;
            } else {
                // 输出当前节点的数据
                System.out.println(tempNode);
                // 然后循环处理后面的节点
                tempNode = tempNode.next;
            }
        }
    }

}


// 每个Node对象就是一个节点
class Node {
    public int id;
    public String name;
    // 指向下一个节点
    public Node next;
    // 指向上一个节点
    public Node pre;

    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node [id = " + id + ", name = " + name + "]";
    }

}

运行程序，结果如下：

Node [id = 2, name = newNode2]