Javaで循環リンクリストを実装する方法は？

Question

「データ構造とアルゴリズム」に関する本を読んで、循環リンクリストの実装を求める割り当てがあります。これは学習の練習であり、私のコードは非常に高いレベルのものではないかもしれません。

私の循環リンクリストの実装の主な考え方は、最後の要素を指すポインタを持つことです。新しい項目を追加するたびに、最後の項目のフィールド「次」がリフレッシュされ、新しく追加されたアイテム。

挿入方法はうまくいきますが、問題なく項目を追加できますが、何らかの理由でリストから項目を削除できません。ここで

は、「リンク」または「ノード」のコードです：

public class Link { 
    public long data; 
    public Link next; 

    public Link(long val) { 
    data = val; 
    next = null; 
    } 

    public void displayLink() { 
    System.out.print(data + " "); 
    } 

} // end class 

これは、作業を行ってクラスのコードで、バグはどこかここで明らかである：

public class CircularList { 
Link first; 
Link last; 

public CircularList() { 
    first = null; 
    last = null; 
} 

public Link find(long key) { 
    Link current = first; 
    while(current.data != key) { 
     current = current.next; 
    } 
    return current; 
} // end find 

public Link delete() { 
    if(first.next == null) 
     last = null; 
    Link temp = first; 
    first = first.next; 
    return temp; 
} // end delete 

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

public void insert(long val) { 
    Link newLink = new Link(val); 

    if(isEmpty()) 
     last = newLink; 

    newLink.next = first; 
    first = newLink; 
    last.next = first; 
} // end insert 

public void displayAmount(int n) { 
    Link current = first; 
    while(n>0) { 
     current.displayLink(); 
     current = current.next; 
     n--; 
    } 
    System.out.println(""); 
} // end displayAmount 

} // end class 

そして、メインのアプリコード：表示金額は一種の愚かに見える

public class App { 
public static void main(String[] args) { 
    CircularList cl = new CircularList(); 

    cl.insert(10); 
    cl.insert(20); 
    cl.insert(30); 
    cl.insert(40); 

    cl.displayAmount(6); 

    cl.delete(); 

    cl.displayAmount(6); 
} 
} // end class 

、私は無限ループとメートルを避けるために試してみました単純に機能する単純なものを用意してください。

Answer 1

あなたの削除（）関数の中でreturn temp前last.next = firstを追加します。

public Link delete() { 
    if(first.next == null) 
     last = null; 
    Link temp = first; 
    first = first.next; 
    if(last != null) 
     last.next = first 
    return temp; 
} 

更新：

私はfirst.next == nullを満たすシナリオを見つけることができない、と我々は削除を呼び出す考慮に入れる必要があります（）空のリストに。

public Link delete() { 
    Link temp = first; 
    if(first == null){ 
     ; // or you can throw some exception as a warning 
    } 
    else if(first==last){ // only one element 
     first = null; // reset to initial state 
     last = null; 
    } 
    else{ 
     first = first.next; 
     last.next = first; 
    } 
    return temp; 
} 

Answer 2

delete()メソッドは、リストの循環性を処理しません。最後の要素は最初の要素を指します。最初の要素が削除されたときにも更新が必要です。

つまり、firstではなく、firstを指すようにlast.nextを設定する必要があります。

その他の問題は、最終要素を削除して（空になるように）、lastをnullに設定する必要があることです。

public Link delete() { 
    if (first.next == null) { 
     first = null; 
     last = null; 
    } 
    Link temp = first; 
    first = first.next; 
    last.next = first; 
    return temp; 
}