java链表开头插入新节点后自动更新头节点

Question

我有这段代码可以将新节点添加到我的链表中，我想在列表的开头添加新节点，我在插入函数上写了这段代码，

Node insert(Node start, int x){
    Node newNode = new Node(x);
    if(start == null) {
        return start = newNode;
    } else {
        newNode.next = start;
        start = newNode;
    }
    return start;
}

这是我的主要 class，有没有其他更有效的方法？

LinkedList list=new LinkedList();
Node startPoint=new Node(20);  
Node newNode=list.insert(startPoint, 16);
Node newNode1=list.insert(newNode, 22);
Node newNode2=list.insert(newNode1, 2);
Node newNode3=list.insert(newNode2, 5);
Node newNode4=list.insert(newNode3, 44);
Node newNode5=list.insert(newNode4, 77);

Answer 1

And this is my main class ,Is there any other way to do it more efficiently ?

没有。
这是此问题的 classical 解决方案。

你不能做得更好的原因是这个操作的这个实现需要 O(1) 时间。这真的很酷也很性感，因为执行它的时间不取决于输入的大小，这对于大型数据集来说真的很酷属性。

您可以通过使用链表实现更复杂的操作来继续锻炼您的 DS 技能，例如插入到列表中的任意位置或反转链表。

Answer 2

效率还可以，但你可以让它更优雅。

首先，您的主程序不必知道节点。它应该只需要创建链表实例，并向其中添加整数。您的主要代码现在维护一些 state（如 startPoint），实际上链表实例应该为您管理。它应该维护对其列表中第一个节点的引用（以 null 开头）：通常这称为 head.

由于您写道 "...想在列表的开头添加新节点"，您不需要将节点作为参数传递给 insert。链接实例可以使用其 head 成员在它之前进行插入，然后更新其 head 以引用该新节点。 insert 方法应该也不需要 return 新创建的节点。调用者不必担心此类实现细节。

最后，您可以添加一个 Node 构造函数重载，它接受对其 next 成员的引用。这将有助于使您的 insert 方法非常简洁。

所以，让你的 Node 构造函数像这样（我假设值成员被称为 value，如果你使用不同的名称，比如 data，根据需要调整）：

class Node {
    private final int value;
    private Node next;

    public Node(int value) {
        this.value = value;
        this.next = null;
    }

    public Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }

    /* ... other methods */
}

然后在您的链表 class 中，确保您有一个 head 成员，并定义您的 insert 方法，使其只接受一个值参数：

public class LinkedList {
    private Node head;

    public LinkedList() {
        this.head = null;
    }

    void insert(int x) {
        head = new Node(x, head);
    }

    /* other methods ... */
}

然后你的主程序可以做：

    LinkedList list = new LinkedList();
    list.insert(20);
    list.insert(16);
    list.insert(22);
    list.insert(2);
    /* ...etc... */

当然，您需要添加允许您从列表中检索值并对其执行其他有趣操作的方法。

java链表开头插入新节点后自动更新头节点

Updating the head node automatically after inserting new node at the beginning of the linked list in java

java

linked-list

data-structures