单独转换为单向链接列表双向链接列表

Question

我已经写了一个带有添加和遍历方法的单链表的小程序。现在我想将它转换为双向链表。我知道双链表的所有概念，但在我的程序中实现它却很困难。

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字段添加到适当的getter和setter列表类，然后添加这个方法：

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

这个方法沿着一个当前单向链接的列表走下去，并将每个节点反向链接，使列表双向链接。

当然，您还需要修改其他方法，但这至少是一个很好的起点。