在已排序的链表中插入节点 [英] Inserting Node in a Sorted linked list

问题描述

以下代码确保元素以排序的方式插入到链表中。

The following code ensures that elements are inserted in a linked list in a sorted manner.

在理解了这个逻辑之后，我决定自己测试。然而，当我写我的版本的代码如下。

After understanding the logic behind this i decided to test it on my own. However when i wrote my version of the code it as follows.

  public class SortedList {

    private Node first;

    public SortedList() {
        first = null;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public void insert(int j) {
        Node newNode = new Node(j);
        Node previous = null;
        Node current = first;

        while (current != null && j > current.iData) {
            previous = current;
            current = current.next;
        }

        if (previous == null)
            first = newNode;

        else

            newNode.next = current;
        previous.next = newNode;

    }

    public Node remove() {
        Node temp = first;
        first = first.next;
        return temp;
    }

    public void displayList() {
        System.out.println("First to -----> Last");
        Node current = first;

        while (current != null) {
            current.display();
            current = current.next;
        }
    }

}

NODE CLASS

NODE CLASS

public class Node {

    public int iData;
    public Node next;

    public Node(int id) {
        iData = id;
    }

    public void display() {
        System.out.println(iData + " ");
    }

}

测试类

TEST CLASS

public class SortedListApp {

    public static void main(String[] args) {

        SortedList list = new SortedList();

        list.insert(20);
        list.insert(40);

        list.displayList();

        list.insert(10);
        list.insert(30);
        list.insert(50);

        list.displayList();

        list.remove();

        list.displayList();

    }

}

唯一的区别两者之间是在我的版本当while循环终止时。我首先将newNode的下一个值设置为当前值，然后设置新节点的上一个下一个值。在原始代码中，它们已经被颠倒了。由于某种原因，这会抛出空指针异常。我想知道为什么？

The only difference between the two is that in my version when the while loop terminates. I first set the next value of the newNode to the current and then i set the next value of previous to the new Node. In the original code posted they have it reversed. For some reason this throws Null Pointer Exception. I am wondering why?

根据我的理解，一旦新节点找到插入位置。我们参考了上一个节点和当前节点，并且我们试图在前一个节点和当前节点的中间插入新的节点。因此，我所做的是将下一个新节点设置为当前节点，然后将上一节点的下一个设置为新节点。

From what i understand, once the new node finds its place for insertion. We have reference to the previous node and the current node and we are trying to insert the new node in the middle of the previous and the current. Therefore what i do is set the next of the new Node to the current and then i set the next of previous node to the new node.

请告诉我我在哪里

推荐答案

当以前为null时， / p>

Trace through this code when previous is null:

if (previous == null)
    first = newNode;
else
    newNode.next = current;
previous.next = newNode;

请注意，您从未真正更改以前的 如果语句，则这将尝试写入下一个 null ，导致崩溃。

Notice that you never actually changed previous in the if statement, so this will try to write the next field of null, causing the crash.

如果以前的为null，那么您需要先将节点列表，在这种情况下，您需要做的是将首先设置为 newNode 并使 newNode 的下一个指针指向旧列表。在以前不是 null 的情况下，则需要进行两次重新插入：您需要使 previous.next 指向新节点，新节点的下一个指针指向当前节点。您可以通过写入

If previous is null, then you need to prepend the node to the list, and in that case all you need to do is set first to newNode and make newNode's next pointer point to the old list. In the case where previous isn't null, then you need to do two rewirings: you need to make previous.next point to the new node and for the new node's next pointer to point to the current node. You can fix this by writing

if (previous == null) {
    newNode.next = current;
    first = newNode;
}
else {
    newNode.next = current;
    previous.next = newNode;
}

等价：

newNode.next = current;
if (previous == null)
    first = newNode;
else
    previous.next = newNode;

希望这有帮助！

这篇关于在已排序的链表中插入节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！