unten einfach umwandeln Verknüpfte Liste zu doppelt verkettete Liste

Question

Ich habe bereits ein kleines Programm der einzelnen verketteten Liste mit Add und Traverse-Methode in diesem geschrieben. Jetzt möchte ich es in eine doppelt verkettete Liste umwandeln. Ich kenne das Konzept der doppelt verketteten Liste, aber ich habe wenig Schwierigkeiten, es in meinem Programm zu implementieren.

public class SingleLinkList<T> { 

private Node<T> head; 
private Node<T> tail; 




public void add(T element) 
{ 
    Node<T> nd = new Node<T>(); 
    nd.setValue(element); 

    if (head==null) 
    { 
     head = nd; 
     tail = nd; 
    } 
    else 
    { 
     tail.setNextRef(nd); 
     tail = nd; 
    } 
} 

public void traverse(){ 

    Node<T> tmp = head; 
    while(true){ 
     if(tmp == null){ 
      break; 
     } 
     System.out.println(tmp.getValue()); 
     tmp = tmp.getNextRef(); 
    } 
} 

public static void main (String args[]) 
{ 
    SingleLinkList<Integer> s1 = new SingleLinkList<Integer>(); 
    s1.add(2); 
    s1.add(3); 
    s1.add(3); 

    s1.traverse(); 
} 

} 


class Node<T> { 

private T value; 
private Node<T> nextRef; 
public T getValue() { 
    return value; 
} 
public void setValue(T value) { 
    this.value = value; 
} 
public Node<T> getNextRef() { 
    return nextRef; 
} 
public void setNextRef(Node<T> nextRef) { 
    this.nextRef = nextRef; 
} 

public int compareTo(T arg) 
{ 
    if (arg==this.value) 
    { 
     return 0;} 
     else 
      {return 1;} 
    } 
} 

Answer 1

nur private Node<T> prevRef; Instanzvariable Node Klasse hinzufügen, und es während add() Verfahren eingestellt. Ich schlage vor, dass traverse() eine boolean erhalten (oder noch besser, Enum) direction Argument

Answer 2

hinzufügen Node<T> prevRef Feld zu Ihrer Liste Klasse mit entsprechenden Getter und Setter und dann diese Methode hinzufügen:

public void linkReverse(Node<T> head) { 
    if (head == null) { 
     return; 
    } 
    head.setPrevRef(null); 
    if (head.getNextRef() == null) { 
     return; 
    } 

    Node<T> prev = head; 
    Node<T> curr = head.getNextRef(); 

    while (curr != null) { 
     curr.setPrevRef(prev); 
     prev = curr; 
     curr = curr.getNextRef(); 
    } 
} 

Diese Methode wird Wenn Sie auf eine Liste mit derzeit einfach verknüpften Listen gehen, werden die einzelnen Knoten in umgekehrter Reihenfolge verknüpft, sodass die Liste doppelt verknüpft bleibt.

Natürlich müssten Sie auch die anderen Methoden ändern, aber das ist zumindest ein guter Ausgangspunkt.