自定义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; 
     } 
    }