Java有序雙向鏈表怎么實(shí)現(xiàn)

142次閱讀

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

要實(shí)現(xiàn)一個(gè)有序雙向鏈表，可以按照以下步驟進(jìn)行：

定義一個(gè)節(jié)點(diǎn)類，包含三個(gè)屬性：前一個(gè)節(jié)點(diǎn)的引用、節(jié)點(diǎn)的值和后一個(gè)節(jié)點(diǎn)的引用。

class Node {
    Node prev;
    int value;
    Node next;
}

定義一個(gè)有序雙向鏈表類，包含兩個(gè)屬性：鏈表的頭節(jié)點(diǎn)和鏈表的尾節(jié)點(diǎn)。

class SortedDoublyLinkedList {
    Node head;
    Node tail;
}

實(shí)現(xiàn)有序雙向鏈表類的插入方法，用于將一個(gè)元素按照順序插入到鏈表中。首先判斷鏈表是否為空，如果為空，則將新節(jié)點(diǎn)作為頭節(jié)點(diǎn)和尾節(jié)點(diǎn)。如果不為空，則從頭節(jié)點(diǎn)開始遍歷鏈表，找到合適的位置插入新節(jié)點(diǎn)。

void insert(int value) {Node newNode = new Node();
    newNode.value = value;
    
    if (head == null) {
        head = newNode;
        tail = newNode;
    } else {Node current = head;
        while (current != null && current.value < value) {current = current.next;}
        
        if (current == head) {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        } else if (current == null) {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        } else {
            newNode.prev = current.prev;
            newNode.next = current;
            current.prev.next = newNode;
            current.prev = newNode;
        }
    }
}

實(shí)現(xiàn)有序雙向鏈表類的刪除方法，用于刪除指定值的節(jié)點(diǎn)。首先判斷鏈表是否為空，如果為空，則直接返回。如果不為空，則從頭節(jié)點(diǎn)開始遍歷鏈表，找到第一個(gè)值等于指定值的節(jié)點(diǎn)，并刪除它。

void remove(int value) {if (head == null) {return;
    }
    
    Node current = head;
    while (current != null && current.value != value) {current = current.next;}
    
    if (current == head) {
        head = head.next;
        if (head != null) {head.prev = null;
        } else {tail = null;
        }
    } else if (current == tail) {
        tail = tail.prev;
        tail.next = null;
    } else {
        current.prev.next = current.next;
        current.next.prev = current.prev;
    }
}