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
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:
- Verificar se a posição é válida (ou seja, entre 0 e o tamanho atual da lista).
- Criar um novo nó com o valor desejado.
- 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 oprev
do antigo primeiro nó. - Inserção no final: Se a posição for igual ao tamanho atual da lista, atualizamos o
tail
e onext
do antigo último nó. - Inserção no meio: Percorremos a lista até a posição desejada e ajustamos os ponteiros
prev
enext
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.