[数据结构与算法]2021-10-25

双向链表

双向链表具有三个域，数据域，前驱和后驱

分析双向链表的遍历，添加，修改，删除的操作

1）遍历方法和单链表一样，只是可以向前，也可向后

2）添加（默认添加到最后）

? 1.先找到双向链表的最后节点

? 2.temp.next = newNode

? 3.newNode.pre = temp

3)修改思路和单向链表一样

4）删除

? 1.因为是双向链表，直接可以找到，然后自我删除

? 2.要删除的节点temp.pre.next = temp.next

? 4)temp.next.pre = temp.pre

代码实现：

? 节点类：

package com.cwnu.linkList.node;

public class DoubleNode<E> {
    public int no;
    public E data;
    public DoubleNode<E> next;//指向节点的上一个节点
    public DoubleNode<E> pre;//指向节点的下一个节点

    public DoubleNode(int no, E data) {
        this.no = no;
        this.data = data;
    }

    @Override
    public String toString() {
        return "DoubleNode{" +
                "no=" + no +
                ", data=" + data.toString() +
                '}';
    }
}

? 链表类：

package com.cwnu.linkList.link;

import com.cwnu.linkList.node.DoubleNode;

public class DoubleLinkedList {
    //初始化头节点
    private DoubleNode head = new DoubleNode(0,null);
    //遍历双向链表
    public void list(){
        if (head.next == null){
            System.out.println("链表为空");
        }
        //辅助指针
        DoubleNode temp = head.next;
        while(true){
            if (temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
    //添加节点到链表的末尾
    public void add(DoubleNode newDoubleNode){
        //辅助变量
        DoubleNode temp = head;
        while(true){
            if (temp.next == null){
                temp.next = newDoubleNode;
                newDoubleNode.pre = temp;
                break;
            }
            temp = temp.next;
        }
    }
    //按照序号添加
    public void addByOrder(DoubleNode newDoubleNode){
        //辅助变量
        DoubleNode temp = head;
        boolean flag = false;
        while(true){
            if (temp.next == null && temp.no < newDoubleNode.no){
                temp.next = newDoubleNode;
                newDoubleNode.pre = temp;
                return;
            }
            if (newDoubleNode.no > temp.no && newDoubleNode.no < temp.next.no){
            newDoubleNode.next = temp.next;
            newDoubleNode.pre = temp;
            temp.next.pre = newDoubleNode;
            temp.next = newDoubleNode;
                return;
            }else if (newDoubleNode.no == temp.no){
            System.out.println("已存在，无法添加");
                return;
            }
            temp = temp.next;
        }
    }

    //删除指定节点
    public void delete(int no){
        //声明辅助节点
        DoubleNode temp = head.next;
        if (temp == null){
            System.out.println("链表为空，无法操作");
            return;
        }
        while (true){
            if (temp.next == null && temp.no == no){
                temp.pre.next = null;
                return;
            }else if (temp.next == null && temp.no != no){
                System.out.println("未找到要删除节点");
                return;
            }
            if (temp.no == no){
                temp.next.pre = temp.pre;
                temp.pre.next = temp.next;
                return;
            }
            temp = temp.next;
        }
    }
    //修改节点的数据
    public void updata(DoubleNode newNode){
        //辅助标量
        DoubleNode temp = head.next;
        if (head.next == null){
            System.out.println("链表为空，无法修改");
            return;
        }
        while (true){
            if (temp.no == newNode.no){
                temp.data = newNode.data;
                return;
            }
            if (temp.next == null && temp.no != newNode.no){
                System.out.println("未找到修改的节点");
                return;
            }
            temp = temp.next;
        }
    }
}

? 测试类：

package com.cwnu;

import com.cwnu.linkList.data.Hero;
import com.cwnu.linkList.data.Student;
import com.cwnu.linkList.link.DoubleLinkedList;
import com.cwnu.linkList.node.DoubleNode;
import org.junit.Test;

public class DoubleLinkListTest {
    @Test
    public void test01(){
        //创建一个节点
        DoubleNode<Hero> node1 = new DoubleNode<>(1,new Hero(1,"林冲","豹子头"));
        DoubleNode<Hero> node2 = new DoubleNode<>(2,new Hero(2,"林冲","豹子头"));
        DoubleNode<Hero> node3 = new DoubleNode<>(3,new Hero(3,"林冲","豹子头"));
        DoubleNode<Hero> node4 = new DoubleNode<>(4,new Hero(4,"林冲","豹子头"));
        DoubleNode<Student> node5 = new DoubleNode<>(5,new Student(1,"孙波","2019133",20));
        DoubleNode<String> node6 = new DoubleNode<>(6,"555555" );
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        System.out.println("添加之前：");
        doubleLinkedList.list();
        /*doubleLinkedList.add(node1);
        doubleLinkedList.add(node2);
        doubleLinkedList.add(node3);
        doubleLinkedList.add(node4);
        doubleLinkedList.add(node5);*/
        doubleLinkedList.addByOrder(node3);
        doubleLinkedList.addByOrder(node1);
        doubleLinkedList.addByOrder(node2);
        doubleLinkedList.addByOrder(node5);
        doubleLinkedList.addByOrder(node4);
        doubleLinkedList.addByOrder(node6);
        System.out.println("添加之后：");
        doubleLinkedList.list();
        System.out.println("删除之后：");
        doubleLinkedList.delete(7);
        doubleLinkedList.list();
        System.out.println("修改之后：");
        DoubleNode<Hero> newNode = new DoubleNode<>(7,new Hero(3,"武松","行者"));
        doubleLinkedList.updata(newNode);
        doubleLinkedList.list();
    }
}