链表插入

Harshit Jindal 2023年1月30日 2021年3月21日
  1. 链表插入算法
  2. 链表插入图
  3. 链表插入实现
  4. 链表插入算法的复杂度
链表插入

在本文中,我们将学习如何在链表中插入节点。我们可以看到出现了 4 种不同的情况。

  1. 我们要在链接列表的开头之前插入一个节点。此操作类似于堆栈中的推入操作。
  2. 我们要在链接列表的末尾(即尾节点旁边)插入一个节点。
  3. 我们想在链接列表的第 i 个位置插入一个节点。
  4. 我们有该节点的引用,之后我们要插入新节点。

链表插入算法

head 为指向链表第一个节点的指针,令 x 为要插入链表中的数据。

在链接列表 push() 的开头插入节点

  • 用数据 x 创建一个新节点 temp
  • temp->next 设置为 head,以在 head 之前插入 temp
  • temp 设置为链接列表的开头。

在链接列表 append() 的末尾插入节点

  • 用数据 x 创建一个新节点 temp
  • 初始化指向 headtail
  • 如果链接列表为空,则将 temp 设置为链接列表的 head,然后返回。
  • 否则,迭代链接列表的末尾,使 tail->next!=NULL,以便你到达最后一个元素
  • tail->next 设置为 temp

在链接列表 insertNpos()i-th 位置处插入节点

  • 如果位置 pos<=0,则返回;否则返回 0。
  • 如果 pos==0 并且 head 为空,则创建一个数据为 x 的新节点并将其设置为 head
  • 如果 pos==1,则调用 push()
  • 另外,用数据 x 创建一个新节点 temp
  • 初始化指向 headcurr
  • pos-- 时,执行以下操作。
    • 如果 pos==1

      • 如果 curr 不是 NULL
        • temp->next 设置为 curr->next,以便在 curr 之后插入 temp
        • curr->next 设置为 temp,以将 curr 连接到 temp
      • 返回;
    • 否则将 curr 设置为 curr->next

在给定节点的引用旁边插入节点 - insertAfter()

  • 如果 prev==NULL,则返回;
  • 用数据 x 创建一个新节点 curr
  • curr->next 指向 prev->next 以在 prev 之后添加新节点。
  • prev->next 指向 curr 以完成插入。

链表插入图

假设我们有一个节点 temp,其数据值等于 5,我们想将其插入链表中。让我们考虑所有 4 种情况,并说明上述算法是如何工作的。

在链接列表的开头插入节点 - push()

  • temp 的指针设置为 head
  • head 指向 temp

在链接列表的开头插入节点

在链接列表 append() 的末尾插入节点

  • curr 指向 head,数据为 2
  • curr 设置为 curr->next,并将其移动到数据为 3 的节点。
  • curr 设置为 curr->next,并将其移动到数据为 4 的节点。
  • 退出 while 循环并将 curr->next 设置为 temp

在链接列表的末尾插入节点

在链接列表的 i-th 位置处插入节点 - insertNpos()

我们将节点插入到位置 3

  • curr 指向 head,数据为 1pos=pos-1=2
  • curr 设置为 curr->next,并将其移动到数据为 3pos=pos -1=1 的节点。
  • temp->next 设置为 curr->next,以便在 curr 之后插入 temp。
  • curr->next 设置为 temp,以在 currcurr->next 之间完成 temp 的插入。

在链接列表的特定位置插入节点

在给定节点 insertAfter() 的引用旁边插入节点

  • temp->next 设置为 prev->next,以在 prevprev->next 之间插入 temp
  • prev->next 设置为 temp 以完成插入。

在给定节点的引用旁边插入节点

链表插入实现

#include <bits/stdc++.h>
using namespace std;

class Node {
    public:
        int data;
        Node* next;
        Node(int x) {
            this->data = x;
            this->next = NULL;
        }
};

void push(Node** head, int x)
{
    Node* temp = new Node(x);
    temp->next = (*head);
    (*head) = temp;
}

void insertAfter(Node* prev, int x)
{
    if (prev == NULL) {
        return;
    }
    Node* curr = new Node(x);
    curr->next = prev->next;
    prev->next = curr;
}

void printList(Node* head)
{
    Node*curr = head;
    while (curr != NULL) {
        cout << curr->data << " ";
        curr = curr->next;
    }
}
void insertNpos(Node**head, int x, int pos) {
    if (pos <= 0) {
        return;
    }
    if (!head && pos == 1) {
        *head = new Node(x);
    }
    else if (pos == 1) {
        push(head, x);
    }
    Node* temp = new Node(x);
    Node*curr = *head;
    while (pos--) {
        if (pos == 1) {
            if (curr) {
                temp->next = curr->next;
                curr->next = temp;
            }
            return;
        }
        curr = curr->next;
    }
}
void append(Node** head, int x)
{
    Node* temp = new Node(x);
    Node *tail = *head;
    if (*head == NULL)
    {
        *head = temp;
        return;
    }
    while (tail->next != NULL)
        tail = tail->next;
    tail->next = temp;
    return;
}

int main()
{
    Node* head = new Node(1);
    head -> next = new Node(2);
    printList(head); cout << "\n";
    push(&head, 3);
    push(&head, 4);
    printList(head); cout << "\n";
    append(&head, 5);
    printList(head); cout << "\n";
    insertAfter(head->next->next, 6);
    printList(head); cout << "\n";
    insertNpos(&head, 24, 2);
    printList(head);
    return 0;
}

链表插入算法的复杂度

时间复杂度

  • 平均情况

要将节点插入链表中的第 i 个位置,我们必须访问 i 个节点。因此,时间复杂度约为 O(i)。而且我们在链表中有 n 个节点,因此平均情况下的时间复杂度为 O(n/2)O(n)。时间复杂度约为 O(n)

  • 最佳情况

最好的情况是,当我们想在链表的开头插入一个节点,或者在插入站点之前有对该节点的引用时。最佳情况下的时间复杂度是 O(1)

  • 最坏情况

最差的时间复杂度是 O(n)。这与平均情况下的时间复杂度相同。

空间复杂度

该插入算法的空间复杂度为 O(1),因为除 curr 指针外不需要其他空间。

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相关文章 - Data Structure

相关文章 - Linked List