在java中，在链表的开头插入新节点后，自动更新head节点

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;
}

这是我的主要课程，有没有其他方法可以更有效地做到这一点？

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

这是我的主类，有其他方法可以更有效地做到这一点吗？

没有
这是这个问题的经典解决方案。

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

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

Answer 2

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

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

既然你写你"。。。想要在列表的开头添加新的节点">，则不需要将节点作为参数传递给insert。链接实例可以使用其head成员在其之前执行插入，然后更新其head以引用该新节点。insert方法也不需要返回新创建的节点。调用者不必担心这样的实现细节。

最后，您可以添加一个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 */
}

然后在链表类中，确保您有一个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... */

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