Java实现双向链表

墨蓝 2024-04-08 08:40 70阅读 0赞

#### 简介(百度百科) ####

> 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

#### 图解 ####

![在这里插入图片描述][8f441d237fa44e2ca0b99aedd5861168.png]

#### 实现思路 ####

*  遍历
    
     *  和单向链表的遍历相同，需要一个辅助节点来保存当前正在遍历的节点
 *  添加
    
     *  双向链表多出了一个frnot，所以在添加时，要让新增节点的front指向链表尾节点
 *  修改
    
     *  和单向链表的修改相同
 *  删除
    
     *  使用temp来保存要删除的节点
     *  temp.pre.next指向temp.next
     *  temp.next指向temp.pre

#### 实现代码 ####

public class Demo {
        
        public static void main(String[] args) {
        
            BidirectionalList bidirectionalList = new BidirectionalList();
            bidirectionalList.addNode(new Node(1,"唱"));
            bidirectionalList.addNode(new Node(2,"跳"));
            bidirectionalList.addNode(new Node(3,"rap"));
            bidirectionalList.addNode(new Node(4,"篮球"));
            bidirectionalList.addNode(new Node(5,"鸡你太美"));
            bidirectionalList.update(new Node(1,"ikun"));
            bidirectionalList.delete(new Node(2,""));
            bidirectionalList.traverseNode();
        }
    }
    
    class BidirectionalList {
        
        /** 创建一个头节点 */
        private Node head = new Node(-1, "");
    
        /**
         * 向链表末尾添加链表节点
         * 当节点的next为空时，说明到达链表的结尾，添加节点
         * @param node
         */
        public void addNode(Node node) {
        
            Node temp = head;
            while (temp.next != null) {
        
                temp = temp.next;
            }
            temp.next = node;
            node.front = temp;
        }
    
        /**
         * 遍历链表
         */
        public void traverseNode(){
        
            Node temp = head;
            while (temp.next != null){
        
                System.out.println(temp.next);
                temp = temp.next;
            }
        }
    
        /**
         * 修改链表
         */
        public void update(Node node){
        
            Node temp = head;
            while (temp.next!=null){
        
                if (temp.next.id == node.id){
        
                    temp.next.name = node.name;
                    return;
                }
                temp = temp.next;
            }
            System.out.println("没有找到id："+node.id+"的节点");
        }
    
        /**
         * 删除节点
         */
        public void delete(Node node){
        
            Node temp = head;
            while (temp.next != null){
        
                if (temp.next.id == node.id){
        
                    temp.next = temp.next.next;
                    temp.next.next.front = temp;
                    return;
                }
                temp = temp.next;
            }
        }
    }
    
    
    class Node {
        
        int id;
        String name;
        Node front;
        Node next;
    
        public Node(int id, String name) {
        
            this.id = id;
            this.name = name;
        }
    
        @Override
        public String toString() {
        
            return "BidirectionalList.Node{" +
                    "id=" + id +
                    ", name='" + name + '\'' +
                    '}';
        }
    }

#### 运行结果 ####

BidirectionalList.Node{
        id=1, name='ikun'}
    BidirectionalList.Node{
        id=3, name='rap'}
    BidirectionalList.Node{
        id=4, name='篮球'}
    BidirectionalList.Node{
        id=5, name='鸡你太美'}

#### 结语 ####

> 发现错误可以直接在评论区指出，一般都能看到的哦，踊跃讨论，才能共同成长！谢谢大家阅读~

[8f441d237fa44e2ca0b99aedd5861168.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/77f373a7c5bb4c7fb43bfa8063824a90.png