链表是具有不同长度的数据结构，任何节点都可以删除或添加到链表中。在本教程中，我们将实现一个完整的程序，用于在具有空间和时间复杂度的链表中插入节点。让我们首先了解问题陈述。
问题简介
在给定的问题中，我们给出一个链表，由于我们可以通过在链表中添加或删除节点来更改链表的大小，因此我们将在链表中添加或插入节点。
在链表中，我们可以在三个不同的位置添加新节点：最前面的节点、最后一个节点之后以及链表的中间。例如，给定的链表是 –
1 -> 2 -> 3 -> 4 -> 5 -> null，我们必须添加一个值为 9 的随机节点。因此，有很多情况需要添加节点，例如 –
在起始处添加节点 – 7 -> 1 -> 2 -> 3 -> 4 -> 5 -> null
立即学习“Java免费学习笔记（深入）”；
在中间添加节点 – 1 -> 2 -> 3 -> 7 -> 4 -> 5 -> null
在末尾添加节点 – 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> null
让我们看看实现以下任务的方法 –
在链表开头添加节点
示例
要在链表的开头添加节点，我们必须创建新节点并将链表的头作为下一个节点传递给新节点，然后将头移动到新节点，添加新节点节点到链表的开头。
// creating the linked list nodeclass Node { constructor(data) { this.value = data; this.next = null; }}function push(tail, data){ var new_node = new Node(data); tail.next = new_node; tail = tail.next; return tail}function add(data) { var new_node = new Node(data); new_node.next = head; return new_node;}var head = new Node(1);var tail = head;tail = push(tail, 2)tail = push(tail, 3)tail = push(tail, 4)tail = push(tail, 5)head = add(7);var data = 0;while(head != null) { data = data + head.value + " -> "; head = head.next;}console.log("Linked List after adding a node at starting: ")console.log(data + "null")
登录后复制
上述代码的时间复杂度为 O(1)，因为我们只需移动一个指针，同样没有使用额外的空间，使得空间复杂度为 O(1)。
在链表中间添加节点
示例
要在链表中间添加节点，我们必须创建新节点并传递该节点，然后才能将链表的新节点添加为新节点的下一个节点，这会添加新节点节点到中间的链表。
// creating the linked list nodeclass Node { constructor(data) { this.value = data; this.next = null; }}function push(tail, data) { var new_node = new Node(data); tail.next = new_node; tail = tail.next; return tail}function add(data,head) { var new_node = new Node(data); var temp = head; while(temp.value != 3) { temp = temp.next; } new_node.next = temp.next; temp.next = new_node; return head;}var head = new Node(1);var tail = head;tail = push(tail, 2)tail = push(tail, 3)tail = push(tail, 4)tail = push(tail, 5)head = add(7,head);var data = 0;while(head != null) { data = data + head.value + " -> "; head = head.next;}console.log("Linked List after adding node in middle:")console.log(data + "null")
登录后复制
上述代码的时间复杂度是 O(N)，因为我们必须移动到需要添加新节点的节点。上述过程的空间复杂度是 O(1)，因为我们没有使用任何额外的空间。
在链表末尾添加节点
示例
要在链表末尾添加节点，我们必须创建一个新节点，并将该节点添加到尾节点之后，并将尾节点移动到下一个节点。
// creating the linked list nodeclass Node { constructor(data) { this.value = data; this.next = null; }}function push(tail, data) { var new_node = new Node(data); tail.next = new_node; tail = tail.next; return tail }function add(data) { var new_node = new Node(data); tail.next = new_node; tail = tail.next return tail;}var head = new Node(1);var tail = head;tail = push(tail, 2)tail = push(tail, 3)tail = push(tail, 4)tail = push(tail, 5)tail = add(7);var data = 0;while(head != null){ data = data + head.value + " -> "; head = head.next;}console.log("Linked List after adding a node at the end: ")console.log(data + "null")
登录后复制
上述代码的时间复杂度为 O(1)，因为我们只需移动一个指针，同样没有使用额外的空间，使得空间复杂度为 O(1)。
结论
在上面的教程中，我们学习了如何通过三种可能的方式在现有链表中添加新节点。我们已经看到了带有解释的正确代码以及时间和空间复杂性。在链表中间添加一个节点需要 O(N) 时间，而对于其他两种情况，其时间复杂度为 O(1)，并且对于所有三种可能性，空间复杂度都是 O(1)。
以上就是在链表中插入节点的 JavaScript 程序的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2690075.html
