從定製列表中遞歸地插入和刪除

Question

插入代碼似乎正在完美工作，直到最後一次插入，而不是按順序添加它，而是將它放在列表的末尾。

public void insert(Comparable item) 
{ 
    if (this.first == null || item.compareTo(this.first.data) <= 0) 
    { 
     addFirst(item); 
    } 
    else if(item.compareTo(this.first.data) > 0) 
    { 
     addLast(item); 
    } 
    else 
    { 
     Node oldFirst = this.first; 
     this.first = this.first.next; 

     insert(item); 

     this.first = oldFirst; 
    } 
} 

這是它產生的輸出...

6 Item(s) 

5 
16 
21 
22 
45 
23 

---

remove方法停止編譯它刪除的項目，我無法找出原因後。

public Comparable remove(Comparable item) 
{ 
    if(this.first == null) 
    { 
     return null; 
    } 

    Node oldFirst = this.first; 

    if(this.first.next == null && this.first.data.equals(item)) 
    { 
     Comparable found = this.first.data; 
     this.first = null; 
     return found; 
    }     

    this.first = this.first.next; 

    if(this.first.data.equals(item)) 
    { 
     Comparable found = this.first.data; 
     oldFirst.next = this.first.next; 
     this.first = oldFirst; 
     return found; 
    } 

    Comparable foundIt = remove(item);  

    return foundIt; 
} 

這是來自remove方法輸出....

at List.remove(List.java:164) 
Removed: 21. List has: 4 Item(s) 
at List.remove(List.java:164) 

16 
at List.remove(List.java:164) 
22 
45 
at TestRecursion.main(TestRecursion.java:87) 

Answer 1

我注意到你打電話addlast僅當產品比你的第一個元素更大。這不會給你一個排序列表。

考慮用1，4，2，3調用插入。輸出將按照該順序。 1，4，3，2

而且，爲什麼刪除崩潰......

//what if its last item, and the data !.equals(item)? 
if(this.first.next == null && this.first.data.equals(item)) 
{ 
    Comparable found = this.first.data; 
    this.first = null; 
    return found; 
} 
this.first = this.first.next; 
//first could be null here if you are at end of list. 
if(this.first.data.equals(item)) 
{ 
    Comparable found = this.first.data; 
    oldFirst.next = this.first.next; 
    this.first = oldFirst; 
    return found; 
} 

我建議您使用調試器。應該快速清理事情。

Answer 2

您的插入方法將23最後因爲

item.compareTo(this.first.data) > 0 

23確實比較，你第一要素。

Answer 3

public void insert(Comparable item) 
{ 
    first = insertRecursively(first, item); 
} 
private static Node insert(Node node, Comparable item) 
    if (node == null || item.compareTo(node.data) <= 0) 
    { 
     Node created = new Node(item); 
     created.next = node; 
     return created;    
    } 
    else 
    { 
     node.next = insertRecursively(node.next, item); 
     return node; 
    } 
} 

以遞歸方式做它需要改變剛剛檢查過的第一個/下一個。