algorithm - 为什么这个 LinkedList 排序算法有效？

Question

我一直在研究一种算法，将元素添加到链表中，并在添加元素时对其进行排序。我的代码有效，我知道大部分原因，但我很惊讶地看到这段代码适用于在列表末尾添加元素。这是代码:

    public void add(int value)
  {
    Node currentNode;
    Node previousNode;
    Node newNode;
    if(firstNode == null)
    {
      firstNode = new Node(value,firstNode);
    }

    else
    {
     currentNode = firstNode; 
     previousNode = null;

     while(currentNode != null && value > currentNode.getValue())
     {
      previousNode = currentNode;
      currentNode = currentNode.getNextNode();
     }
       if(previousNode == null)
       {
        firstNode = new Node(value, firstNode); 
       }
       else
       {
       newNode = new Node(value,currentNode);
       previousNode.setNextNode(newNode); 
       }
    }
  }

所以我知道这适用于添加到开头或中间，但它如何添加到结尾？我的意思是，如果 while 循环遍历到列表的末尾，则 currentNode 是最后一个节点，前一个节点是之前的一个，所以不会:

newNode = new Node(value,currentNode);
previousNode.setNextNode(newNode); 

从不在末尾添加元素？它不会总是在先前和当前之间添加新节点吗？

Answer 1

previousNode，顾名思义，指向当前节点后面的一个节点。当您到达终点时，(当您尝试插入的值大于任何当前元素时会发生这种情况)currentNode 变为 null，但 previousNode 指向最后一个节点。因此 previousNode.setNextNode(newNode) 工作正常。