java雙向鏈表怎么實(shí)現(xiàn)

153次閱讀

共計(jì) 1973 個(gè)字符，預(yù)計(jì)需要花費(fèi) 5 分鐘才能閱讀完成。

Java 中的雙向鏈表可以通過(guò)定義一個(gè) Node 類來(lái)實(shí)現(xiàn)，該類包含一個(gè)值和兩個(gè)指針，分別指向前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)。具體實(shí)現(xiàn)如下：

public class DoublyLinkedList {private Node head; // 鏈表頭節(jié)點(diǎn) 
    private Node tail; // 鏈表尾節(jié)點(diǎn) 

    // 節(jié)點(diǎn)類 
    private class Node {private int value;
        private Node prev;
        private Node next;

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

    // 在鏈表末尾添加節(jié)點(diǎn) 
    public void add(int value) {Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
    }

    // 在指定位置插入節(jié)點(diǎn) 
    public void insert(int index, int value) {if (index < 0 || index > size()) {throw new IndexOutOfBoundsException("Invalid index");
        }

        if (index == 0) {Node newNode = new Node(value);
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        } else if (index == size()) {add(value);
        } else {Node cur = head;
            for (int i = 0; i < index; i++) {cur = cur.next;}

            Node newNode = new Node(value);
            newNode.prev = cur.prev;
            newNode.next = cur;
            cur.prev.next = newNode;
            cur.prev = newNode;
        }
    }

    // 刪除指定位置的節(jié)點(diǎn) 
    public void remove(int index) {if (index < 0 || index >= size()) {throw new IndexOutOfBoundsException("Invalid index");
        }

        if (index == 0) {
            head = head.next;
            head.prev = null;
        } else if (index == size() - 1) {
            tail = tail.prev;
            tail.next = null;
        } else {Node cur = head;
            for (int i = 0; i < index; i++) {cur = cur.next;}

            cur.prev.next = cur.next;
            cur.next.prev = cur.prev;
        }
    }

    // 獲取指定位置的節(jié)點(diǎn)值 
    public int get(int index) {if (index < 0 || index >= size()) {throw new IndexOutOfBoundsException("Invalid index");
        }

        Node cur = head;
        for (int i = 0; i < index; i++) {cur = cur.next;}

        return cur.value;
    }

    // 返回鏈表的大小 
    public int size() {int count = 0;
        Node cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
}

使用示例：

public class Main {public static void main(String[] args) {DoublyLinkedList list = new DoublyLinkedList();
        
        list.add(1);
        list.add(2);
        list.add(3);
        
        System.out.println("Size: " + list.size()); // 輸出：Size: 3
        
        list.insert(1, 4);
        
        System.out.println("Size: " + list.size()); // 輸出：Size: 4
        System.out.println("Element at index 1: " + list.get(1)); // 輸出：Element at index 1: 4
        
        list.remove(2);
        
        System.out.println("Size: " + list.size()); // 輸出：Size: 3
        System.out.println("Element at index 2: " + list.get(2)); // 輸出：Element at index 2: 3
    }
}