Javaで二重リンクリストを実装する方法

1. 二重リンクリスト

1.1 二重リンクリストの各ノードにはノードデータ、前のノード (pre)、次のノード (next) が含まれます

1.2 二重リンクリストのノード構造

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

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

    }

2. 二重リンクリスト(crud)の追加・削除・変更・チェック

2.1 二重リンクリストの追加・削除・変更チェック

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 テストclass (メインエントリ関数)

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. いくつかの欠点を修正する必要があります

1). ループは最後から 2 番目のノードで終了します. 削除などのさまざまな状況を考慮する必要がありますヘッド ノードの削除、テール ノードの削除など、結果として関数が削除されます。これははるかに複雑です
2)、最後のノードにループするためのcontain関数に変更があります
3 )、その後の削除関数の変更は時間があるときに行う必要があります (完了予定)

以上がJavaで二重リンクリストを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。