convert under singly Связанный список с дважды связанным списком

Question

Я уже написал небольшую программу одиночного связанного списка с помощью метода add и traverse. Теперь я хочу преобразовать его в двусвязный список. Я знаю всю концепцию двусвязного списка, но мне трудно выполнить ее в моей программе.

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

просто добавить переменную private Node<T> prevRef; экземпляра в Node класса, и установить его во время add() метода. Я полагаю, что traverse() получит логическое (или даже лучше, перечисление) direction аргумент

Answer 2

Добавить Node<T> prevRef поле в список вашего класса с соответствующими добытчиками и сеттеров, а затем добавить этот метод:

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(); 
    } 
} 

Этот метод пройдите вниз по однократно связанному списку и свяжите каждый узел в обратном порядке, оставив список дважды связанным.

Конечно, вам также нужно будет изменить другие методы, но это, по крайней мере, хорошая отправная точка.