当插入一个新元素时，从最低值到最高值对链表进行排序

Question

我刚刚创建了一个从头创建的链表，目前为止我创建了两个插入新元素到列表的方法。一种方法将元素放置在列表的开始位置，另一种方法将其放在列表的后面。我现在试图创建第三种方法，其中我试图放入列表中的元素将根据元素的值进行放置。所以如果我试图插入的元素的值小于列表中的第一个元素，但低于列表中的第二个元素，我希望该方法自动将新元素放置在这两个元素之间。

这听起来很简单，但我现在意识到执行起来比我想象的要困难得多。我似乎无法停止NullPointerExceptions和其他错误，所以在这一点上我完全空白，不知道下一步该怎么做。

Anywas，下面的代码：

import java.util.*; 

public class OrdnetLenkeliste<T extends Comparable<T>> extends Lenkeliste<T>{ 

    public void insert(T element){ 
     Node node = new Node(element); 
     if(super.isEmpty()){ 
      node.next = head; 
      head = node; 
      numberOfNodes++; 
     } else { 
      Node currentNode = head; 
      Node previous = null; 

      while(currentNode != null){ 
       if(currentNode.data.compareTo(node.data) < 0){ 
        currentNode = currentNode.next; 
       } else if (currentNode.data.compareTo(node.data) > 0 && currentNode.previous.data.compareTo(node.data) < 0){ 
        node = currentNode.previous; 
        currentNode.previous = node.previous; 
        currentNode = currentNode.next; 
        numberOfNodes++; 
       } else if(currrentNode.data.compareTo(node.data) == 0){ 
        currentNode = currentNode.next; 
        currentNode.previous = node; 
        numberOfNodes++; 
       } 
      } 
     } 
    } 
} 

有可能是在变量的几个拼写错误，但这只是因为我翻译的变量名，使代码更易读。

Answer 1

你的代码有几个错误，你已经使它比它需要更复杂。

首先，实际上只有两种情况：新节点小于当前节点，在这种情况下，新节点插入到当前节点之前，或者它大于或等于当前节点，因此需要插入列表中的某个地方。

这样的想法是非常简单的：

loop until the new node's value is less than the current node's value 
insert the new node before the current node 

唯一的特殊情况是，当列表为空或新节点比第一点更小。在这两种情况下，新节点成为列表的头部。

执行过程比较冗长，但并不那么复杂。

public void insert(T element) 
{ 
    Node node = new Node(element); 
    Node currentNode = head; 
    Node previous = null; 

    // loop to find the insertion point. 
    while (currentNode != null && node.Data.compareTo(currentNode.data) >= 0) 
    { 
     previous = currentNode; 
     currentNode = currentNode.next; 
    }   

    // Insert the item between the previous node and the current node. 

    // This node's next pointer references the current node. 
    node.next = currentNode; 

    if (previous == null) 
    { 
     // Either the list is empty, 
     // or the new node is smaller than the head. 
     // This node becomes the head. 
     head = node; 
    } 
    else 
    { 
     // otherwise, the previous node's next pointer 
     // references the current node. 
     previous.next = node; 
    } 
    ++numberOfNodes; 
} 

Answer 2

看起来你有一些错误在链接列表中插入新元素。

  while(currentNode != null){ 
       if(currentNode.data.compareTo(node.data) < 0){ 
        currentNode = currentNode.next; 
       } 
       else if (currentNode.data.compareTo(node.data) > 0 && currentNode.previous == null){ 
        currentNode.previous = node; 
        head = node;  
       } 
       else if (currentNode.data.compareTo(node.data) > 0 && currentNode.previous.data.compareTo(node.data) < 0){ 
        currentNode.previous.next = node; // set the next for previous node of current node 
        node.previous = currentNode.previous; // set previous and next of node 
        node.next = currentNode; 
        currentNode.previous = node; // set the previous of current node 
        numberOfNodes++; 
       } else if(currrentNode.data.compareTo(node.data) == 0){ 
        // I am not sure what you want to do here, if you want to insert the node before current node, then do the same as above 
        currentNode.previous.next = node; // set the next for previous node of current node 
        node.previous = currentNode.previous; // set previous and next of node 
        node.next = currentNode; 
        currentNode.previous = node; // set the previous of current node 
        numberOfNodes++; 
       } 
      }