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

2020-12-10 22:08 作者:C语言编程__Plus 0人读过 | 我要投稿

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

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

C ++

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

1）在链表的最前面

2）在给定节点之后。

3）在链接列表的末尾。

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

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

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

C++

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

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

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

C ++

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

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

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

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

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

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

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

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

C ++

#include <bits/stdc++.h>

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<<"the given previous node cannot be NULL";

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

        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<<"Created Linked list is: ";

    printList(head);

    return 0;

}

C语言

#include <stdio.h>

#include <stdlib.h>

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;

}