Agora temos uma sequência ordenada de vários elementos (em ordem crescente), e temos que inserir um novo elemento. Por favor, insira o novo elementonúmero ordenado subsequente.

Vamos implementar separadamente:

1. Implementação de uma lista simples
2. Simulação de uma lista simples usando um array

por que usar um array para simular uma lista simples

1. Localidade de memória otimizada: os elementos no array são armazenados contíguamente na memória, o que permite que a accionamento de elementos seja mais eficiente, aproveitando o cache.
2. Menor fragmentação de memória: os elementos na lista simples são distribuídos ao longo da memória, o que pode levar a fragmentação de memória. O array pode garantir uma utilização mais eficiente de memória.
3. Simplificação do código: em algumas situações, é possível simplificar o código de manipulação de listas (como insert, remove, etc.) usando um array, já que o índice pode ser usado diretamente para acessar e modificar elementos.
4. Tamanho fixo da estrutura: se sabemos o tamanho máximo da lista, podemos pré definir um tamanho suficiente para o array, evitando o runtime de frequentes allocation e releases de memória.
5. Aplicativos específicos: em certas situações específicas, como ipmlementação de filas ou pilhas, usar um array pode ser mais adequado.

Quando estamos construindo uma lista simples, temos que inserir um novo nó como quaisquer?

Aqui está a implementação complete de uma lista simples:

#include <iostream>
using namespace std;

// Define a estrutura do nó
struct Node {
    int data;           // Dados do nó
    Node* next;         // Pointer para o nó next
};

Node* head, * p, * r;

int main() {
    int n;
    cin >> n;

    // Cria um novo nó inicial (head)
    head = new Node();
    head->next = NULL; // O next do head é inicialmente NULL
    r = head;

    // Cria os n elementos da lista
    for (int i = 1; i <= n; i++) {
        p = new Node(); // Cria um novo nó
        cin >> p->data; // Digitar o valor do nó
        p->next = NULL; // O next do nó é inicialmente NULL
        r->next = p;    // Link o novo nó ao final da lista
        r = p;          // Move r para o novo nó
    }

    int t;
    cin >> t; // Digitar o novo valor para ser inserido

    Node* q = new Node();
    q->data = t;
    q->next = NULL;

    // Caso de inserção ao início
    if (head->next == NULL || head->next->data > t) {
        q->next = head->next; // O next do novo nó é o nó atual
        head->next = q;       // O head aponta para o novo nó
    } else {
        // Encontrar a posição correta para inserir o novo nó
        p = head->next; // p aponta para o primeiro nó não-vazio
        while (p->next != NULL && p->next->data <= t) {
            p = p->next; // Encontrar o nó next que é maior do que t
        }
        // Insere o novo nó após p
        q->next = p->next;
        p->next = q;
    }

    // Imprimir os elementos da lista
    p = head->next; // Começar do nó inicial
    while (p != NULL) {
        cout << p->data << " "; // Imprimir os dados
        p = p->next; // Move para o nó next
    }
    cout << endl;

    return 0;
}

Simulação de uma lista simples usando um array

Aqui está a implementação usando um array para simular uma lista simples:

O código-fonte-fonte para a lista simples e sua simulação em GitHub