Clojure: Listas e vetores

Guilherme Lima
Guilherme Lima

Compartilhe

Listas e vetores são estruturas de dados sequenciais ordenadas que fazem parte da vida daqueles que desenvolvem. Porém, embora sejam semelhantes, internamente essas duas estruturas de dados são muito diferentes e vou te mostrar neste artigo.

Vetores

Observe a próxima imagem. Você pode pensar em um vetor como semelhante a uma matriz, um grande pedaço de memória contínua. Basta colocar o primeiro item no primeiro slot do bloco, ou seja, no primeiro espaço disponível da memória, o segundo elemento no segundo bloco de memória e assim por diante.

Imagem de 4 quadrados, um ao lado do outro, com cada um apontando para um dado. No primeiro, o valor armazenado é 1, no segundo a palavra dois, no terceiro o número 3 e no quarto a palavra quatorze. Além disso, há um quadrado maior com o texto espaço extra, indicando que novos valores podem ser armazenados

Listas

As listas, por outro lado, são implementadas como listas vinculadas - por isso o nome (suspeitei desde o princípio!).

Na imagem abaixo, temos uma lista com uma série de objetos de dois slots, em que o primeiro recebe o dado a ser armazenado e o segundo aponta para o próximo slot.

Imagem com dois quadrados ligados. O primeiro deles aponta para o valor 1 e o segundo aponta para o segundo quadro, também chamado de slot. No segundo slot, temos a palavra dois armazenada, e o segundo slot aponta para o próximo grupo.

Um slot contém uma referência a algum item de dados, enquanto o segundo slot aponta para o próximo objeto na lista.

Esses objetos de lista de dois slots têm, na verdade, três slots. O terceiro slot é uma contagem do número de itens na lista. Isso permite que a função de contagem faça seu trabalho sem ter que percorrer toda a lista dizendo: um elemento, dois elementos, três elementos e assim por diante.

Essas duas maneiras de organizar dados possuem pontos fortes muito diferentes. Vamos descobrir?

Quais as diferenças?

É muito mais fácil - e mais rápido - adicionar um novo elemento à frente de uma lista do que um vetor com uma lista. Basta alocar um novo item de dois slots, e em seguida apontar um slot para o seu elemento e o outro para a lista original.

Como os vetores dependem de blocos de memória, adicionar um novo elemento à frente envolve mais código e pode exigir a alocação de mais memória.

Por outro lado, adicionar um novo item ao final de um vetor pode ser rápido se houver espaço no final do bloco de memória.

Exemplo prático

A diferença de implementação entre listas e vetores aparece muito claramente com a função conj.

Lembre-se de que conj pega uma coleção e um elemento e retorna uma nova coleção com todas as coisas do original, mais o novo elemento.

Vamos criar uma lista e um vetor, com os seguintes elementos: 1, "dois", 3 e "quartorze", como mostra o código código a seguir:

(def lista-teste '(1 "dois" 3 "quatorze"))
(def vetor-teste [1 "dois" 3 "quatorze"])

Agora vamos adicionar um elemento na lista e no vetor:

(println "lista" (conj lista-teste 2048))
(println "vetor" (conj vetor-teste 2048))

Observe a saída da nova lista e do novo vetor:

lista (2048 1 dois 3 quatorze)
vetor [1 dois 3 quatorze 2048]

Conclusão

Significativamente, conj está ciente dos diferentes pontos fortes de listas e vetores e age de acordo: ele alinha o novo elemento com eficiência na frente das listas, mas no final dos vetores. E aí, curtiu?

Para aprender mais sobre Clojure, veja:

Veja outros artigos sobre Programação