Arrays e listas encadeadas
Hoje eu vou dar continuidade sobre a leitura que ando fazendo sobre o meu livro de algoritmos.
Sobre o livro
O livro em questão se trata deste aqui:
Pelo que eu li, eu poderia dizer que o autor se esforçou para produzir uma obra bem didática. Suas explicações são muito boas e ele usa bastante de figuras para embasar seus exemplos. Neste livro ele não aborda todos os algoritmos, mas mesmo assim apresenta os principais como meio de te introduzir neste conhecimento.
Se você já mexe com programação a algum tempo, se já chegou a desenvolver vários scripts, sistemas pequenos ou similares. Eu lhe aconselharia a compra desta obra caso você se interesse por isso. E caso você realmente deseja comprar eu deixarei abaixo o meu link de afiado da amazon para a compra deste livro logo abaixo.
Mas bem, vamos ao que interessa!
Desta vez o assunto será sobre arrays e listas encadeadas. Se eu te perguntasse a diferença entre elas, você saberia me dizer?
Então, antes de entender um pouco disso, precisamos ter claro em nossa mente a ideia básica sobre a forma como computadores armazenam seus dados.
Imagine um computador como um móvel contendo inúmeras gavetas. Tais gavetas serão o local onde vamos guardar as nossas coisas.
Um computador é capaz de armazenar informações que são estruturadas de forma similar a este móvel da imagem. Pois cada quadradinho é como se fosse um espaço de memória onde podemos armazenar algum tipo de informação.
Um bom exemplo de memória pode ser exemplificado pela imagem acima também.
Assimile em sua mente que uma memória é apenas um conjunto de quadradinhos que podem ser ocupados com algum tipo de informação.
Encare neste exemplo acima como se os quadrinhos em branco fossem espaços vagos na memória. Os coloridos são espaços ocupados por algum tipo de informação.
Pela imagem vocês já podem observar que dependendo de como estas informações são organizadas, podemos ter espaço sobrando ou não.
O que é um array
Um array é uma estrutura de dados capaz de armazenar informações de forma sequencial. Isso significa que se eu adicionar um elemento no meu array, este elemento entrará na próxima posição seguindo uma estrutura de armazenamento sequencial.
Veja um exemplo de um array.
Este array contém elemento que vão de dez a cem. E cada um destes elementos estão armazenados num determinado endereço que se inicia em zero e vai até o nove.
A sua natureza sequencial se deve ao fato de que se for necessário adicionar novos elementos, o próximo (por exemplo, o número 110) seria armazenado numa posição posterior ao último elemento. Então teríamos um array com o valor 110 na posição 10. Pois o valor 100 se encontra na posição 9 que é uma posição anterior ao último elemento inserido.
Problema de armazenamento com os arrays
O problema de armazenamento com os arrays é que para o sistema de armazenamento no geral, ou seja, o espaço que será alocado para este array precisa ser um espaço de tamanho fixo.
Vejamos novamente o exemplo do móvel com suas gavetas. Observe novamente a imagem abaixo:
Nestas gavetas de exemplo vocês podem observar que o seu espaço é finito. Ou seja, existe um limite para a quantidade de coisas que podem ser armazenadas neste móvel.
Da mesma forma, numa estrutura computacional, também existe um limite de espaço em disco.
Se todo o nosso espaço de armazenamento fosse apenas este móvel de exemplo, na hora de separarmos um espaço para o armazenarmos um array, este array não poderia passar do tamanho 8. Pois como vocês podem ver na imagem, para cada gaveta, temos apenas 8 espaços de armazenamento.
Então, se eu declarar um array de tamanho 3, este array vai estar ocupando 3 posições da minha gaveta. Eu poderia criar outros arrays, mas eles não poderiam ocupar mais do que 8 posições dentro de uma gaveta.
Então o que aconteceria se eu criasse um array que ocupasse os três primeiros espaços da gaveta com cartas dentro dele e logo em seguida criasse um outro array que ocupasse os próximos 3 espaço da gaveta com anéis dentro dele.
A image de exemplo seria mais ou menos assim:
Observe que temos um array de cartas ocupando as três primeiras posições. E logo em seguida um outro array de anéis ocupam as próximas posições.
O nosso array teria uma estrutura de peseudo código mais ou menos assim:
[carta 1, carta 2, carta 3, anel 1, anel 2, anel 3, espaço vazio, espaço vazio]
Se por algum motivo for necessário adicionar mais uma nova carta, nós não conseguiríamos, pois a próxima posição já está ocupada por um anel conforme a imagem acima.
Por causa disso a estrutura de array precisa ser declarada com mais espaços em branco para garantir que suas próximas posições não sejam ocupadas.
Porém esta abordagem não é muito prática, pois ela pode acarretar numa declaração de espaço desnecessário. Pois imagine que fosse declarado 6 espaços da gaveta para armazenarmos 6 cartas. Mas na prática, armazenamos apenas 4 espaços. Nisso, acabou havendo um desperdício de dois espaços de memória. Pois como eles estão reservados para as próximas cartas, qualquer outra lista que você for declarar, não vai conseguir ocupar este espaço que ficará livre atoa.
Para resolver este tipo de problema. Podemos usar as listas encadeadas
O que é uma lista encadeada
Uma lista encantada é uma estrutura de dados mais complexa pois cada elemento do array, vai conter uma estrutura de dados capaz de armazenar o endereço do seu próximo elemento. Eles não estão ligados de forma sequencial, a sua ligação não esta dependente da próxima posição do ele. Pois como o próprio elemento consegue armazenar a posição do seu próximo elemento. Ele vai conseguir acessá-lo sem que o elemento esteja vizinho a ele.
Veja um exemplo de uma listagem encadeada.
Os números acima do retângulo azul são seus endereços de memória. Lembra do que falei a respeito sobre endereço. É similar ao nosso mundo real quando precisamos saber o endereço de uma casa para encontrá-la.
O número 4 representa o valor armazenado no primeiro item da lista. E além do seu número, está estrutura de dados também precisa armazenar o endereço do próximo elemento da list. Pois somente desta forma ele vai conseguir acessar o próximo elemento.
Então o elemento 4 possui um endereço de número 560, e dentro dele, existe o armazenamento do endereço do próximo elemento. Que no caso se trata do endereço 750 que é onde está armazenado o número 9.
Este número 9 por sua vez, possui dentro de si o número de endereço do elemento 6 que e 650 que por sua vez possui o número de endereço 3 e assim por diante.
Qual sua vantagem em relação ao array sequencial?
Sua grande vantagem é que por ter a referência do próximo elemento de forma dinâmica, ele não precisa estar fortemente acoplado como na estrutura de array sequencial.
Lembra do exemplo anterior? Vou exibir novamente a imagem da gaveta com suas cartas e anéis armazenados.
Na estrutura de array nós não poderíamos armazenar a próxima carta por causa de seus próxima posição já estar ocupada por um anel. A própria natureza sequencial da estrutura de array faz com que não seja possível inserir um novo elemento numa posição que já está ocupada.
Mas por outro lado se estivermos usando uma estrutura de lista encadeada, este problema não será mais uma pedra no nosso sapato.
Pois como na lista encadeada nós armazenarmos na nossa estrutura o endereço da próximo elemento. O fato da próxima posição já estar armazenada não será um problema. Pois nós vamos encontrar a próxima posição livre dentro da memória e nesta nova posição nós vamos armazenar o nosso valor. Está nova posição vai possuir um endereço próprio de memória. E tudo que vamos precisar fazer é apenas armazenar no elemento anterior o endereço deste novo elemento.
Sendo assim. O penúltimo elemento da list vai ter armazenado dentro de si o endereço do último elemento inserido na lista. Dessa forma nós conseguimos garantir que todos os elementos da lista estejam encadeadas, mesmo que cada elemento esteja em endereços de memória completamente distantes um dos outros.
Bem galera, este artigo foi apenas para dar uma luz de conhecimento base sobre o assunto. Encare isso como uma porta de entrada para uma longa jornada de conhecimento.
