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

Passo 1

Vamos começar entendendo o que o enunciado está pedindo. Precisamos implementar o Tipo Abstrato de Dados (TAD) para Listas Duplamente Ligadas de inteiros. Isso envolve criar uma estrutura de dados onde cada elemento (nó) aponta tanto para o próximo quanto para o nó anterior na lista. Além disso, devemos implementar a operação de inserir um nó em uma posição específica. Para resolver isso, vamos precisar entender como funcionam as listas duplamente ligadas e como manipulamos os ponteiros para inserir corretamente um novo nó na posição desejada.

Passo 2

Primeiro, vamos definir como será a estrutura de um nó em uma lista duplamente ligada. Cada nó deve conter um valor inteiro e dois ponteiros: um que aponta para o nó anterior e outro para o próximo nó na lista.

Passo 3

Em seguida, vamos definir a estrutura da própria lista. A lista deve manter referência ao seu primeiro nó (head) e, opcionalmente, ao último nó (tail) para facilitar operações no final da lista. Também é útil manter um contador do número de elementos (size) na lista.

Passo 4

Agora, vamos focar na operação de inserir um nó em uma posição específica. Para isso, precisamos:
  1. Verificar se a posição é válida (ou seja, entre 0 e o tamanho atual da lista).
  2. Criar um novo nó com o valor desejado.
  3. Ajustar os ponteiros dos nós adjacentes para incluir o novo nó na posição correta.

Passo 5

Vamos implementar isso em pseudocódigo para facilitar a compreensão. Suponhamos que estamos usando uma linguagem similar a C.
\begin{verbatim}
struct Node {
    int data;
    Node* prev;
    Node* next;
};

struct DoublyLinkedList {
    Node* head;
    Node* tail;
    int size;
};

// Função para inserir um nó em uma posição específica
void insertAtPosition(DoublyLinkedList* list, int position, int value) {
    if (position < 0 || position > list->size) {
        printf("Posição inválida\n");
        return;
    }
    
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->prev = NULL;
    newNode->next = NULL;
    
    if (position == 0) { // Inserir no início
        newNode->next = list->head;
        if (list->head != NULL)
            list->head->prev = newNode;
        list->head = newNode;
        if (list->size == 0)
            list->tail = newNode;
    }
    else if (position == list->size) { // Inserir no final
        newNode->prev = list->tail;
        if (list->tail != NULL)
            list->tail->next = newNode;
        list->tail = newNode;
    }
    else { // Inserir no meio
        Node* current = list->head;
        for (int i = 0; i < position; i++)
            current = current->next;
        newNode->prev = current->prev;
        newNode->next = current;
        current->prev->next = newNode;
        current->prev = newNode;
    }
    
    list->size++;
}
\end{verbatim}

Passo 6

Vamos analisar o que fizemos no código:
  • Verificação de posição: Garantimos que a posição onde queremos inserir o novo nó seja válida.
  • Criação do novo nó: Alocamos memória para o novo nó e definimos seu valor.
  • Inserção no início: Se a posição for 0, atualizamos o head da lista e ajustamos o prev do antigo primeiro nó.
  • Inserção no final: Se a posição for igual ao tamanho atual da lista, atualizamos o tail e o next do antigo último nó.
  • Inserção no meio: Percorremos a lista até a posição desejada e ajustamos os ponteiros prev e next dos nós adjacentes para inserir o novo nó.

Resposta

Com isso, implementamos com sucesso a operação de inserir um nó em uma posição específica em uma lista duplamente ligada de inteiros. A função insertAtPosition verifica a validade da posição, cria um novo nó e ajusta os ponteiros dos nós existentes para manter a integridade da lista.

Exercícios relacionados