基於Java實現雙向連結串列

public class DoubleLinkedList {
     //建立頭結點。表示連結串列的頭
    private Node Head=new Node(0,"","");
    
    //返回頭結點
    public Node getHead() {
        return Head;
    }
    //AddNode1:新增節點到單連結串列的尾部
    //思路：當不考慮節點順序
    //1、找到連結串列的最後一個節點
    //2、將最後這個節點的Next指向新節點
    public void AddNode1(Node node) {
        //因為頭節點不能動，所以需要一個輔助節點遍歷
        Node temp=Head;
        while(true) {
            //找到連結串列的最後一個節點
            if(temp.next==null) {
                break;
            }
            //否則temp=temp的下一個節點
            temp=temp.next;
            
        }
        //迴圈出來之後，temp是最後一個節點
        temp.next=node;
        node.pre=temp;
    }
    
    //AddNode2:新增節點，按順序
    public void AddNode2(Node node) {
        //因為頭結點不能動，所以需要一個輔助節點遍歷，找到新增新節點的位置
        Node temp=Head;
        boolean flag=false; //用於標識連結串列中是否已經存在新節點的順序
        while(true) {
            //如果該節點是最後一個節點，則新節點新增到最後一個位置
            if(temp.next==null) {
                break;
            }else if(temp.next.number>node.number) { //說明找到了新增新節點的位置
                break;
            }else if(temp.next.number==node.number) { //說明新節點的順序已經存在在連結串列中
                flag=true;
            }
            temp=temp.next;
        }
        if(flag) {
            System.out.println("該節點的順序已經存在，插入失敗");
        }else {
            //則說明新節點在連結串列中不存在，插入新節點
            //新節點的下一個節點=輔助節點的下一個節點
            node.next=temp.next;
            if(temp.next!=null) {   //如果temp的下一個節點不為空，則temp的下一個節點的前一個節點為新節點
                temp.next.pre=node;
            }
            //輔助節點的下一個節點=新節點
            temp.next=node;
            //新節點的前一個節點為輔助節點
            node.pre=temp;
        }
        
    }
    
    //刪除節點
    public void remove(Node node) {
        if(Head.next==null) {
            System.out.println("連結串列為空！");
            return;
        }
        //建立輔助節點
        Node temp=Head.next;
        boolean flag=false; //標識是否找到了要刪除的節點
        while(true) {
            if(temp==null) { //遍歷完連結串列了
                break;
            }else if(temp.number==node.number) { //找到要刪除的節點了
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if(flag) { //連結串列中存在要刪除的節點
            
                temp.pre.next=temp.next;    //令temp的前一個節點的下一個節點為temp的後一個節點
                if(temp.next!=null) {       //如果temp不為最後一個節點的話
                    temp.next.pre=temp.pre;    //令temp的下一個節點的前一個節點為temp的前一個節點
                }
            
        }else {
            System.out.printf("不存在編號為%d的節點",node.number);
        }
    }
    
    //修改節點，按照節點的Number來修改
    public void update(Node newNode) {
        if(Head.next==null) {
            System.out.println("連結串列為空！");
            return;
        }
        //建立輔助節點，對連結串列遍歷，知道找到等於修改節點的number的時候
        Node temp=Head.next;
        boolean flag=false; //用來標識是否找到了修改節點的Number
        while(true) {
            if(temp==null) { //則已經遍歷完連結串列
                break;
            }
            if(temp.number==newNode.number) {
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if(flag) {
            temp.name=newNode.name;
            temp.nickName=newNode.nickName;
        }else {
            System.out.printf("沒有找到編號為%d的節點",newNode.number);
        }
    }
    //展示連結串列
    public void show() {
        if(Head.next==null) {
            System.out.println("連結串列為空！");
            return;
        }
        //因為頭節點不能動，所以通過輔助節點遍歷連結串列
        Node temp=Head.next;
        while(true) {
            //判斷是不是最後一個節點
            if(temp.next==null) {
                System.out.println(temp);
                break;
            }
            System.out.println(temp);
            //temp指向下一個節點
            temp=temp.next;
        }
    }

}

//建立節點
class Node{
    public int number;
    public String name;
    public String nickName;
    public Node next; //指向下一個節點
    public Node pre;//指向前一個節點
    //構造器
    public Node(int number,String name,String nickName) {
        this.number=number;
        this.name=name;
        this.nickName=nickName;
        
        
    }

    @Override
    public String toString() {
        return "Node [number=" + number + ", name=" + name + ", nickName=" + nickName + "]";
    }
}

public static void main(String[] args) {
        // TODO 自動生成的方法存根
        Node node1=new Node(1,"宋江","及時雨");
        Node node2=new Node(2,"盧俊義","玉麒麟");
        Node node3=new Node(3,"吳用","智多星");
        Node node4=new Node(4,"林沖","豹子頭");
        Node node5=new Node(4,"linchong","豹子頭");
        //建立一個連結串列
        DoubleLinkedList linkedList=new DoubleLinkedList();
        linkedList.AddNode2(node1);
        linkedList.AddNode2(node3);
        linkedList.AddNode2(node4);
        linkedList.AddNode2(node2);
        linkedList.show();
        
        System.out.println("------------");
        linkedList.remove(node4);
        linkedList.show();
    }