C++程序向链表中插入节点

我们在前面的帖子中介绍了链表。我们还创建了一个包含3个节点的简单链表，并讨论了链表的遍历。
本帖子中考虑以下链表的表示。

// 链表节点
class Node
{
    public:
    int data;
    Node *next;
};
// 本代码由rathbhupendra提供```

在本帖子中，讨论了在链表中插入新节点的方法。新节点可以通过以下三种方式添加：

1）在链表的最前面。

2）在给定节点之后。

3）在链表的末尾。

在最前面添加节点：（4步流程）

新节点总是添加在给定链表的头之前。新添加的节点成为链表的新头。例如，如果给定的链表是10->15->20->25，我们在前面添加一个项5，则链表变为5->10->15->20->25。让我们称在列表前面添加的函数为push（）。push（）必须接收指向头指针的指针，因为push必须更改头指针以指向新节点（请参阅此处）

C++程序向链表中插入节点

这是使用类创建4个节点的链接列表的示例：

#include <iostream>
using namespace std;
class node {
public:
    int data;
    node* next;
    node(int d){
    data = d;
    next = NULL;
    }
};
void insertAthead(node*& head, int data)
{
    node* n = new node(data);
    n->next = head;
    head = n;
}
void print(node* head)
{
    while (head != NULL) {
        cout << head->data << "->";
        head = head->next;
    }
}
int main()
{
    node* head = NULL;
    insertAthead(head, 5);
    insertAthead(head, 2);
    insertAthead(head, 8);
    insertAthead(head, 3);
    print(head);
}

输出

    3->8->2->5->

说明： 我们要在链表的开头插入元素3、8、2和5，它将输出为—> 3→8→2→5→。

push（）的时间复杂度为O（1），因为它只做了固定量的工作。

在给定节点之后添加节点：（5步流程）

给定一个指向节点的指针，新节点插入在给定节点之后。

C++程序向链表中插入节点

// 针对给定的prev_node，插入新节点
// 给定prev_node是空的
if (prev_node == NULL)
{
    cout    << “给定的先前节点不能为空”;
    return;
}

// 2. 分配新节点
Node* new_node = new Node();

// 3. 放入数据
new_node->data = new_data;

// 4. 将新节点的下一个设为
// prev_node的下一个
new_node->next = prev_node->next;

// 5. 将prev_node的下一个设为
// new_node
prev_node->next = new_node;
}
//本代码由anmolgautam818提供```

insertAfter（）的时间复杂度为O（1），因为它只做了固定量的工作。

在末尾添加一个节点：(6个步骤的过程)

新节点总是添加在给定链表的最后一个节点后面。比如，如果给定的链表是5->10->15->20->25, 如果我们在末尾添加一个元素30，那么链表将变成5->10->15->20->25->30。

由于链表通常是通过其头部来表示的，我们必须遍历链表直至末尾，然后将倒数第二个节点改为新的节点。

C++程序向链表中插入节点

下面是添加节点到末尾的6个步骤。

// 给定指向列表头部的引用（指针的指针）和一个int，将新节点添加到末尾
void append(Node** head_ref, int new_data) 
{ 
   
    // 1. 分配新节点
    Node* new_node = new Node();
   
    // 用于第五个步骤
    Node *last = *head_ref;
   
    // 2. 放入数据
    new_node->data = new_data; 
   
    // 3. 这个新节点将成为
    //    最后一个节点，所以将其下一个节点设置为NULL
    new_node->next = NULL; 
   
    // 4. 如果链表为空，
    //    将新节点作为头部
    if (*head_ref == NULL) 
    { 
        *head_ref = new_node; 
        return; 
    } 
   
    // 5. 否则遍历到最后一个节点
    while (last->next != NULL) 
        last = last->next; 
   
    // 6. 将最后一个节点的下一个节点更改
    last->next = new_node; 
    return; 
} 
// 本代码由anmolgautam818贡献```

添加一个节点的时间复杂度是O(n)，其中n是链表中节点的数量。由于从头到尾有一个循环，所以该函数执行O(n)的工作。

通过保留链接列表尾部的额外指针，也可以将此方法优化为O(1)的算法。

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

//一个完整的、可工作的C++程序，演示了链表上的所有插入方法
# include
using namespace std;
//链表节点
class Node
{
    public:
    int data;
    Node *next;
};
//在列表前面插入一个新的节点，给出一个指向指针的头和一个int
void push(Node** head_ref, int new_data)
{
    //1.分配节点
    Node* new_node = new Node();
    //2.输入数据
    new_node->data = new_data;
    //3.将新节点的下一项作为头
    new_node->next = (*head_ref);
    //4.将头指向新的节点
    (*head_ref) = new_node;
}
//给定一个节点prev_node，在给定的prev_node之后插入一个新的节点
void insertAfter(Node* prev_node,int new_data)
{
    /*1.检查给定的prev_node是否为空*/
    if(prev_node==NULL)
    {
        cout<<"the given previous node cannot be NULL";
        return;
    }
    //2.分配新的节点
    Node* new_node = new Node();
    //3.输入数据
    new_node->data = new_data;
    //4.将新节点的下一项作为prev_node的下一项
    new_node->next=prev_node->next;
    //5.将prev_node的下一项改为新节点
    prev_node->next=new_node;
}
//给定一个指向指针的头和一个int，在末尾添加一个新的节点
void append(Node** head_ref,int new_data)
{
    //1.分配节点
    Node* new_node = new Node();
    //用于第5步
    Node* last = *head_ref;
    //2.输入数据
    new_node->data = new_data;
    /*3.这个新节点将是最后一个节点，所以它的下一项是NULL*/
    new_node->next = NULL;
    //4.如果列表为空，那么把新节点作为头
    if(*head_ref==NULL)
    {
        *head_ref=new_node;
        return;
    }
    //5.变量直到最后一个节点
    while(last->next!=NULL)
        last = last->next;
    //6.将最后一个节点的下一项改为新节点
    last->next = new_node;
    return;
}
//这个函数从头开始打印连接列表的内容
void printList(Node *node)
{
    while(node!=NULL)
    {
        cout<<" "<data;
        node=node->next;
    }
}
//驱动代码
int main()
{
    //从空列表开始
    Node* head=NULL;
    //插入6，以及超链接列表
    append(&head;,6);
    //在头部插入7，连接列表变为7->6->NULL
    push(&head;,7);
    //在头部插入1，连接列表变为1->7->6->NULL
    push(&head;,1);
    //插入4在末尾，连接列表变为1->7->6->4->NULL
    append(&head;,4);
    //在7之后插入8，连接列表变为1->7->8->6->4->NULL
    insertAfter(head->next,8);
    cout<<"Created Linked list is: ";
    printList(head);
    return 0;
}
//此代码由rathbhupendra贡献```