双链表

• 双链表
  • 单链表的缺点分析
  • 实现思路
    • 遍历
    • 添加
    • 修改
    • 删除
  • 代码实现

单链表的缺点分析

1. 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。

2. 单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp，temp是待删除节点的前一个节点

实现思路

遍历

和单链表一样，但是双链表可以向前查找

添加

1. 默认加入到链表的最后
   （1）先找的双向链表的最后节点
   （2）temp.next = newHeroNode
   （3）newHeroNode.pre = temp
2. 按顺序添加节点到链表
   （1）建立辅助指针 temp ，初始位置在链表头节点
   （2）首先遍历找第一个序号比节点序号大的节点前一个结点
   （3）若找到则退出循环，找不到temp指向链表尾部，若找到相同值节点，则退出循环，输出该序号已存在节点。
   （4）将待加入节点的next指向待加入位置上的节点
   （5）将待加入节点的pre指向待加入位置的节点的上个节点
   （6）判断待加入位置的前一个节点是否在链表尾部
   （7）否则将待加入位置的前一个节点next指向待加入节点
   （8）最后将待加入位置的节点的上个节点next指向待加入节点

   doubleLinkedNode.next = temp.next;
   doubleLinkedNode.pre = temp;
   if (temp.next != null) {
         temp.next.pre = doubleLinkedNode;
   }
   temp.next = doubleLinkedNode;

修改

和单链表一样

删除

（1）因为是双向链表，因此可以实现自我删除
（2）直接找到待删除节点temp
（3）temp.pre.next = temp.next
（4）temp.next.pre = temp.pre

代码实现

public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
//        doubleLinkedList.add(new DoubleLinkedNode(1));
//        doubleLinkedList.add(new DoubleLinkedNode(2));
//        doubleLinkedList.add(new DoubleLinkedNode(3));
//        doubleLinkedList.add(new DoubleLinkedNode(4));
        doubleLinkedList.addByOrder(new DoubleLinkedNode(1));
        doubleLinkedList.addByOrder(new DoubleLinkedNode(3));
        doubleLinkedList.addByOrder(new DoubleLinkedNode(2));
        doubleLinkedList.addByOrder(new DoubleLinkedNode(4));
        doubleLinkedList.List();
        doubleLinkedList.del(1);
        System.out.println("删除后");
        doubleLinkedList.List();
    }
}

class DoubleLinkedList {

    // 初始化一个头节点
    private DoubleLinkedNode head = new DoubleLinkedNode(0);

    public DoubleLinkedNode getHead() {
        return head;
    }

    // 遍历
    public void List() {
        // 判断非空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        // 辅助指针
        DoubleLinkedNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

    // 添加（尾插法）
    public void add(DoubleLinkedNode doubleLinkedNode) {
        DoubleLinkedNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = doubleLinkedNode;
        doubleLinkedNode.pre = temp;
    }

    public void addByOrder(DoubleLinkedNode doubleLinkedNode) {
        // 新建辅助指针temp
        DoubleLinkedNode temp = head;
        boolean flag = false; // 标识节点val是否存在
        while (temp.next != null) {
            // 找到第一个比 doubleLinkedNode 大的节点的前一个节点
            if (temp.next.val > doubleLinkedNode.val) {
                break;
            } else if (temp.next.val == doubleLinkedNode.val) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 此时 temp 在待加入位置的前一个节点
        // 或者 没找到第一个比 doubleLinkedNode 大的节点的前一个节点
        // temp 即为最后一个节点
        if (flag) {
            System.out.println("该编号已经存在");
        } else {
            doubleLinkedNode.next = temp.next;
            doubleLinkedNode.pre = temp;
            if (temp.next != null) {
                temp.next.pre = doubleLinkedNode;
            }
            temp.next = doubleLinkedNode;
        }
    }

    // 修改一个节点的内容
    public void update(DoubleLinkedNode doubleLinkedNode) {
        // 判断非空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        DoubleLinkedNode temp = head.next;
        boolean flag = false;
        while (temp != null) {
            if (temp.val == doubleLinkedNode.val) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.val = doubleLinkedNode.val;
        } else {
            System.out.println("没有找到");
        }
    }

    // 删除节点
    public void del(int val) {
        if (head.next == null) {
            System.out.println("链表为空，无法删除");
            return;
        }
        // 辅助指针
        DoubleLinkedNode temp = head.next;
        boolean flag = false;
        while (temp != null) {
            if (temp.val == val) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.pre.next = temp.next;
            // 如果是最后一个节点,就不需要执行下面这句话,否则出现空指针
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }
        } else {
            System.out.println("未找到该节点");
        }

    }
}

class DoubleLinkedNode {
    public int val;
    public DoubleLinkedNode next;
    public DoubleLinkedNode pre;

    public DoubleLinkedNode(int val) {
        this.val = val;
    }

    public DoubleLinkedNode(int val, DoubleLinkedNode next, DoubleLinkedNode pre) {
        this.val = val;
        this.next = next;
        this.pre = pre;
    }

    @Override
    public String toString() {
        return "DoubleLinkedNode{" +
                "val=" + val +
                '}';
    }
}