Comment implémenter une liste doublement chaînée en Java

1. Liste doublement chaînée

1.1 Chaque nœud de la liste doublement chaînée contient des données de nœud, le nœud précédent (pré), le nœud suivant (suivant)

1.2 Structure des nœuds de liste doublement chaînée

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

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

    }

2.Ajout, suppression, modification et vérification de liste doublement chaînée (crud)

2.1 Ajout, suppression, modification et vérification de liste doublement chaînée. 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 Classe de test (fonction d'entrée principale)

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 Certaines lacunes doivent être modifiées

1). l'avant-dernier nœud, donc une variété de problèmes différents doivent être pris en compte, suppression du nœud de tête, suppression du nœud de queue, etc., ce qui entraîne beaucoup de complexité dans la fonction de suppression
2), il y a des modifications dans le contient la fonction pour boucler jusqu'au dernier nœud
3), et modifications ultérieures de la fonction de suppression Opération vide (à compléter)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!