Java實作雙向連結清單詳細代碼

雙向連結清單有一個頭指針和一個尾指針，分别指向第一個節點和最後一個節點。

Node類：雙向連結清單的節點類

public class Node {
    public int value;
    public Node pre;
    public Node next;

    public Node(){

    }

    public Node(int value){
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}
           

DoubleLinkedList類：雙向連結清單類

public class DoubleLinkedList {
    private Node first;
    private Node last;
    private int size;

    public int getSize() {
        return size;
    }

    public Node getFirst() {
        return first;
    }

    public Node getLast() {
        return last;
    }

    public boolean isEmpty(){
        return first == null;
    }

    //頭插法
    public void addFirst(Node node){
        if(isEmpty()){
            last = node;

        }
        else{
            node.next = first;
            first.pre = node;
        }
        first = node;
        size++;
    }

    //尾插法
    public void addLast(Node node){
        if(isEmpty()){
            first = node;
        }
        else{
            last.next = node;
            node.pre = last;
        }
        last = node;
        size++;
    }

    //在特定節點前插入
    public void addBefore(int value, Node node){
        if(isEmpty()){
            System.out.println("連結清單是空的！");
            return;
        }
        if(first.value == value){
            addFirst(node);
            return;
        }
        Node tmp = first;
        while(tmp.next != null){
            if(tmp.next.value == value){
                node.next = tmp.next;
                node.pre = tmp;
                tmp.next.pre = node;
                tmp.next = node;
                size++;
                return;
            }
            tmp = tmp.next;
        }
        if(last.value == value){
            node.next = last;
            node.pre= last.pre;
            last.pre.next = node;
            last.pre = node;
            size++;
            return;
        }
        System.out.println("沒有特定的節點，添加失敗，請頭插或尾插。");
    }

    //在特定節點後插入
    public void addAfter(int value, Node node){
        if(isEmpty()){
            System.out.println("連結清單是空的！");
            return;
        }
        Node tmp = first;
        while(tmp != null){
            if(tmp.value == value ){
                node.next = tmp.next;
                node.pre = tmp;

                if(tmp.next == null){
                    last = node;
                    tmp.next = node;
                    size++;
                    return;
                }
                tmp.next = node;
                tmp.next.pre = node;
                size++;
                return;
            }
            tmp = tmp.next;
        }
        System.out.println("沒有特定的節點，添加失敗，請頭插或尾插。");
    }

    //頭删
    public void deleteFirst(){
        if(isEmpty()){
            System.out.println("連結清單是空的，删除失敗！");
            return;
        }
        first = first.next;
        if(first == null){
            last = null;
            size--;
            return;
        }
        first.pre = null;
        size--;
    }

    //尾删
    public void deleteLast(){
        if(isEmpty()){
            System.out.println("連結清單是空的，删除失敗！");
            return;
        }
        last = last.pre;
        if(first.next == null){
            first = null;
            size--;
            return;
        }
        last.next = null;
        size--;

    }
    //按值删
    public void deleteByValue(int value){
        if(isEmpty()){
            System.out.println("連結清單是空的，删除失敗！");
            return;
        }
        Node tmp = first;
        while(tmp != null){
            if(tmp.value == value){
                tmp.pre.next = tmp.next;
                if(tmp.next == null){
                    last = tmp.pre;
                    size--;
                    return;
                }
                tmp.next.pre = tmp.pre;
                size--;
                return;
            }
            tmp = tmp.next;
        }
    }

    //列印連結清單
    public void printDoubleLinkedList(){
        Node tmp = first;
        while(tmp != null){
            System.out.println(tmp);
            tmp = tmp.next;
        }
    }
}
           

UseDoubleLinkedList類：測試類

public class UseDoubleLinkedList {
    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(5);
        Node n3 = new Node(3);
        Node n4 = new Node(7);
        System.out.println("===============頭插法");
        DoubleLinkedList dll = new DoubleLinkedList();
        dll.addFirst(n1);
        dll.addFirst(n2);
        dll.addFirst(n3);
        dll.printDoubleLinkedList();
        System.out.println("===============尾插法");
        dll.addLast(n4);
        dll.printDoubleLinkedList();
        System.out.println("===============在特定值以前插入");
        Node n5 = new Node(5);
        dll.addBefore(7, n5);
        dll.printDoubleLinkedList();
//        System.out.println(dll.getLast());
        System.out.println("===============在特定值以後插入");
        Node n6 = new Node(6);
        dll.addAfter(7, n6);
        dll.printDoubleLinkedList();
//        System.out.println(dll.getLast());
        System.out.println("===============頭删");
        dll.deleteFirst();
        dll.printDoubleLinkedList();
//        System.out.println(dll.getLast());
        System.out.println("===============尾删");
        dll.deleteLast();
        dll.printDoubleLinkedList();
        System.out.println("===============按值删");
        dll.deleteByValue(1);
        dll.printDoubleLinkedList();
    }
}
           

歡迎讨論。