arrays - 数组和链表中的插入时间

如果一个节点是这样的c

// A linked list Node
struct Node {
    int data;
    struct Node* next;
};

在链表前面插入一个新节点如下！

void push(struct Node** head_ref, int new_data)
{
    /* 1. allocate node */
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
  
    /* 2. put in the data  */
    new_node->data  = new_data;
  
    /* 3. Make next of new node as head */
    new_node->next = (*head_ref);
  
    /* 4. move the head to point to the new node */
    (*head_ref)    = new_node;
}

你可以看到没有循环，也不需要遍历列表，因为我们有一个指向插入位置的指针（它是列表的开头或结尾）。有关更多参考，请参阅链接列表插入节点。

在 Array 中的特定位置插入元素的意思是这样的：下面是一个 C 程序，用于在 Array 中的特定位置插入元素，需要大约n/2等于复杂度的操作o(n)。

#include <stdio.h>

int main()
{
    int arr[100] = { 0 };
    int i, x, pos, n = 10;

    // initial array of size 10
    for (i = 0; i < 10; i++)
        arr[i] = i + 1;

    // print the original array
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    // element to be inserted
    x = 50;

    // position at which element
    // is to be inserted
    pos = 5;

    // increase the size by 1
    n++;

    // shift elements forward
    for (i = n-1; i >= pos; i--)
        arr[i] = arr[i - 1];

    // insert x at pos
    arr[pos - 1] = x;

    // print the updated array
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

有关更多参考，请参阅在数组中插入元素。

请注意，在链表中的所需位置插入节点也需要n/2操作，O(n)如下所示：

void insertPos(Node** current, int pos, int data)
{
    // This condition to check whether the
    // position given is valid or not.
    if (pos < 1 || pos > size + 1)
        cout << "Invalid position!" << endl;
    else {
 
        // Keep looping until the pos is zero
        while (pos--) {
 
            if (pos == 0) {
 
                // adding Node at required position
                Node* temp = getNode(data);
 
                // Making the new Node to point to
                // the old Node at the same position
                temp->next = *current;
 
                // Changing the pointer of the Node previous
                // to the old Node to point to the new Node
                *current = temp;
            }
            else
              // Assign double pointer variable to point to the
              // pointer pointing to the address of next Node
              current = &(*current)->next;
        }
        size++;
    }
}

这两个最后的算法都需要循环，这意味着o(n)。

有关更多参考，请参阅在链表中的特定位置插入节点。

arrays - 数组和链表中的插入时间

问题描述

解决方案

推荐阅读