Java實現雙向連結串列

class Node {
//節點資料data
        int data;
        Node pre;
        Node next;

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

    }

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);
        }
    }

}

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);

    }
}