Introdução
Estás a trabalhar num projeto para desenvolver um sistema de horários para uma rede ferroviária movimentada.
Foi-te pedido que desenvolvesses um protótipo para as rotas dos comboios no sistema de horários. Cada rota é composta por uma sequência de estações onde um determinado comboio para.
Instruções
A tua equipa decidiu usar uma lista duplamente ligada para representar cada rota de comboio no horário.
Cada estação ao longo da rota do comboio será representada por um nó na lista ligada.
Não precisas de te preocupar com as horas de chegada e de partida nas estações.
Cada estação será simplesmente representada por um número.
As rotas podem ser estendidas, acrescentando estações ao início ou ao fim de uma rota.
Também podem ser encurtadas, removendo estações do início ou do fim de uma rota.
Por vezes, uma estação é encerrada e, nesse caso, tem de ser removida da rota, mesmo que não esteja no início nem no fim da rota.
O tamanho de uma rota não se mede pela distância que o comboio percorre, mas pelo número de estações onde para.
A lista ligada é uma estrutura de dados fundamental da informática, usada frequentemente na implementação de outras estruturas de dados.
Como o nome sugere, é uma lista de nós ligados entre si.
É uma lista de "nós", em que cada nó se liga ao seu vizinho ou vizinhos.
Numa lista ligada simples, cada nó liga-se apenas ao nó que se lhe segue.
Numa lista duplamente ligada, cada nó liga-se tanto ao nó que vem antes como ao nó que vem depois.
Se quiseres aprofundar os teus conhecimentos sobre listas ligadas, espreita este artigo, que as explica com desenhos muito claros.
Implementação
Vais escrever uma implementação de uma lista duplamente ligada.
Implementa um Node para guardar um valor e ponteiros para os nós seguinte e anterior.
Depois, implementa uma List que guarda referências ao primeiro e ao último nó e oferece funções para adicionar e remover itens.
O teu Node deve ter os seguintes campos e métodos:
-
Value: o valor do nó (vamos usar any).
-
Next() *Node: ponteiro para o nó seguinte.
-
Prev() *Node: ponteiro para o nó anterior.
Deves ter uma função NewList() que cria e devolve uma List:
-
NewList(args ...any) *List: cria uma nova lista ligada preservando a ordem dos valores.
A tua List deve ter os seguintes métodos:
-
First() *Node: devolve um ponteiro para o primeiro nó (cabeça).
-
Last() *Node: devolve um ponteiro para o último nó (cauda).
-
Push(v any): insere um valor no fim da lista.
-
Pop() (any, error): remove um valor do fim da lista.
-
Unshift(v any): insere um valor no início da lista.
-
Shift() (any, error): remove um valor do início da lista.
-
Reverse(): inverte a lista ligada.
Fonte
Tópico clássico da informática
