Desafio 2: Implemente o TAD Listas circulares simples. Deve ter as operações abaixo: (2 V)
b. Inserir nó numa posição específica

Passo 1

Beleza, vamos lá! O enunciado pede para a gente implementar o TAD (Tipo Abstrato de Dados) de Listas Circulares Simples, especificamente a operação de inserir um nó numa posição específica. Então, vamos trabalhar com estruturas de listas onde o último elemento aponta de volta para o primeiro, formando um ciclo. Para isso, vamos precisar entender como navegar na lista e ajustar os ponteiros para inserir o novo nó na posição que a gente quer.

Passo 2

Primeiro, vamos lembrar como é uma lista circular simples. Cada elemento (ou nó) tem dois componentes principais: o valor que ele guarda e um ponteiro para o próximo nó. O último nó sempre aponta para o primeiro, garantindo que a lista seja circular. Para inserir um novo nó numa posição específica, precisamos:
  1. Criar o novo nó com o valor que queremos.
  2. Navegar até a posição anterior onde queremos inserir o novo nó.
  3. Ajustar os ponteiros para que o novo nó seja ligado corretamente na lista.

Passo 3

Vamos detalhar cada um desses passos. Primeiro, criar o novo nó é bem direto: alocamos memória para ele, definimos o valor e inicialmente apontamos seu próximo para NULL. Depois, se a lista estiver vazia, ou seja, não tiver nenhum nó, o novo nó vai apontar para ele mesmo, já que é circular. Caso contrário, temos que encontrar a posição anterior onde vamos inserir o novo nó.

Passo 4

Para navegar até a posição anterior, começamos no primeiro nó e avançamos pelos ponteiros até chegarmos na posição imediatamente antes da onde queremos inserir. É importante verificar se a posição desejada é válida, ou seja, não ultrapassa o tamanho da lista.

Passo 5

Depois de chegar na posição anterior, vamos ajustar os ponteiros. O próximo do nó anterior vai apontar para o novo nó, e o próximo do novo nó vai apontar para o nó que estava originalmente nessa posição. Dessa forma, mantemos a estrutura circular sem perder nenhum nó.

Passo 6

Vamos colocar isso tudo em código para ficar mais claro. Aqui está um exemplo em C:
#include <stdio.h>
#include <stdlib.h>

// Definição do nó
typedef struct Nodo {
    int valor;
    struct Nodo* proximo;
} Nodo;

// Função para inserir na posição específica
void inserir(Nodo** head, int valor, int pos) {
    Nodo* novo = (Nodo*)malloc(sizeof(Nodo));
    novo->valor = valor;
    
    if (*head == NULL) {
        // Lista vazia: novo nó aponta para si mesmo
        novo->proximo = novo;
        *head = novo;
    } else if (pos == 1) {
        // Inserir no início
        Nodo* temp = *head;
        while (temp->proximo != *head) {
            temp = temp->proximo;
        }
        novo->proximo = *head;
        temp->proximo = novo;
        *head = novo;
    } else {
        // Inserir em posição específica
        Nodo* temp = *head;
        for (int i = 1; i < pos-1 && temp->proximo != *head; i++) {
            temp = temp->proximo;
        }
        novo->proximo = temp->proximo;
        temp->proximo = novo;
    }
}

// Função para imprimir a lista
void imprimir(Nodo* head) {
    if (head == NULL) return;
    Nodo* temp = head;
    do {
        printf("%d ", temp->valor);
        temp = temp->proximo;
    } while (temp != head);
    printf("\n");
}

int main() {
    Nodo* head = NULL;
    inserir(&head, 10, 1); // Inserir 10 na posição 1
    inserir(&head, 20, 2); // Inserir 20 na posição 2
    inserir(&head, 15, 2); // Inserir 15 na posição 2
    imprimir(head); // Deve imprimir: 10 15 20
    return 0;
}

Resposta

Seguindo os passos acima, conseguimos implementar a operação de inserir um nó numa posição específica em uma lista circular simples. No exemplo de código em C, a função inserir trata casos onde a lista está vazia, inserção no início e inserção em posições intermediárias, mantendo sempre a estrutura circular da lista. Quando executamos o programa, a lista resultante após as inserções será: 10 15 20.

Exercícios relacionados