#1 [tuto][estrutura de dados]lista encadeada. Qui Out 13, 2011 3:40 pm
#Kamikaze ' ~
Novato
Tuto de listas (linear e ordenada) encadeadas.
Difículdade:
Básico
Índice:
1. Lista linear
2. Vantagens e desvantagens
3. Lista ordenada
4. Nodo ou Nó
5. Sources
Lista linear
Lista linear é uma estrutura de dados dinâmica cujos elementos estão organizados de maneira seqüencial. São estruturas flexíveis , que podem crescer ou diminuir durante a execução do programa, de acordo com a demanda.
Operações mas freqüentes em listas:
°Iniciar/Criar/Instanciar uma lista linear vazia.
°Verificação do estado da lista: vazia ou cheia.
°Inclusão de elemento em uma posição específica;
°Remoção e retorno do elemento em uma posição específica;
°Consulta a um elemento em uma posição específica
°Alteração de um elemento de uma posição específica
°Busca de um elemento na lista
°Ordenação dos elementos da lista
°Fazer uma cópia da lista
°Mostrar a lista
Tipos de implementações de Listas:
1. Implementação seqüencial:
um
vetor é utilizado para armazenar os elementos da estrutura. Vemos
abaixo a representação gráfica de uma lista com 4 elementos armazenada
em um vetor de capacidade para até 10 elementos.
Expandir esta imagemReduzir esta imagem Ver em tamanho real
2. Implementação encadeada
Os
elementos são armazenados em nodos que têm um campo que aponta para o
próximo elemento da lista. Vemos abaixo a representação gráfica de uma
lista vazia e de uma lista com 4 elementos encadeados.
Expandir esta imagemReduzir esta imagem Ver em tamanho real
Vantagens e desvantagens do encadeamento em relação á implementação sequencial:
°Desvantagens
1. Acesso indireto aos elementos
2. Tempo variável para acessar os elementos (depende da posição do elemento)
3. Gasto de memória maior pela necessidade de um novo campo para o ponteiro
°Vantagens
1. A inserção e remoção de elementos podem ser feitas sem deslocar os itens seguintes da lista
2.Não há necessidade de previsão do número de elementos da estrutura,o espaço necessário é alocado em tempo de execução
3. Facilita o gerenciamento de várias listas (fusão,divisão,...)
Listas ordenadas
São
listas lineares onde os elementos estão ordenados segundo um critério
preestabelecido. As remoções são realizadas de qualquer posição,mas as
inserções são feitos de modo que cada novo elemento a ser inserido
ocupará a posição que mantenha os elementos ordenados.Essa ordenação é
mantida para facilitar a busca de elementos na lista.
Operações mas frequentes em listas:
°Iniciar/Criar uma lista linear vazia (Construtor)
°Verificação do estado da lista: Vazia ou Cheia
°Inclusão de elemento
°Remoção e retorno do elemento em uma posição específica
°Busca de um elemento na lista (Busca Binária só na implementação sequencial)
°Fazer uma cópia da lista
°Mostrar Lista
Implementação sequencial de uma lista ordenada
Representação gráfica
Expandir esta imagemReduzir esta imagem Ver em tamanho real
Implementação encadeada de uma lista ordenada (encadeamento com nodos cabeça e sentinela)
Expandir esta imagemReduzir esta imagem Ver em tamanho real
Não há possibilidades de eu terminar esse tuto sem explicar o "esqueleto" da encadeação.
Nodo ou Nó
Um
nodo ou nó representa cada ponto de inter-conexão com uma estrutura ou
rede,independente da função do equipamento representado por ele. Em
ciência da computação,nodo ou nó também pode representar um elemento de
uma árvore de busca binária ou um vértice de um grafo (BY WIKIPÉDIA)
Resumindo de uma forma bem vulgar,nodo é um elemento da lista encadeada.
Nodo cabeça:
Um
nodo cabeça é um nodo extra,mantido sempre na primeira posição de uma
lista encadeada.Ele não é usado para armazenar um elemento da
lista,tendo como único objetivo simplificar as funções de inserção e
remoção da lista. No caso de uma lista numérica ele pode ser usado para
, por exemplo, armazenar o número de elementos na lista
Nodo Sentinela
Um
nodo sentinela também é um nodo extra,mantido na última posição com o
mesmo objetivo do nodo cabeça.Seu valor não faz parte da lista.Muitas
vezes ele armazena o maior valor (HV - High Value) para o tipo
armazenado.Isso simplifica,Ainda mas,os processos de inserção e remoção
Sources
Lista sequencial
Spoiler:class ListaDeInteiros {
private int nel;
private int ele[];
public ListaDeInteiros() {
nel = 0;
ele = new int[10];
}
public ListaDeInteiros(int cap) {
nel = 0;
if(cap < 10)
ele = new int[10];
else
ele = new int[cap];
}
public ListaDeInteiros(ListaDeInteiros lis)
{
nel = lis.nel;
ele = new int[lis.ele.length];
System.arraycopy(lis.ele, 0, ele, 0, nel);
}
public boolean estaVazia()
{
return nel == 0;
}
public boolean estaCheia()
{
return nel == ele.length;
}
public int getNel() {
return nel;
}
public void insereNoFinal(int val)
{
ele[nel++] = val;
}
public void insereNoInicio(int val)
{
for(int i=nel; i>0; i--) // Deslocamento de dados
ele[i] = ele[i-1];
ele[0] = val;
nel++;
}
public void insereNoIndice(int val, int ind)
{
for(int i=nel; i>ind; i--) // Deslocamento de dados
ele[i] = ele[i-1];
ele[ind] = val;
nel++;
}
public int removeDoFinal()
{
return ele[--nel];
}
public int removeDoInicio()
{
int res = ele[0];
for(int i=0; i<nel-1; i++)
ele[i] = ele[i+1];
nel--;
return res;
}
public int removeDoIndice(int ind)
{
int res = ele[ind];
for(int i=ind; i<nel-1; i++)
ele[i] = ele[i+1];
nel--;
return res;
}
public int busca(int val)
{
for(int i=0; i<nel; i++)
if(ele[i] == val)
return i;
return -1;
}
public void remove(int val)
{
int rb = busca(val);
if(rb > -1)
removeDoIndice(rb);
}
public void removeTodos(int val)
{
int i = 0;
while(i < nel)
{
if(ele[i] == val)
removeDoIndice(i);
else
i++;
}
}
@Override
public String toString() {
if(estaVazia()) return "[]";
String res = "[";
for(int i=0; i<nel-1; i++)
res += ele[i]+", ";
return res+ele[nel-1]+"]";
}
}
Lista encadeada
Obs: por motivos de preguiça,tempo e burrice (no final do tópico explico porque da burrice) está sem nodo cabeça e sentinela
Spoiler:public class ListaEncadeada<E extends Object & Comparable> {
private Nodo<E> lis;
/**
* Construtor padrão da classe. Cria uma
* lista vazia.
*/
public ListaEncadeada()
{
lis = null;
}
public boolean estaVazia()
{
return lis == null;
}
public boolean estaCheia()
{
return false;
}
public int getNel()
{
Nodo<E> p = lis;
int res = 0;
while(p != null)
{
res++;
p = p.pro;
}
return res;
}
public void insereNoInicio(E val)
{
Nodo<E> nn = new Nodo<E>(val, lis);
//nn.pro = lis;
lis = nn;
}
public void insereNaPosicao(E val, int pos)
{
if(pos == 1)
insereNoInicio(val);
else
{
Nodo<E> nn = new Nodo<E>(val);
Nodo p = lis;
while(pos > 2)
{
p = p.pro;
pos--;
}
nn.pro = p.pro;
p.pro = nn;
}
}
public void insereNoFinal(E val)
{
Nodo<E> nn = new Nodo<E>(val);
Nodo p = lis;
while(p.pro != null)
{
p = p.pro;
}
nn.pro = p.pro;
p.pro = nn;
}
public E removeDoInicio()
{
E res = lis.val;
lis = lis.pro;
return res;
}
public E removeDaPosicao(int pos)
{
if(pos == 1)
return removeDoInicio();
else
{
Nodo<E> p = lis;
while(pos > 2)
{
p = p.pro;
pos--;
}
E res = p.pro.val;
p.pro = p.pro.pro;
return res;
}
}
public Nodo<E> busca(E val)
{
Nodo<E> p = lis;
while(p != null)
{
if(p.val.compareTo(val) == 0)
return p;
p = p.pro;
}
return null;
}
public void remove(E val)
{
if(lis.val.compareTo(val)== 0)
{
lis = lis.pro;
}
else
{
Nodo<E> p = lis;
while(p.pro != null && p.pro.val.compareTo(val) != 0)
p = p.pro;
if(p.pro != null)
p.pro = p.pro.pro;
}
}
public void removeTodos(E val)
{
while(busca(val) != null)
remove(val);
}
public void ordena()
{
Nodo<E> i = lis;
while(i.pro != null)
{
Nodo<E> pm = i;
Nodo<E> j = i.pro;
while(j != null)
{
if(j.val.compareTo(pm.val) < 0)
pm = j;
j = j.pro;
}
E aux = i.val;
i.val = pm.val;
pm.val = aux;
i = i.pro;
}
}
@Override
public String toString() {
if(estaVazia())
return "[]";
String res = "[";
Nodo p = lis;
while(p.pro != null)
{
res += p.val + ", ";
p = p.pro;
}
return res + p.val + "]";
}
}
Nodo
Spoiler:public class Nodo<T> {
public T val;
public Nodo<T> pro;
public Nodo(T v)
{
val = v;
pro = null;
}
public Nodo(T v, Nodo p)
{
val = v;
pro = p;
}
}
Fim.
Observações gerais:
*Tutorial usando como referencia NetBeans
*Algumas coisas do tuto fizeram no word e depois passou para cá,porque algumas formatações de texto não sei fazer aqui xd
*Desculpa ser tiver qualquer erro de português
*Qualquer dúvida relacionada ao tópico estárei respondendo =]
**Ahh,
sobre a burrice(citada no tópico) é que estáva fazendo o tuto e sem
querer fechei a página e perdi tudo u.u então fui fazer tudo denovo e
pra agilizar coloquei essa source sem nodo cabeça e sentinela
Espero que tenha ajudado vocês
Créditos: Totalmente de lipinf o/
To aqui para ajudar as pessoas e não para críticar!
Difículdade:
Básico
Índice:
1. Lista linear
2. Vantagens e desvantagens
3. Lista ordenada
4. Nodo ou Nó
5. Sources
Lista linear
Lista linear é uma estrutura de dados dinâmica cujos elementos estão organizados de maneira seqüencial. São estruturas flexíveis , que podem crescer ou diminuir durante a execução do programa, de acordo com a demanda.
Operações mas freqüentes em listas:
°Iniciar/Criar/Instanciar uma lista linear vazia.
°Verificação do estado da lista: vazia ou cheia.
°Inclusão de elemento em uma posição específica;
°Remoção e retorno do elemento em uma posição específica;
°Consulta a um elemento em uma posição específica
°Alteração de um elemento de uma posição específica
°Busca de um elemento na lista
°Ordenação dos elementos da lista
°Fazer uma cópia da lista
°Mostrar a lista
Tipos de implementações de Listas:
1. Implementação seqüencial:
um
vetor é utilizado para armazenar os elementos da estrutura. Vemos
abaixo a representação gráfica de uma lista com 4 elementos armazenada
em um vetor de capacidade para até 10 elementos.
Expandir esta imagemReduzir esta imagem Ver em tamanho real
2. Implementação encadeada
Os
elementos são armazenados em nodos que têm um campo que aponta para o
próximo elemento da lista. Vemos abaixo a representação gráfica de uma
lista vazia e de uma lista com 4 elementos encadeados.
Expandir esta imagemReduzir esta imagem Ver em tamanho real
Vantagens e desvantagens do encadeamento em relação á implementação sequencial:
°Desvantagens
1. Acesso indireto aos elementos
2. Tempo variável para acessar os elementos (depende da posição do elemento)
3. Gasto de memória maior pela necessidade de um novo campo para o ponteiro
°Vantagens
1. A inserção e remoção de elementos podem ser feitas sem deslocar os itens seguintes da lista
2.Não há necessidade de previsão do número de elementos da estrutura,o espaço necessário é alocado em tempo de execução
3. Facilita o gerenciamento de várias listas (fusão,divisão,...)
Listas ordenadas
São
listas lineares onde os elementos estão ordenados segundo um critério
preestabelecido. As remoções são realizadas de qualquer posição,mas as
inserções são feitos de modo que cada novo elemento a ser inserido
ocupará a posição que mantenha os elementos ordenados.Essa ordenação é
mantida para facilitar a busca de elementos na lista.
Operações mas frequentes em listas:
°Iniciar/Criar uma lista linear vazia (Construtor)
°Verificação do estado da lista: Vazia ou Cheia
°Inclusão de elemento
°Remoção e retorno do elemento em uma posição específica
°Busca de um elemento na lista (Busca Binária só na implementação sequencial)
°Fazer uma cópia da lista
°Mostrar Lista
Implementação sequencial de uma lista ordenada
Representação gráfica
Expandir esta imagemReduzir esta imagem Ver em tamanho real
Implementação encadeada de uma lista ordenada (encadeamento com nodos cabeça e sentinela)
Expandir esta imagemReduzir esta imagem Ver em tamanho real
Não há possibilidades de eu terminar esse tuto sem explicar o "esqueleto" da encadeação.
Nodo ou Nó
Um
nodo ou nó representa cada ponto de inter-conexão com uma estrutura ou
rede,independente da função do equipamento representado por ele. Em
ciência da computação,nodo ou nó também pode representar um elemento de
uma árvore de busca binária ou um vértice de um grafo (BY WIKIPÉDIA)
Resumindo de uma forma bem vulgar,nodo é um elemento da lista encadeada.
Nodo cabeça:
Um
nodo cabeça é um nodo extra,mantido sempre na primeira posição de uma
lista encadeada.Ele não é usado para armazenar um elemento da
lista,tendo como único objetivo simplificar as funções de inserção e
remoção da lista. No caso de uma lista numérica ele pode ser usado para
, por exemplo, armazenar o número de elementos na lista
Nodo Sentinela
Um
nodo sentinela também é um nodo extra,mantido na última posição com o
mesmo objetivo do nodo cabeça.Seu valor não faz parte da lista.Muitas
vezes ele armazena o maior valor (HV - High Value) para o tipo
armazenado.Isso simplifica,Ainda mas,os processos de inserção e remoção
Sources
Lista sequencial
Spoiler:class ListaDeInteiros {
private int nel;
private int ele[];
public ListaDeInteiros() {
nel = 0;
ele = new int[10];
}
public ListaDeInteiros(int cap) {
nel = 0;
if(cap < 10)
ele = new int[10];
else
ele = new int[cap];
}
public ListaDeInteiros(ListaDeInteiros lis)
{
nel = lis.nel;
ele = new int[lis.ele.length];
System.arraycopy(lis.ele, 0, ele, 0, nel);
}
public boolean estaVazia()
{
return nel == 0;
}
public boolean estaCheia()
{
return nel == ele.length;
}
public int getNel() {
return nel;
}
public void insereNoFinal(int val)
{
ele[nel++] = val;
}
public void insereNoInicio(int val)
{
for(int i=nel; i>0; i--) // Deslocamento de dados
ele[i] = ele[i-1];
ele[0] = val;
nel++;
}
public void insereNoIndice(int val, int ind)
{
for(int i=nel; i>ind; i--) // Deslocamento de dados
ele[i] = ele[i-1];
ele[ind] = val;
nel++;
}
public int removeDoFinal()
{
return ele[--nel];
}
public int removeDoInicio()
{
int res = ele[0];
for(int i=0; i<nel-1; i++)
ele[i] = ele[i+1];
nel--;
return res;
}
public int removeDoIndice(int ind)
{
int res = ele[ind];
for(int i=ind; i<nel-1; i++)
ele[i] = ele[i+1];
nel--;
return res;
}
public int busca(int val)
{
for(int i=0; i<nel; i++)
if(ele[i] == val)
return i;
return -1;
}
public void remove(int val)
{
int rb = busca(val);
if(rb > -1)
removeDoIndice(rb);
}
public void removeTodos(int val)
{
int i = 0;
while(i < nel)
{
if(ele[i] == val)
removeDoIndice(i);
else
i++;
}
}
@Override
public String toString() {
if(estaVazia()) return "[]";
String res = "[";
for(int i=0; i<nel-1; i++)
res += ele[i]+", ";
return res+ele[nel-1]+"]";
}
}
Lista encadeada
Obs: por motivos de preguiça,tempo e burrice (no final do tópico explico porque da burrice) está sem nodo cabeça e sentinela
Spoiler:public class ListaEncadeada<E extends Object & Comparable> {
private Nodo<E> lis;
/**
* Construtor padrão da classe. Cria uma
* lista vazia.
*/
public ListaEncadeada()
{
lis = null;
}
public boolean estaVazia()
{
return lis == null;
}
public boolean estaCheia()
{
return false;
}
public int getNel()
{
Nodo<E> p = lis;
int res = 0;
while(p != null)
{
res++;
p = p.pro;
}
return res;
}
public void insereNoInicio(E val)
{
Nodo<E> nn = new Nodo<E>(val, lis);
//nn.pro = lis;
lis = nn;
}
public void insereNaPosicao(E val, int pos)
{
if(pos == 1)
insereNoInicio(val);
else
{
Nodo<E> nn = new Nodo<E>(val);
Nodo p = lis;
while(pos > 2)
{
p = p.pro;
pos--;
}
nn.pro = p.pro;
p.pro = nn;
}
}
public void insereNoFinal(E val)
{
Nodo<E> nn = new Nodo<E>(val);
Nodo p = lis;
while(p.pro != null)
{
p = p.pro;
}
nn.pro = p.pro;
p.pro = nn;
}
public E removeDoInicio()
{
E res = lis.val;
lis = lis.pro;
return res;
}
public E removeDaPosicao(int pos)
{
if(pos == 1)
return removeDoInicio();
else
{
Nodo<E> p = lis;
while(pos > 2)
{
p = p.pro;
pos--;
}
E res = p.pro.val;
p.pro = p.pro.pro;
return res;
}
}
public Nodo<E> busca(E val)
{
Nodo<E> p = lis;
while(p != null)
{
if(p.val.compareTo(val) == 0)
return p;
p = p.pro;
}
return null;
}
public void remove(E val)
{
if(lis.val.compareTo(val)== 0)
{
lis = lis.pro;
}
else
{
Nodo<E> p = lis;
while(p.pro != null && p.pro.val.compareTo(val) != 0)
p = p.pro;
if(p.pro != null)
p.pro = p.pro.pro;
}
}
public void removeTodos(E val)
{
while(busca(val) != null)
remove(val);
}
public void ordena()
{
Nodo<E> i = lis;
while(i.pro != null)
{
Nodo<E> pm = i;
Nodo<E> j = i.pro;
while(j != null)
{
if(j.val.compareTo(pm.val) < 0)
pm = j;
j = j.pro;
}
E aux = i.val;
i.val = pm.val;
pm.val = aux;
i = i.pro;
}
}
@Override
public String toString() {
if(estaVazia())
return "[]";
String res = "[";
Nodo p = lis;
while(p.pro != null)
{
res += p.val + ", ";
p = p.pro;
}
return res + p.val + "]";
}
}
Nodo
Spoiler:public class Nodo<T> {
public T val;
public Nodo<T> pro;
public Nodo(T v)
{
val = v;
pro = null;
}
public Nodo(T v, Nodo p)
{
val = v;
pro = p;
}
}
Fim.
Observações gerais:
*Tutorial usando como referencia NetBeans
*Algumas coisas do tuto fizeram no word e depois passou para cá,porque algumas formatações de texto não sei fazer aqui xd
*Desculpa ser tiver qualquer erro de português
*Qualquer dúvida relacionada ao tópico estárei respondendo =]
**Ahh,
sobre a burrice(citada no tópico) é que estáva fazendo o tuto e sem
querer fechei a página e perdi tudo u.u então fui fazer tudo denovo e
pra agilizar coloquei essa source sem nodo cabeça e sentinela
Espero que tenha ajudado vocês
Créditos: Totalmente de lipinf o/
To aqui para ajudar as pessoas e não para críticar!