Java のネイティブな順序付き双方向連結リストの実装方法

2年 ago
芽依, 雨夜
1 minute

ソートされた両方向連結リストを実現するには、次の手順に従ってください。

  1. 前ノードへの参照、ノードの値、後ノードへの参照を持つノードクラスを定義。
class Node {
    Node prev;
    int value;
    Node next;
}
  1. 双方向リンクリストのクラスを定義し、2つのプロパティ、リストの先頭ノードとリストの末尾ノードを含みます。
class SortedDoublyLinkedList {
    Node head;
    Node tail;
}
  1. 挿入法を伴う、順番付きの双方向リンクリストクラスを実装する。リストが空かどうかをチェックし、空であれば新しいノードを頭と尾のノードとする。空でない場合、リストに先頭から順に辿り、新しいノードを挿入する適切な位置を探す。
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;
        }
    }
}
  1. 指定された値を持つノードを削除する、順序付き連結リストクラスの削除メソッドを実装します。まず、リストが空かどうかを確認し、空の場合は直接返します。空でない場合は、先頭ノードからリストを走査し、指定された値と同じ値を持つ最初のノードを見つけ、それを削除します。
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;
    }
}

挿入時も削除時も常にソートされた状態を保った、基本的な順序付き双方向リストを実装します。

bannerAds