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 测试类（main入口函数）

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）、在contain函数中有修改到循环到最后一个节点
3）、后续对删除函数修改有空再操作（待完成）