カスタム二重リンクリストで無限ループを修正するにはどうすればよいですか？

Question

カスタムLinkedListを作成しましたが、値に基づいてそれを分割するメソッドを作成しようとしています。順序を維持する必要はないので、リストの先頭にxより小さい値を追加し、テールに等しいかそれ以上の値を追加することを考えました。

それにもかかわらず、チェックが行われているときにnode.nextがnullになることはないため、無限ループが発生します。再現する

public class LinkedList<T extends Comparable<T>> { 
    private int size = 0; 
    private Node<T> head = null; 
    private Node<T> tail = null; 

    public int size() { 
     return size; 
    } 

    public boolean isEmpty() { 
     return size == 0; 
    } 

    /** 
    * 
    * @param t the new element to be added at the end of the list 
    *   NOTE: null items are not allowed 
    * 
    * @return true if added 
    */ 
    public boolean add(T t) { 

     if (t == null) { 
      return false; 
     } 
     // if head is null add as head 
     if (head == null) { 
      head = new Node<>(t, null, null); 
      tail = head; 
     } else { 
      Node<T> newTail = new Node<>(t, tail, null); 
      tail.next = newTail; 
      tail = newTail; 
     } 
     size++; 
     return true; 
    } 

    void partition(T value) { 
     Node<T> node = head; 

     while (node != null) { 
      Node<T> prev = node.previous; 
      Node<T> next = node.next; 

      if (node.data.compareTo(value) >= 1) { 
       // should go to tail 
       if (node != tail) { 
        prev.next = node.next; 
        next.previous = node.previous; 

        tail.next = node; 
        node.previous = tail; 
        node.next = null; 
        tail = node; 
       } 

      } else { 
       // should go to head 
       if (node != head) { 
        prev.next = node.next; 
        if (null != next) { 
         next.previous = node.previous; 
        } 

        head.previous = node; 
        node.next = head; 
        head = node; 
       } 
      } 

      node = next; 
     } 

     head.previous = null; 
     tail.next = null; 
    } 

    public T getFirst() { 
     return head.data; 
    } 

    public Node<T> getHead() { 
     return head; 
    } 

    public T getLast() { 
     return tail.data; 
    } 


    private static class Node<T extends Comparable<T>> { 
     T data; 
     Node<T> previous; 
     Node<T> next; 

     Node(T data, Node<T> previous, Node<T> next) { 
      this.data = data; 
      this.previous = previous; 
      this.next = next; 
     } 
    } 

} 

テストケース：ここ

はコードである

import org.testng.annotations.AfterMethod; 
import org.testng.annotations.BeforeMethod; 
import org.testng.annotations.Test; 

import java.util.Arrays; 

import static org.testng.Assert.assertEquals; 
import static org.testng.Assert.assertTrue; 


public class LinkedListTest { 

    private LinkedList<Integer> linkedList; 

    @BeforeMethod 
    public void setUp() { 
     linkedList = new LinkedList<>(); 
    } 

    @Test 
    public void testPartition() { 
     linkedList.add(0); 
     linkedList.add(9); 
     linkedList.add(2); 
     linkedList.add(5); 
     linkedList.add(4); 
     linkedList.add(7); 
     linkedList.add(1); 

     int[] actual = new int[linkedList.size()]; 

     linkedList.partition(5); 

     for (int i = 0; i < linkedList.size(); ++i) { 
      actual[i] = linkedList.get(i); 
     } 

     System.out.println(Arrays.toString(actual)); 
    } 

} 

Answer 1

のは、あなたのリストには二つのアイテムを持っているとしましょう：A-> Bとの両方のAとB>値（いわゆる "尾に行かなければならない "）。コードを開始します。ノードA>の値なので、Aはテールに置かれます。だからあなたのリストはB-> Aであり、Bは「次の」ノードであり、Aは今のテールです。

ループの次の反復では、ノードBを参照します。ノードB>値なので、Bが末尾に置かれます。あなたのリストはA→Bで、Aは「次の」ノードで、Bは今のテールです。明らかにこれは無限ループです。

はこのコードが書かれている方法の精神でこの問題を解決するには、開始前にループがこれを行う：今

last_node = tail; 

を、あなたが持っているだけで前node = next;は、次の操作を行います。では

if(node == last_node) break; 

上記の例では、last_nodeがBを指しています.Bがlast_nodeであるため、ループ処理AとBが終了します。