扭轉一個雙鏈表 -

Question

嘿，我目前卡在我的DoublyLinkedList的反向方法。一切工作正常（不知何故），除了相反的方法。我沒有收到任何錯誤 - System.out.println(list.reverse())根本沒有輸出。

有什麼建議嗎？非常感謝你提前。 :)

好吧：我現在編輯了我的代碼。到目前爲止，everyhing正常工作。但是，遞歸方法只是按照相同的順序打印列表，而不是實際地倒轉它。

更新的代碼：

public class DoublyLinkedStringList { 

private String content; 
private DoublyLinkedStringList prev; 
private DoublyLinkedStringList next; 

public DoublyLinkedStringList(String info) { 
    content = info; 
    prev = null; 
    next = null; 
} 

private DoublyLinkedStringList(String content, DoublyLinkedStringList prev, DoublyLinkedStringList next) { 
    this.content = content; 
    this.prev = prev; 
    this.next = next; 
} 

public DoublyLinkedStringList prepend(String info) { 
    DoublyLinkedStringList newNode = new DoublyLinkedStringList(info); 
    prev = newNode; 
    newNode.next = this; 

    return newNode; 
} 

public DoublyLinkedStringList delete(int index) { 
    DoublyLinkedStringList curr = this; 

    if (index == 0) { 
     next.prev = null; 
     return next; 
    } 

    for (int i = 0; i < index; i++) { 
     curr = curr.next; 
    } 

    curr.prev.next = curr.next; 
    if (curr.prev.next != null) {    
     curr.prev.next.prev = curr.prev; 
    } 
    return this; 
} 

public DoublyLinkedStringList reverse() { 
    DoublyLinkedStringList currNode = this; 

    while (currNode != null) { 
     DoublyLinkedStringList temp = currNode.next; 
     currNode.next = currNode.prev; 
     currNode.prev = temp; 

     if (currNode.prev != null) { 
      currNode = currNode.prev; 
     } 
    } 

    return this; 
} 

@Override 
public String toString() { 
    StringBuilder sb = new StringBuilder(); 

    for (DoublyLinkedStringList currNode = this; currNode != null; currNode = currNode.next) { 
     sb.append(currNode.content); 
     if (currNode.next != null) { 
      sb.append(", "); 
     } 
    } 
    return sb.toString(); 
} 

public static void main(String argv[]) { 
    DoublyLinkedStringList list = new DoublyLinkedStringList("Testliste"); 
    list = list.prepend("6"); 
    list = list.prepend("5"); 
    list = list.prepend("4"); 
    list = list.prepend("3"); 
    list = list.prepend("2"); 
    list = list.prepend("1"); 
    list = list.prepend("0"); 

    list = list.delete(1); 
    System.out.println(list); 

    list = list.reverse(); 
    System.out.println(list); 
} 

}

Answer 1

通常我會實現接口Iteratable並使用Iterator扭轉列表中，但我一直在我的修訂符合當前模型。我將Node的getNext()和getPrev()方法的返回類型更改爲取決於forward變量。現在，列表從未更改鏈接，當「顛倒」但它通過變量getNext()和getPrev()行爲以相反的順序遍歷。

IDEONE link to code

考慮這個編輯：

class DoublyLinkedStringList { 

private Node head, tail; 
boolean forward; 

/** 
* Diese Klasse repraesentiert einen Knoten in der Doubly Linked List der 
* Klasse 
* <code>DoublyLinkedStringList</code> 
* 
*/ 
private class Node { 
    private String content; 
    private Node next; 
    private Node prev; 

    public Node(String content) { this.content = content; } 

    public Node(String content, Node next) { 
     this.content = content; 
     if(forward) { this.next = next; }      //EDITED 
     else  { this.prev = next; }      //EDITED 
    } 

    public Node getNext() { return (forward) ? next : prev; } //EDITED 
    public Node getPrev() { return (forward) ? prev : next; } //EDITED 

    public void setNext(Node next) { 
     if(forward) { this.next = next; }      //EDITED 
     else  { this.prev = next; }      //EDITED 
    } 

    public void setPrev(Node prev) { 
     if(forward) { this.prev = prev; }      //EDITED 
     else  { this.next = prev; }      //EDITED 
    } 
} 

public DoublyLinkedStringList() { 
    this.head = null; 
    this.tail = null; 
} 

public Node prepend(String info) { 
    Node newNode = new Node(info); 
    newNode.setPrev(null); 
    newNode.setNext(getHead()); 
    if(newNode.getNext()!=null) { 
     newNode.getNext().setPrev(newNode);      //EDITED 
    } 
    if(forward) { head = newNode; }       //EDITED 
    else  { tail = newNode; }       //EDITED 
    if(getTail() == null) {         //EDITED 
     if(forward) { tail = newNode; }       //EDITED 
     else  { head = newNode; }       //EDITED 
    } 
    return head; 
} 

public Node delete(int index) { 
    Node currNode = getHead(); 
    int count = 0; 

    if (index == 0) { 
     if(forward) { head = head.next; }      //EDITED 
     else  { tail = tail.prev; }      //EDITED 
     return head; 
    } 

    while (currNode != null) { 
     if (count + 1 == index) { 
      currNode.next.prev = currNode.prev; 
      currNode.prev.next = currNode.next;    //EDITED 
      break; 
     } 
     currNode = currNode.getNext();      //EDITED 
     count++; 
    } 
    return currNode; 
} 

private Node next() { 
    Node currNode = head; 

    if (forward) { 
     return currNode.getNext(); 
    } else { 
     return currNode.getPrev(); 
    } 
} 

public Node getHead() { return (forward) ? head : tail; }  //EDITED 
public Node getTail() { return (forward) ? tail : head; }  //EDITED 
public DoublyLinkedStringList reverse() { forward = !forward; return this; } 

@Override 
public String toString() { 
    StringBuilder sb = new StringBuilder(); 
    //EDITED LOOP STRUCTURE 
    for (Node currNode = getHead(); currNode != null; currNode = currNode.getNext()) { 
     sb.append(currNode.content); 
     if (currNode.getNext() != null) { 
      sb.append(", "); 
     } 
    } 
    return sb.toString(); 
} 

public static void main(String argv[]) { 
    DoublyLinkedStringList list = new DoublyLinkedStringList(); 
    list.prepend("6"); 
    list.prepend("5"); 
    list.prepend("4"); 
    list.prepend("3"); 
    list.prepend("2"); 
    list.prepend("1"); 
    list.prepend("0"); 
    list.delete(3); 
    System.out.println(list); 
    System.out.println(list.reverse()); 
} 
} 

Answer 2

一個你要與你的設計的問題是，當你扭轉列表中的頭變成了尾巴，尾巴變成了頭。但客戶指向頭部，而不是尾部。即使你做了100％正確的操作，你也不能改變客戶端的引用。你想要做的是將列表的概念作爲一個對象與組成這個對象的節點（目前你已經將這兩個概念結合在一起，因爲節點是列表，反之亦然）。通過將它們分開，對列表的引用始終是相同的，無論其中包含什麼，排序等。該列表包含頭部和尾部引用，並且節點僅包含下一個/ prev。現在，如果在頭部/尾部改變（即前置，刪除或反向）時不更換每個參考，您的列表中的每個節點都會有頭部和尾部，這可能會導致令人討厭的錯誤彈出。如果您將這兩個實例移出每個節點，則無需對更改列表進行多少維護。我認爲如果你這樣做，那麼你會發現實現反向更容易。

你的錯誤正是我說的問題。最後你要回復這個問題，以及客戶的頭像（即這個）。但是，在遍歷並反轉所有內容之後，頭部現在是尾部，所以您通過返回這個來返回新的尾部。而尾部的toString（）是沒有用的。

Answer 3

你只需要設置頭部和尾部。那麼它應該工作。但看到chubbsondubs回答進一步改善！

Answer 4

既然你有一個DoublyLinkedStringList作爲返回類型，我想你想返回一個新的對象。在這種情況下，我建議你循環你的對象，並用你已經實現的prepend方法構建一個新的列表（任何一個case有其他錯誤）。您可以從空列表開始，並且在掃描原始對象時添加當前元素。否則，如果你想反轉列表「in place」，你應該返回void，用最後一個元素改變頭部，並且由於是雙重鏈接的，所以你應該做任何事情，因爲有指向節點的指針兩個方向。

Answer 5

嘗試一下本作相反的方法：

public class DoublyLinkedList { 
    Node first, current; 
    boolean forward; 
     //constructors... methods... 

    private Node next() { 
     if(forward) return current.next(); 
     else return current.previous(); 
    } 

    public void reverse() { 
    while(true) { 
      if(next() == null) { 
     first = current; 
     forward = !forward; 
     return; 
     } 
     current = next(); 
    } 
    } 
} 

Answer 6

這裏只是我的解決方案。不幸的是，我沒有更多的時間來解釋說明。

public class DoublyLinkedStringList { 
    private String info; 
    private DoublyLinkedStringList prev; 
    private DoublyLinkedStringList next; 

public DoublyLinkedStringList(String pInfo) 
{ 
    info = pInfo; 
    prev = null; 
    next = null; 
} 

private DoublyLinkedStringList(String pInfo, DoublyLinkedStringList pPrev, DoublyLinkedStringList pNext) 
{ 
    info = pInfo; 
    prev = pPrev; 
    next = pNext; 
} 

public DoublyLinkedStringList prepend(String info) 
{ 
    DoublyLinkedStringList n = new DoublyLinkedStringList(info); 
    prev = n; 
    n.next = this; 

    return n; 
} 

public DoublyLinkedStringList delete(int index) 
{ 
    if (index == 0) 
    { 
     next.prev = null; 
     return next; 
    } 

    DoublyLinkedStringList d = this; 

    for (int i = 0; i<index; i++) 
     d = d.next; 

    // d is now the node which should be deleted 

    // after delete(x) "next" schould be on pos x 

    d.prev.next = d.next; // take the next of the prev and set the new next to the next of d 

    if (d.prev.next != null) // if the next of d was not set to null, it must get to know his new prev (d's prev) 
     d.prev.next.prev = d.prev; 

    return this; 
} 


public DoublyLinkedStringList reverse() // moe or less less similar to my implementation in IntList.java 
{ 
    DoublyLinkedStringList oldLast = getLast(); 
    next.reverse(this); 
    prev = next; 
    next = null; 
    return oldLast; 
} 

public void reverse(DoublyLinkedStringList last) 
{ 
    if (next != null) 
     next.reverse(this); 
    prev = next; 
    next = last; 
} 

public DoublyLinkedStringList getLast() 
{ 
    if (next == null) 
     return this; 
    return next.getLast(); 
} 

@Override 
public String toString() 
{ 
    String r = ""; 

    for (DoublyLinkedStringList i = this; i != null; i = i.next) 
    { 
     r += i.info; 
     if (i.next != null) 
      r += ", "; 
    } 
    return r; 
} 

public String reverseToString() // uses prev; just for testing issues :) 
{ 
    String r = ""; 

    for (DoublyLinkedStringList i = getLast(); i != null; i = i.prev) 
    { 
     r += i.info; 
     if (i.prev != null) 
      r += ", "; 
    } 
    return r; 
} 

public static void main(String argv[]) 
{ 
    DoublyLinkedStringList list = new DoublyLinkedStringList("Test"); 
    list = list.prepend("6"); 
    list = list.prepend("5"); 
    list = list.prepend("4"); 
    list = list.prepend("3"); 
    list = list.prepend("2"); 
    list = list.prepend("1"); 
    list = list.prepend("0"); 
    list = list.delete(1); 
    System.out.println(list); 
    System.out.println(list.reverseToString()+"\n"); 

    list = list.reverse(); 
    System.out.println(list); 
    System.out.println(list.reverseToString()); 

    list = list.delete(6); 
    list = list.delete(0); 
    System.out.println(list); 
    list = list.reverse(); 
    list = list.prepend("1"); 
    System.out.println(list); 
}