How to implement a doubly linked list in Java

1. Doubly linked list

1.1 Each node of the doubly linked list contains node data, the previous node (pre), the next node (next)

1.2 Doubly linked list node structure

class Node {
//节点数据data
        int data;
        Node pre;
        Node next;

        public Node(int data) {
            this.data = data;
        }
        public Node() {
            super();
        }
        

    }

2. Addition, deletion, modification and check of doubly linked list (crud)

2.1 Addition, deletion and modification check of doubly linked list

public class DoubleLinkedList {
    private Node first;
    private Node current;

    private static class Node {

        int data;
        Node pre;
        Node next;

        public Node(int data) {
            super();
            this.data = data;
        }

        public Node() {
            super();
        }
        

    }

    public DoubleLinkedList() {
        super();
    }

    /**
     * 双向链表增加
     */
    public void add(int val) {
        // 如果是头结点
        if (first == null) {
            Node node = new Node(val);
            first = node;
            first.pre = null;
            first.next = null;
            current = first;
        } else {
            Node node = new Node(val);
            current.next = node;
            node.pre = current;
            current = node;
        }
    }

    /**
     * 双向链表的删除 删除所有值为val的元素
     */
    public void del(int val) {
        if (first == null) {
            System.out.println("双向链表为空，无法进行删除操作！");
        } else {
            
            Node node = first;
            while(true) {
                // 首节点的删除可能
                if (node.data == val) {
                    //如果只有一个节点
                    if(node.next==null) {
                        node=null;
                        first=null;
                        System.out.println("删除所有的"+val+"成功");
                        return;
                    }else {
                        node = node.next;
                        node.pre.next=null;
                        node.pre=null;
                        first=node;
                        //删除后重新循环判断首节点是否值相等
                        continue;
                    }
                
                    
                } else {
                    
                    while (node.next != null) {
                        if (node.data == val) {
                            node.pre.next = node.next;
                            node.next.pre = node.pre;
                            Node tempNode = node.pre;
                            node.pre=null;
                            node.next=null;
                            node = tempNode;
                        }
                        node = node.next;
                    }
                    // 末节点删除可能
                    if (node.data == val) {
                        node.pre.next=null;
                        node.pre=null;

                    }
                    System.out.println("删除所有的"+val+"成功");
                    //末节点判断完成后，结束循环
                    return;
                }
            }
        }

    }
    /**
     * 遍历双向链表操作
     */
    public void traverse() {
        if(first==null) {
            System.out.println("双向链表为空");
        }else {
            Node node = first;
            //循环遍历到倒数第二个节点截止
            while(node.next!=null) {
                System.out.print(node.data+" ");
                node=node.next;
            }
            //遍历最后一个节点
            System.out.print(node.data);
        }
    }
    /**
     * 双向链表插入操作,在所有值为value的后面插入一个数insert
     */
    public void insert(int value,int insert) {
        
        if(first==null) {
            System.out.println("双向链表为空，无法插入");
        }else {
            Node node = first;
            //循环遍历到倒数第二个节点截止
            while(node.next!=null) {
                if(node.data==value) {
                    Node insertNode = new Node(insert);
                    node.next.pre = insertNode;
                    insertNode.next = node.next;
                    node.next = insertNode;
                    insertNode.pre = node;
                }
                node=node.next;
            }
            //最后一个节点后插入
            if(node.data == value) {
                Node insertNode = new Node(insert);
                node.next = insertNode;
                insertNode.pre = node;
            }
            System.out.println();
            System.out.println("插入操作完成");
            
        }
    }
    /**
     * 双向链表修改数据,将所有值为val的修改为revised
     */
    public void revise(int val,int revised) {
        if(first==null) {
            System.out.println("双向链表为空，无法修改");
        }else {
            Node node = first;
            while (node.next!=null) {
                if(node.data == val) {
                    node.data = revised;
                }
                node=node.next;
            }
            if(node.data == val) {}
            node.data = revised;
        }
        System.out.println("修改操作完成");
    }
    /**
     * 查找双向链表中是否包含val值
     * @param val
     */
    public void contain(int val) {
        if(first==null) {
            System.out.println("链表为空，无法查找");
        }else {
            Node node = first;
            while(node!=null) {
                if(node.data==val) {
                    System.out.println("该链表中包含"+val+"的值");
                    return;
                }else {
                    node=node.next;
                }
            }
            System.out.println("该链表不包含"+val);
        }
    }

}

2.2 Test class (main entry function)

public class Main {
    public static void main(String[] args) {
        DoubleLinkedList list = new DoubleLinkedList();

        list.add(1);
        list.add(1);
        list.add(2);
        list.insert(1, 3);
        list.add(2);
        list.add(3);
        list.traverse();
        System.out.println();
        list.del(1);
    
        list.traverse();
        list.add(4);
        System.out.println();
        list.traverse();
        System.out.println();
        list.contain(4);
        
        list.contain(3);
        list.contain(0);

    }
}

3. Some shortcomings need to be modified

1). The loop ends at the penultimate node. A variety of different situations must be considered, such as deletion of the head node, deletion of the tail node, etc., resulting in the deletion of the function. It’s a lot more complicated
2), there are modifications in the contain function to loop to the last node
3), and subsequent modifications to the delete function should be done when you have time (to be completed)

The above is the detailed content of How to implement a doubly linked list in Java. For more information, please follow other related articles on the PHP Chinese website!