C/C＋编程笔记：链接列表（链表）丨插入节点的三种方法

在上一篇文章中，我们介绍了链接列表。我们还创建了一个具有3个节点的简单链表，并讨论了链表遍历。

本文讨论的所有程序均考虑以下链表的表示形式。

C ++

C

在这篇文章中，讨论了在链表中插入新节点的方法。可以通过三种方式添加节点：

1）在链表的最前面

2）在给定节点之后。

3）在链接列表的末尾。

在前面添加一个节点：（4个步骤）

将新节点始终添加到给定链接列表的开头之前。新添加的节点成为链接列表的新头。例如，如果给定的链接列表为10-> 15-> 20-> 25，并且我们在前面添加了项目5，则链接列表将变为5-> 10-> 15-> 20-> 25。让我们将添加到列表最前面的函数称为push（）。push（）必须接受一个指向头指针，因为必须推头指针改为指向新的节点。

以下是在最前面添加节点的4个步骤。

C++

C

push（）的时间复杂度为O（1），因为它要做的工作量是恒定的。

在给定节点之后添加一个节点：（5个步骤）

给我们一个指向节点的指针，并将新节点插入到给定节点之后。

C ++

C

insertAfter（）的时间复杂度为O（1），因为它的工作量是恒定的。

在最后添加一个节点：（6个步骤）

将新节点始终添加到给定链接列表的最后一个节点之后。例如，如果给定的链接列表为5-> 10-> 15-> 20-> 25，并且我们在末尾添加了项目30，则链接列表将变为5-> 10-> 15-> 20-> 25- > 30。

由于链接列表通常由其头部表示，因此我们必须遍历该列表直至结束，然后将最后一个节点的下一个更改为新节点。

以下是最后添加节点的6个步骤。

C

append的时间复杂度为O（n），其中n是链表中节点的数量。由于从头到尾都有一个循环，因此该函数可以执行O（n）。

还可以通过保留指向链表尾部的额外指针，将该方法优化为在O（1）中工作。

以下是使用上述所有方法创建链表的完整程序。

C ++

#include

usingnamespacestd;

classNode

{

public:

intdata;

Node *next;

};

voidpush(Node** head_ref, intnew_data)

{

Node* new_node = newNode();

new_node->data = new_data;

new_node->next = (*head_ref);

(*head_ref) = new_node;

}

voidinsertAfter(Node* prev_node, intnew_data)

{

if(prev_node == NULL)

{

cout

return;

}

Node* new_node = newNode();

new_node->data = new_data;

new_node->next = prev_node->next;

prev_node->next = new_node;

}

voidappend(Node** head_ref, intnew_data)

{

Node* new_node = newNode();

Node *last = *head_ref; /* used in step 5*/

new_node->data = new_data;

new_node->next = NULL;

then make the new node as head */

if(*head_ref == NULL)

{

*head_ref = new_node;

return;

}

while(last->next != NULL)

last = last->next;

last->next = new_node;

return;

}

voidprintList(Node *node)

{

while(node != NULL)

{

cout

node = node->next;

}

}

int main()

{

Node* head = NULL;

append(&head, 6);

push(&head, 7);

push(&head, 1);

append(&head, 4);

insertAfter(head->next, 8);

cout

printList(head);

return 0;

}

C语言

#include

#include

structNode

{

intdata;

structNode *next;

};

voidpush(structNode** head_ref, intnew_data)

{

structNode* new_node = (structNode*) malloc(sizeof(structNode));

new_node->data  = new_data;

new_node->next = (*head_ref);

(*head_ref)    = new_node;

}

voidinsertAfter(structNode* prev_node, intnew_data)

{

/*1. check if the given prev_node is NULL */

if(prev_node == NULL)

{

printf("the given previous node cannot be NULL");

return;

}

structNode* new_node =(structNode*) malloc(sizeof(structNode));

new_node->data  = new_data;

new_node->next = prev_node->next;

prev_node->next = new_node;

}

voidappend(structNode** head_ref, intnew_data)

{

structNode* new_node = (structNode*) malloc(sizeof(structNode));

structNode *last = *head_ref;  /* used in step 5*/

new_node->data  = new_data;

it as NULL*/

new_node->next = NULL;

if(*head_ref == NULL)

{

*head_ref = new_node;

return;

}

while(last->next != NULL)

last = last->next;

last->next = new_node;

return;

}

voidprintList(structNode *node)

{

while(node != NULL)

{

printf(" %d ", node->data);

node = node->next;

}

}

intmain()

{

structNode* head = NULL;

append(&head, 6);

push(&head, 7);

push(&head, 1);

append(&head, 4);

insertAfter(head->next, 8);

printf("\n Created Linked list is: ");

printList(head);

return0;

}

输出：

创建的链接列表为：1 7 8 6 4

希望本篇文章对你有帮助~