Sign in to follow this  
Wagner_Araxa

Listas

Recommended Posts

Bom, listas estão em basicamente 4 categorias:

A primeira, mais geral, é onde você guarda valores e acessa, remove e insere qualquer posição.

Ela útil para muita coisa, como algoritmos de ordenação e busca.

A segunda, é a pilha que pemite a remoção e a inserção apenas em uma ponta e possivelmente restringe o acesso a apenas essa ponta também.

Ela é útil para recursão (todo algoritmo recursivo depende da pilha do sistema), busca em profundidade em grafos e backtrack (que não deixa de ser uma busca em grafos).

A terceira é a fila, onde a inserção é em uma ponta e a remoção é na outra ponta e o acesso é possivelmente limitado a ponta de saida da fila. É como uma fila do banco, quem entra por último é acessado por último.

Ela é útil para busca em largura em grafos, ou seja achar o menor caminho de um vértice ao outro num grafo simples ou direcionado, mas sem pesos nas arestas.

A quarta é a fila dupla que permite a inserção e remoção em ambas as pontas. Agora pra que serve eu já não sei, acho que nunca usei uma dessas.

Bibliografia Recomendada:

Donald E. Knuth - The Art of Computer Programming Vol I Capitulo 2.2 Linear Lists que contém algumas imagens que mostra melhor os tipos de listas.

Cormen et al - Introduction to Algorithms Cap 10.1 - Stacks ans queues pg 200

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this