Single Linked Lists

Você pode chamar de lista ligada, lista encadeada, eu vou chamar de linked list.

A grande diferença linked list e arrays é que linked list não são indexadas, não tem como buscar o sexto elemento, ou o segundo e etc. A linked list funciona como estações do monotrilho, onde cada estação é um valor e existe uma conexão entre uma estação e outra, formando uma linha.

E por isso podemos declarar a Linked list como uma estrutura de dados linear.

O exemplo com o monotrilho é bem específico exatamente porque vou falar de doubly linked list também e essa tem mais a ver com linhas de metrô.

N_a linked list_ cada Node ou nó irá representar uma estação, cada node tem uma propriedade que pode ser um int, string ou qualquer outro tipo. Nesse caso será uma string e a propriedade são as estações do monotrilho.

A segunda parte de um Node é um ponteiro que faz a ligação apontando para o próximo node, no nosso exemplo, a próxima estação, criando assim uma ligação entre todos os nós.

No nosso exemplo enquanto os Nodes são as estações, o Monotrilho vai representar a própria linked list.

Outras duas partes importante nas linked list são o headNode e o tail o head é o primeiro item que entra na lista e o tail o último, no caso do tail o pointer dele aponta para nil, o que representa o fim da lista. Essas duas partes também são importantes pois são referência para a criação dos métodos que precisaremos usar na linked list.

Claro que uma estrutura da de dados não é nada seus seus métodos, e vamos implementá-los aqui. Para entender por completo é necessário que você saiba como usar ponteiros, então vou deixar alguns recursos aqui pra você consultar antes de começar a falar de código.

Go by Example: Pointers

Aprenda Go: O que são ponteiros?

A estrutura

O struct Estação é o que vai representar os nós dessa Linked List, então temos a propriedade que é o valor nome e proximaEstacao que faz a ligação entre os nós apontando para o próximo Node.

Com a struct Monotrilho temos agora como setar a primeiraEstacao (head) que é onde começa a linked list, então primeiraEstacao vai apontar para Estacao (Node) que é onde fica a proximaEstacao.

Adicionar um head

O método AddPrimeiraEstacao vai adicionar um valor ao primeiro Node que é primeiraEstacao.

AddPrimeiraEstacao usa a struct Monotrilho como receiver e possui um parâmetro string. Instanciamos Estacao e atribuímos o parâmetro a propriedade nome.

Agora linha.primeiraEstacao recebe a referencia de memória presente na Estacao instanciada.

IterateList

Basicamente o que faríamos com um for statement em um array porém usando as propriedades das structs para percorrer a lista de Estações.

Enquanto a Estacao instanciada for diferente de nil (representação do fim da lista) estacao é igual a proximaEstacao análogo ao i++.

LastNode

O método UltimaEstacao do Monotrilho retorna o node no final da linha. A linha é percorrida para verificar se proximaEstacao é nil caso seja a variável ultimaEstacao recebe o valor atual de estacao feito no for.

AddToEnd

O método AdicionaEstacao adiciona um node no final da linha.

Primeiro buildamos um Node, nome = parâmetro e o proximaEstacao que recebe nil pois como essa estação é adicionada no final da linha ela precisa ser um tail.

Em seguida encontramos o fim da linha atual reutilizando UltimaEstacao() o método criado anteriormente e setamos seu valor com o a estacao criada.

NodeWithValue

O método ProcuraEstacao do Monotrilho retorna o node com o valor do parâmetro. A lista é percorrida e verificada para ver se o valor da propriedade é igual ao parâmetro caso contrário retorna nil.

AddAfter

O método AddProximaEstacao adiciona um Node após uma Estacao específica.

O método AddProximaEstacao do Monotrilho possui dois parâmetros, onde o primeiro é o node de referencia e o segundo o novo node a ser adicionado na posição seguinte a referência.

Uma estacao com o valor nomeDaEstacaoAnterior é recuperada reutilizando o método ProcuraEstacao().

Um node (parâmetro 2) é criado e adicionada após o retorno de ProcuraEstacao().

RemoveNode

O método RemoveEstacao verifica se o primeiraEstacao é nil, caso o Monotrilho esteja vazio.

Em seguida se a propriedade do primeiraEstacao for a mesma do parâmetro então proximaEstacao é movido para primeiraEstacao assim ocupando a posição do Node removido.

Em seguida uma nova condição onde estacaoAtual é setada como head para que possamos verificar os itens além da primeiraEstacao e assim caso seja encontrado fazemos a atribuição para a esquerda novamente alocando os nodes seguintes a posição do node removido.

SizeList

TamanhoDaLinha faz o mesmo papel que len() em estruturas de array retornando a quantidade de Nodes presentes no Monotrilho.

FuncMain

Depois disso tudo você pode utilizar os métodos para construir a sua LinkedList como preferir.

Output

<<<<<<< HEAD

A versão em código no repositório não utiliza a os mesmos exemplos com o Monotrilho, os nomes no arquivo original contam com os nomes comuns usados na estrutura de LinkeList.

A versão em código no repositório não utiliza a os mesmos exemplos com o Monotrilho, os nomes no arquivo original contam com os nomes comuns usados na estrutura de LinkeList.

LinkedList vs Arrays

• Um array é a estrutura de dados que contém uma coleção de elementos de dados de tipo semelhante, enquanto a linked list é considerada como uma estrutura de dados não primitiva contém uma coleção de elementos vinculados não ordenados conhecidos como nodes.

• No array, os elementos pertencem a índices, ou seja, se você deseja o quarto elemento, deve escrever o nome da variável com seu índice ou localização dentro do colchete.

• Em uma linked list, porém, você tem que começar do head e ir trabalhando até chegar ao quarto elemento. O acesso a um elemento em um array é rápido, enquanto a linked list leva um tempo linear, portanto, é um pouco mais lento.

• Operações como insert e delete em arrays consomem muito tempo. Por outro lado, o desempenho dessas operações em linked lists é rápido.

• Arrays são de tamanho fixo. Em contraste, as linked lists são dinâmicas e flexíveis e podem expandir e diminuir seu tamanho.

• Em um array, a memória é atribuída durante o tempo de compilação, enquanto uma linked list é alocada em tempo de execução.

• Os elementos são armazenados consecutivamente na memória com arrays, enquanto que são armazenados aleatoriamente em linked lists.

Tudo em relação as estruturas terão tradeoff então a aplicação de cada uma vai depender da necessidade do desenvolvedor.