双向链表

双向链表应用实例,双向链表的操作分析和实现

管理单向链表的缺点分析:

1. 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
2. 向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除 时节点，总是找到 temp,temp 是待删除节点的前一个节点(认真体会).
3. 分析了双向链表如何完成遍历，添加，修改和删除的思路
   双向链表实现思路

分析 双向链表的遍历，添加，修改，删除的操作思路===》代码实现

1. 遍历 方和 单链表一样，只是可以向前，也可以向后查找

2. 添加 (默认添加到双向链表的最后)

3. (1) 先找到双向链表的最后这个节点

4. (2) temp.next = newHeroNode

5. newHeroNode.pre = temp;

6. 修改 思路和 原来的单向链表一样. 4) 删除

(1) 因为是双向链表，因此，我们可以实现自我删除某个节点

(2) 直接找到要删除的这个节点，比如 temp

(3) temp.pre.next = temp.next

(4) temp.next.pre = temp.pre;
实现链表节点

/** * 双向链表要用的节点 * */
class ListNode {
    //排名
    public int No;
    // 姓名
    public String Name;
    //昵称
    public String NickName;
    // 下一个节点
    public ListNode next;
    //上一个节点
    public ListNode pre;

    public ListNode(int hNo, String hName, String hNickName) {
        this.No = hNo;
        this.Name = hName;
        this.NickName = hNickName;
    }

    //方便输出语句输出
    @Override
    public String toString() {
        return "HeroNode{" +
                "No=" + No +
                ", Name='" + Name + '\'' +
                ", NickName='" + NickName + '\'' +
                '}';
    }
}

双向链表实现

class DoubleLinkedList {
    //创建一个头结点
    ListNode head = new ListNode(0, "", "");

    public ListNode getHead() {
        return head;
    }

    public void setHead(ListNode head) {
        this.head = head;
    }

    //遍历链表
    public void List() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //头节点不能动 这里我们用一个临时指针来记录
        ListNode temp = head.next;
        while (true) {
            //遍历为空就代表找了最后一个节点
            if (temp == null) {
                break;
            }
            //输出节点
            System.out.println(temp);
            //后移一位
            temp = temp.next;
        }
    }

    //加入双向链表
    public void add(ListNode node) {
        //头节点不能动 这里我们用一个临时指针来记录
        ListNode temp = head;
        //遍历链表
        while (true) {
            //遍历为空就代表找了最后一个节点
            //不为空就后移一位继续找
            if (temp.next == null) {
                break;
            }
            //没有找到最后就后移 temp
            temp = temp.next;
        }
        //指向下一个节点
        temp.next = node;
        //指向上一个节点
        node.pre = temp;
    }

    //修改双向链表，和单向链表基本一致不需要过多的修改
    //修改节点信息
    public void updateNode(ListNode newlistnode) {
        if (head.next == null) {
            System.out.println("链表是空的");
        }
        //这里是头节点不能修改，我用 temp 来指向头结点
        ListNode temp = head.next;
        // 是否找到了no的标识
        boolean flag = false;
        while (true) {
            //找到最后一个
            if (temp == null) {
                break;
            }
            if (temp.No == newlistnode.No) {
                //如果等于 那么代表可以修改
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            // true 修改信息
            temp.NickName = newlistnode.NickName;
            temp.Name = newlistnode.Name;
        } else {
            System.out.printf("没有找到 %d 这个节点", newlistnode.No);
        }
    }

    /* * 双向链表删除 * 对于双向链表来说就不需要找到上一个节点来删除了， * 可以找到自己删除 * */
    public void DeleteNode(int no) {
        if (head.next == null) {
            System.out.println("链表为空 不需要删除");
            return;
        }
        ListNode temp = head.next;
        // 用来标注 是不是可以删除
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.next.No == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag 删除Node
        if (flag) {
            //找到的话就删除，这里我们只需要指向空 GC会回收
            //temp.next = temp.next.next; 原先的单向链表删除现在在双向链表里就不好使了
            /*将当前节点的上一个节点的下一个指向 指向当前节点的下一个节点 相当于向前指向的next 直接跨过当前的节点指向下一个节点*/
            temp.pre.next = temp.next;
            /*将当前节点的下一个节点的上一个指向 指向当前节点的上一个节点，相当于向前的pre 直接快过当前的节点指向上一个 * 如果当前节点是最后一节点，就不执行后面这个将下一个节点的指向更改，不然会出现空指针 * */
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }
            /*这两步 坐完相当于 此时的当前节点已经没有了指向 会被回收*/
        } else {
            System.out.printf("要删除的 %d 没有找到", no);
        }
    }
}

效果

总结

双向链表在之前的基础上：

1. 对比单向链表 双向链表可以自己删除，
2. 双线链表正反遍历更加的容易