自定義LinkedList與排序

Question

我想創建一個鏈表（不使用Java的默認，而是我自己定義）。 鏈表應該足夠能夠以某種順序添加數據。 與用戶一樣，嘗試按給定順序插入1,3和2。 「2」應該在3之前插入，並且生成的鏈表應該有1,2和3.

最重要的是，一切都應該使用泛型（我想學習它）。

爲自定義鏈接列表創建以下類，只需要幫助按排序順序提供插入。

package customlinkedlist; 

public class Node<T> { 

    private T data; 
    private Node<T> next; 

    public T getData() { 
     return data; 
    } 
    public void setData(T data) { 
     this.data = data; 
    } 
    public Node<T> getNext() { 
     return next; 
    } 
    public void setNext(Node<T> next) { 
     this.next = next; 
    } 
} 

然後界面 -

package customlinkedlist; 

public interface CustomLinkedList<T> { 

    Node<T> insert(T data); 
} 

和各自implementation-

package customlinkedlist; 

public class CustomLinkedListimpl<T> implements CustomLinkedList<T> { 

    private Node<T> head; 

    public CustomLinkedListimpl() { 
     head = new Node<T>(); 
     head.setNext(null); 
     head.setData(null); 
    } 

    public Node<T> insert(T data) { 

     Node<T> nodeToInsert = null; 

     if (head.getNext() == null) { 

      nodeToInsert = new Node<T>(); 
      nodeToInsert.setData(data); 
      nodeToInsert.setNext(null); 

      head.setNext(nodeToInsert); 
     } else { 

      Node<T> tempNode = head; 
      while(tempNode.getNext() != null) { 
       tempNode = tempNode.getNext(); 
      } 

      nodeToInsert = new Node<T>(); 
      nodeToInsert.setData(data); 
      nodeToInsert.setNext(null); 

      tempNode.setNext(nodeToInsert); 
     } 
     return nodeToInsert; 
    } 

    public void printList() { 

     if (head == null) { 
      System.out.println("List is null."); 
      return; 
     } 

     Node<T> tempNode = head.getNext(); 
     System.out.print(tempNode.getData()); 

     while (tempNode.getNext() != null) { 
      tempNode = tempNode.getNext(); 
      System.out.print(" --> " + tempNode.getData()); 
     } 
    } 
} 

這是客戶端接收機類

package customlinkedlist; 

public class CustomLLClient { 

    public static void main(String[] args) { 

     CustomLinkedListimpl<Integer> customLinkedList = new CustomLinkedListimpl<Integer>(); 
     customLinkedList.insert(1); 
     customLinkedList.insert(3); 
     customLinkedList.insert(2); 

     customLinkedList.printList(); 
    } 
} 

Answer 1

您可以使用Comparable泛型化你的排序。
有兩種方法可以實現insert方法。
1.遞歸
2.非遞歸

這裏是一個非遞歸的方式來實現它：

public void add(Comparable data) { //you can generify your code and then use Comparable<T> 
     Node nodeToInsert = new Node(data); 
     if (head == null) { 
      head = nodeToInsert; 

     } 
     else if (data.compareTo(head.data) < 0) { 
      nodeToInsert.next = head; 
      head = nodeToInsert; 
     } 
     else { 
      Node before = head, after = head.next; 
      while (after != null) { 
       if (data.compareTo(after.data) < 0) { 
        break; 
       } 
       before = after; 
       after = after.next; 
      } 
      nodeToInsert.next = before.next; 
      before.next = nodeToInsert; 
     } 
    }