aula Estrutura de Dados 04

Prévia do material em texto

Tecnologia em Sistemas para Internet - IFMS
Aula 04 – Listas (parte 1)
Estruturas de Dados
Prof.º Msc. Sidney Roberto de Sousa
sidney.sousa@ifms.edu.br
Tec. em Sistemas para Internet - IFMS 2
O que veremos nesta aula?
● O que é uma lista?
● Listas simples
● Listas encadeadas
● Listas duplamente encadeadas
Tec. em Sistemas para Internet - IFMS 3
Lista
● Estrutura de dados abstrata e linear que 
implementa uma coleção finita e ordenada de 
valores
● Cada instância de um valor na lista é chamado 
de ítem (ou elemento) da lista
Tec. em Sistemas para Internet - IFMS 4
Propriedades de uma lista
● Tamanho: Número de itens armazenados na lista.
● Índice: Cada elemento na lista possui um índice, ou seja, um 
número que o identifica.
● Tipo(*): Toda lista possui um tipo. Assim, todo item da lista possui 
o mesmo tipo.
● Igualdade: Uma lista a é igual a uma outra lista b se e somente se, 
para cada índice i de a e b, ai é igual a bi quanto aos seus valores e 
estruturas.
(* Na verdade, tanto na linguagem Java quanto na maioria das linguagens modernas, uma lista pode conter itens de tipos variados. Manteremos esta definição 
por enquanto apenas por conveniência aos nossos estudos.)
Tec. em Sistemas para Internet - IFMS 5
Listas simples
● Listas simples ou listas estáticas são listas 
que permitem a adição de um número 
limitado de itens → tamanho invariável
● Neste tipo de lista, o acesso a um item situado 
em um determinado índice é feito de forma 
rápida e prática
● Listas simples podem ser implementadas 
como matrizes unidimensionais (vetores)
Tec. em Sistemas para Internet - IFMS 6
Exemplo: Lista simples
Classe ListaSimples
(abaixo no blog)
Tec. em Sistemas para Internet - IFMS 7
Inserção em uma lista simples
public boolean adicionarItem(Integer novoItem, int indiceDoItem) {
    if (indiceDoItem >= 0 && indiceDoItem < tamanho) {
        lista[indiceDoItem] = novoItem;
        return true;
    }
    return false;
}
Tec. em Sistemas para Internet - IFMS 8
Inserção em uma lista simples
public boolean adicionarItem(Integer novoItem, int indiceDoItem) {
    if (indiceDoItem >= 0 && indiceDoItem < tamanho) {
        lista[indiceDoItem] = novoItem;
        return true;
    }
    return false;
}
Verifica se a posição desejada para o armazenamento do 
novo elemento é válida.
Tec. em Sistemas para Internet - IFMS 9
Inserção em uma lista simples
public boolean adicionarItem(Integer novoItem, int indiceDoItem) {
    if (indiceDoItem >= 0 && indiceDoItem < tamanho) {
        lista[indiceDoItem] = novoItem;
        return true;
    }
    return false;
}
Se a posição for válida, o novo elemento é inserido na 
posição desejada. Caso já haja um outro elemento nesta 
posição, tal elemento é sobreposto pelo novo elemento. 
O método retorna o valor true, indicando que o elemento 
foi inserido com sucesso.
Tec. em Sistemas para Internet - IFMS 10
Inserção em uma lista simples
public boolean adicionarItem(Integer novoItem, int indiceDoItem) {
    if (indiceDoItem >= 0 && indiceDoItem < tamanho) {
        lista[indiceDoItem] = novoItem;
        return true;
    }
    return false;
}
Se a posição for inválida, o método retorna o valor false, 
indicando que o elemento não foi inserido.
Tec. em Sistemas para Internet - IFMS 11
Remoção em uma lista simples
public Integer removerItem(Integer indiceDoItem) {
    if (indiceDoItem >= 0 && indiceDoItem < tamanho
        && lista[indiceDoItem] != null) {
        Integer itemRemovido = lista[indiceDoItem];
        lista[indiceDoItem] = null;
        return itemRemovido;
    }
    return null;
}
Tec. em Sistemas para Internet - IFMS 12
Remoção em uma lista simples
public Integer removerItem(Integer indiceDoItem) {
    if (indiceDoItem >= 0 && indiceDoItem < tamanho
        && lista[indiceDoItem] != null) {
        Integer itemRemovido = lista[indiceDoItem];
        lista[indiceDoItem] = null;
        return itemRemovido;
    }
    return null;
}
Verifica se existe algum elemento a ser removido na 
posição desejada. Também verifica se tal posição é 
válida.
Tec. em Sistemas para Internet - IFMS 13
Remoção em uma lista simples
public Integer removerItem(Integer indiceDoItem) {
    if (indiceDoItem >= 0 && indiceDoItem < tamanho
        && lista[indiceDoItem] != null) {
        Integer itemRemovido = lista[indiceDoItem];
        lista[indiceDoItem] = null;
        return itemRemovido;
    }
    return null;
}
Caso a posição informada seja válida e exista 
algum elemento a ser removido, o elemento é 
“removido” ao se substituir o seu valor pelo valor 
null. Por fim, o método retorna o valor do item 
recém removido.
Tec. em Sistemas para Internet - IFMS 14
Remoção em uma lista simples
public Integer removerItem(Integer indiceDoItem) {
    if (indiceDoItem >= 0 && indiceDoItem < tamanho
        && lista[indiceDoItem] != null) {
        Integer itemRemovido = lista[indiceDoItem];
        lista[indiceDoItem] = null;
        return itemRemovido;
    }
    return null;
}
Caso a posição informada seja inválida ou não 
exista um elemento a ser removido, o método 
retorna o valor null.
Tec. em Sistemas para Internet - IFMS 15
Pegando um elemento de uma lista simples
public Integer pegarItem(Integer indiceDoItem) {
    if (indiceDoItem >= 0 && indiceDoItem < tamanho) {
        return lista[indiceDoItem];
    }
    return null;
}
Tec. em Sistemas para Internet - IFMS 16
Pegando um elemento de uma lista simples
public Integer pegarItem(Integer indiceDoItem) {
    if (indiceDoItem >= 0 && indiceDoItem < tamanho) {
        return lista[indiceDoItem];
    }
    return null;
}
Primeiramente, o método verifica se a posição do item 
desejado é válida.
Tec. em Sistemas para Internet - IFMS 17
Pegando um elemento de uma lista simples
public Integer pegarItem(Integer indiceDoItem) {
    if (indiceDoItem >= 0 && indiceDoItem < tamanho) {
        return lista[indiceDoItem];
    }
    return null;
}
Se a posição é válida, o elemento desejado é 
retornado. Note que o acesso ao elemento da lista é 
realizado diretamente por meio do uso do índice 
correto. Caso nenhum elemento tenha sido 
adicionado nesta posição, o valor null é retornado.
Tec. em Sistemas para Internet - IFMS 18
Pegando um elemento de uma lista simples
public Integer pegarItem(Integer indiceDoItem) {
    if (indiceDoItem >= 0 && indiceDoItem < tamanho) {
        return lista[indiceDoItem];
    }
    return null;
}
Se a posição é inválida, o método retorna o valor null.
Tec. em Sistemas para Internet - IFMS 19
Utilizando a classe ListaSimples
ListaSimples listaSimples = new ListaSimples(10);
listaSimples.adicionarItem(8, 0);
listaSimples.adicionarItem(­7, 5);
listaSimples.adicionarItem(98, 9);
listaSimples.adicionarItem(7, 5);
listaSimples.adicionarItem(123, 6);
listaSimples.removerItem(5);
listaSimples.removerItem(2);
for (int i = 0; i < listaSimples.tamanhoDaLista(); i++) {
    System.out.print(listaSimples.pegarItem(i) + " ");
}
/*
 * Imprime na tela:
 * 8 null null null null null 123 null null 98 
 */
Tec. em Sistemas para Internet - IFMS 20
Listas encadeadas
● Listas encadeadas ou listas ligadas são 
listas dinâmicas que permitem a adição de 
um número teoricamente ilimitado de itens
● Neste tipo de lista, o acesso aos itens não é 
realizado diretamente por meio de um índice
● Cada elemento da lista possui um link para o 
próximo elemento da lista
Tec. em Sistemas para Internet - IFMS 21
Exemplo: Lista encadeada
ClassesNo e ListaEncadeada
(abaixo no post)
Tec. em Sistemas para Internet - IFMS 22
Classe No
public class No {
    private Integer item;
    private No proximoItem;
    public No() {
        proximoItem = null;
    }
    // Getters e setters para os atributos da classe...
}
Tec. em Sistemas para Internet - IFMS 23
Classe No
public class No {
    private Integer item;
    private No proximoItem;
    public No() {
        proximoItem = null;
    }
    // Getters e setters para os atributos da classe...
}
Encapsula um item 
na lista encadeada
Tec. em Sistemas para Internet - IFMS 24
Classe No
public class No {
    private Integer item;
    private No proximoItem;
    public No() {
        proximoItem = null;
    }
    // Getters e setters para os atributos da classe...
}
Armazena o valor 
do item
Tec. em Sistemas para Internet - IFMS 25
Classe No
public class No {
    private Integer item;
    private No proximoItem;
    public No() {
        proximoItem = null;
    }
    // Getters e setters para os atributos da classe...
}
Ponteiro (link) para o 
próximo item da lista 
encadeada
Tec. em Sistemas para Internet - IFMS 26
Classe No
public class No {
    private Integer item;
    private No proximoItem;
    public No() {
        proximoItem = null;
    }
    // Getters e setters para os atributos da classe...
}
Construtor da classe 
No. Inicializa o atributo 
proximoItem com o 
valor null. Isto indica 
que inicialmente o item 
não estão ligado a um 
próximo item.
Tec. em Sistemas para Internet - IFMS 27
Representação da lista encadeada
item
pr
ox
im
oI
te
m
item
pr
ox
im
oI
te
m
item
pr
ox
im
oI
te
m
item
pr
ox
im
oI
te
m
No No No No
Tec. em Sistemas para Internet - IFMS 28
Classe ListaEncadeada
public class ListaEncadeada {
    private int tamanho;
    private No primeiroItem;
    private No ultimoItem;
   
    public ListaEncadeada() {
        primeiroItem = null;
        ultimoItem = null;
        tamanho = 0;
    }
    // Restante da classe...
}
Tec. em Sistemas para Internet - IFMS 29
Classe ListaEncadeada
public class ListaEncadeada {
    private int tamanho;
    private No primeiroItem;
    private No ultimoItem;
   
    public ListaEncadeada() {
        primeiroItem = null;
        ultimoItem = null;
        tamanho = 0;
    }
    // Restante da classe...
}
Encapsula uma lista 
encadeada, onde cada 
item da lista é 
encapsulado pela classe 
No. Contém as 
operações sobre a lista.
Tec. em Sistemas para Internet - IFMS 30
Classe ListaEncadeada
public class ListaEncadeada {
    private int tamanho;
    private No primeiroItem;
    private No ultimoItem;
   
    public ListaEncadeada() {
        primeiroItem = null;
        ultimoItem = null;
        tamanho = 0;
    }
    // Restante da classe...
}
Guarda o tamanho da 
lista, ou seja, o número 
de ítens contidos nela.
Tec. em Sistemas para Internet - IFMS 31
Classe ListaEncadeada
public class ListaEncadeada {
    private int tamanho;
    private No primeiroItem;
    private No ultimoItem;
   
    public ListaEncadeada() {
        primeiroItem = null;
        ultimoItem = null;
        tamanho = 0;
    }
    // Restante da classe...
}
Guarda o primeiro 
item da lista.
Tec. em Sistemas para Internet - IFMS 32
Classe ListaEncadeada
public class ListaEncadeada {
    private int tamanho;
    private No primeiroItem;
    private No ultimoItem;
   
    public ListaEncadeada() {
        primeiroItem = null;
        ultimoItem = null;
        tamanho = 0;
    }
    // Restante da classe...
}
Guarda o último 
item da lista.
Tec. em Sistemas para Internet - IFMS 33
Classe ListaEncadeada
public class ListaEncadeada {
    private int tamanho;
    private No primeiroItem;
    private No ultimoItem;
   
    public ListaEncadeada() {
        primeiroItem = null;
        ultimoItem = null;
        tamanho = 0;
    }
    // Restante da classe...
}
Construtor da classe 
ListaEncadeada. 
Inicializa os atributos 
da classe, sinalizando 
que a lista ainda não 
possui elementos.
Tec. em Sistemas para Internet - IFMS 34
Inserindo um novo item no início
public void adicionarNoInicio(Integer novoItem) {
    if (tamanho == 0) {
        primeiroItem = new No();
        primeiroItem.setItem(novoItem);
        ultimoItem = primeiroItem;
    } else {
        No antigoPrimeiroItem = primeiroItem;
        primeiroItem = new No();
        primeiroItem.setItem(novoItem);
        primeiroItem.setProximoItem(antigoPrimeiroItem);
    }
    tamanho++;
}
Tec. em Sistemas para Internet - IFMS 35
Inserindo um novo item no início
public void adicionarNoInicio(Integer novoItem) {
    if (tamanho == 0) {
        primeiroItem = new No();
        primeiroItem.setItem(novoItem);
        ultimoItem = primeiroItem;
    } else {
        No antigoPrimeiroItem = primeiroItem;
        primeiroItem = new No();
        primeiroItem.setItem(novoItem);
        primeiroItem.setProximoItem(antigoPrimeiroItem);
    }
    tamanho++;
}
Caso a lista esteja 
vazia, um novo item é 
criado com o valor 
desejado. O novo item 
se torna o primeiro e o 
último item da lista 
simultaneamente.
Tec. em Sistemas para Internet - IFMS 36
Inserindo um novo item no início
public void adicionarNoInicio(Integer novoItem) {
    if (tamanho == 0) {
        primeiroItem = new No();
        primeiroItem.setItem(novoItem);
        ultimoItem = primeiroItem;
    } else {
        No antigoPrimeiroItem = primeiroItem;
        primeiroItem = new No();
        primeiroItem.setItem(novoItem);
        primeiroItem.setProximoItem(antigoPrimeiroItem);
    }
    tamanho++;
}
Caso a lista não esteja vazia, 
um novo item é criado com o 
valor desejado. O novo item 
se torna o primeiro item da 
lista.
Tec. em Sistemas para Internet - IFMS 37
Inserindo um novo item no início
public void adicionarNoInicio(Integer novoItem) {
    if (tamanho == 0) {
        primeiroItem = new No();
        primeiroItem.setItem(novoItem);
        ultimoItem = primeiroItem;
    } else {
        No antigoPrimeiroItem = primeiroItem;
        primeiroItem = new No();
        primeiroItem.setItem(novoItem);
        primeiroItem.setProximoItem(antigoPrimeiroItem);
    }
    tamanho++;
}
Após o item ser inserido, o 
tamanho da lista é 
incrementado em uma unidade.
Tec. em Sistemas para Internet - IFMS 38
Inserindo um novo item no final
public void adicionarNoFinal(Integer novoItem) {
    if (tamanho == 0) {
        ultimoItem = new No();
        ultimoItem.setItem(novoItem);
        primeiroItem = ultimoItem;
    } else {
        No antigoUltimoItem = ultimoItem;
        ultimoItem = new No();
        ultimoItem.setItem(novoItem);
        antigoUltimoItem.setProximoItem(ultimoItem);
    }
    tamanho++;
}
Tec. em Sistemas para Internet - IFMS 39
Inserindo um novo item no final
public void adicionarNoFinal(Integer novoItem) {
    if (tamanho == 0) {
        ultimoItem = new No();
        ultimoItem.setItem(novoItem);
        primeiroItem = ultimoItem;
    } else {
        No antigoUltimoItem = ultimoItem;
        ultimoItem = new No();
        ultimoItem.setItem(novoItem);
        antigoUltimoItem.setProximoItem(ultimoItem);
    }
    tamanho++;
}
Caso a lista esteja 
vazia, um novo item é 
criado como valor 
desejado. O novo item 
se torna o primeiro e o 
último item da lista 
simultaneamente.
Tec. em Sistemas para Internet - IFMS 40
Inserindo um novo item no final
public void adicionarNoFinal(Integer novoItem) {
    if (tamanho == 0) {
        ultimoItem = new No();
        ultimoItem.setItem(novoItem);
        primeiroItem = ultimoItem;
    } else {
        No antigoUltimoItem = ultimoItem;
        ultimoItem = new No();
        ultimoItem.setItem(novoItem);
        antigoUltimoItem.setProximoItem(ultimoItem);
    }
    tamanho++;
}
Caso a lista não esteja vazia, 
um novo item é criado com o 
valor desejado. O novo item 
se torna o último item da 
lista.
Tec. em Sistemas para Internet - IFMS 41
Inserindo um novo item no final
public void adicionarNoFinal(Integer novoItem) {
    if (tamanho == 0) {
        ultimoItem = new No();
        ultimoItem.setItem(novoItem);
        primeiroItem = ultimoItem;
    } else {
        No antigoUltimoItem = ultimoItem;
        ultimoItem = new No();
        ultimoItem.setItem(novoItem);
        antigoUltimoItem.setProximoItem(ultimoItem);
    }
    tamanho++;
}
Após o item ser inserido, o 
tamanho da lista é 
incrementado em uma unidade.
Tec. em Sistemas para Internet - IFMS 42
Inserindo um novo item em qualquer posição
public boolean adicionarNaPosicao(Integer novoItem, int posicao) {
    if (posicao >= 1 && posicao <= tamanho + 1) {
        if (posicao == 1) {
            adicionarNoInicio(novoItem);
        } else if (posicao == tamanho + 1) {
            adicionarNoFinal(novoItem);
        } else {
            No novoNo = new No();
            novoNo.setItem(novoItem);
            int contador = 1;
            No itemAnteriorAoNovo = primeiroItem;
            while (contador < posicao ­ 1) {
                itemAnteriorAoNovo = itemAnteriorAoNovo.getProximoItem();
                contador++;
            }
            novoNo.setProximoItem(itemAnteriorAoNovo.getProximoItem());
            itemAnteriorAoNovo.setProximoItem(novoNo);
            tamanho++;
        }
        return true;
    }
    return false;
}
Tec. em Sistemas para Internet - IFMS 43
Inserindo um novo item em qualquer posição
public boolean adicionarNaPosicao(Integer novoItem, int posicao) {
    if (posicao >= 1 && posicao <= tamanho + 1) {
        if (posicao == 1) {
            adicionarNoInicio(novoItem);
        } else if (posicao == tamanho + 1) {
            adicionarNoFinal(novoItem);
        } else {
            No novoNo = new No();
            novoNo.setItem(novoItem);
            int contador = 1;
            No itemAnteriorAoNovo = primeiroItem;
            while (contador < posicao ­ 1) {
                itemAnteriorAoNovo = itemAnteriorAoNovo.getProximoItem();
                contador++;
            }
            novoNo.setProximoItem(itemAnteriorAoNovo.getProximoItem());
            itemAnteriorAoNovo.setProximoItem(novoNo);
            tamanho++;
        }
        return true;
    }
    return false;
}
Se a posição desejada for 
válida, então o novo item pode 
ser inserido.
Tec. em Sistemas para Internet - IFMS 44
Inserindo um novo item em qualquer posição
public boolean adicionarNaPosicao(Integer novoItem, int posicao) {
    if (posicao >= 1 && posicao <= tamanho + 1) {
        if (posicao == 1) {
            adicionarNoInicio(novoItem);
        } else if (posicao == tamanho + 1) {
            adicionarNoFinal(novoItem);
        } else {
            No novoNo = new No();
            novoNo.setItem(novoItem);
            int contador = 1;
            No itemAnteriorAoNovo = primeiroItem;
            while (contador < posicao ­ 1) {
                itemAnteriorAoNovo = itemAnteriorAoNovo.getProximoItem();
                contador++;
            }
            novoNo.setProximoItem(itemAnteriorAoNovo.getProximoItem());
            itemAnteriorAoNovo.setProximoItem(novoNo);
            tamanho++;
        }
        return true;
    }
    return false;
}
Se a primeira posição for a 
desejada, então o método de 
inserção de itens no início da 
lista é chamado.
Tec. em Sistemas para Internet - IFMS 45
Inserindo um novo item em qualquer posição
public boolean adicionarNaPosicao(Integer novoItem, int posicao) {
    if (posicao >= 1 && posicao <= tamanho + 1) {
        if (posicao == 1) {
            adicionarNoInicio(novoItem);
        } else if (posicao == tamanho + 1) {
            adicionarNoFinal(novoItem);
        } else {
            No novoNo = new No();
            novoNo.setItem(novoItem);
            int contador = 1;
            No itemAnteriorAoNovo = primeiroItem;
            while (contador < posicao ­ 1) {
                itemAnteriorAoNovo = itemAnteriorAoNovo.getProximoItem();
                contador++;
            }
            novoNo.setProximoItem(itemAnteriorAoNovo.getProximoItem());
            itemAnteriorAoNovo.setProximoItem(novoNo);
            tamanho++;
        }
        return true;
    }
    return false;
}
Se a última posição for a 
desejada, então o método de 
inserção de itens no final da 
lista é chamado.
Tec. em Sistemas para Internet - IFMS 46
Inserindo um novo item em qualquer posição
public boolean adicionarNaPosicao(Integer novoItem, int posicao) {
    if (posicao >= 1 && posicao <= tamanho + 1) {
        if (posicao == 1) {
            adicionarNoInicio(novoItem);
        } else if (posicao == tamanho + 1) {
            adicionarNoFinal(novoItem);
        } else {
            No novoNo = new No();
            novoNo.setItem(novoItem);
            int contador = 1;
            No itemAnteriorAoNovo = primeiroItem;
            while (contador < posicao ­ 1) {
                itemAnteriorAoNovo = itemAnteriorAoNovo.getProximoItem();
                contador++;
            }
            novoNo.setProximoItem(itemAnteriorAoNovo.getProximoItem());
            itemAnteriorAoNovo.setProximoItem(novoNo);
            tamanho++;
        }
        return true;
    }
    return false;
}
Se a posição desejada não for a 
primeira nem a última, então o método 
percorre a lista encadeada até 
encontrar a posição desejada. Por fim, 
o item é inserido na posição correta.
Tec. em Sistemas para Internet - IFMS 47
Inserindo um novo item em qualquer posição
public boolean adicionarNaPosicao(Integer novoItem, int posicao) {
    if (posicao >= 1 && posicao <= tamanho + 1) {
        if (posicao == 1) {
            adicionarNoInicio(novoItem);
        } else if (posicao == tamanho + 1) {
            adicionarNoFinal(novoItem);
        } else {
            No novoNo = new No();
            novoNo.setItem(novoItem);
            int contador = 1;
            No itemAnteriorAoNovo = primeiroItem;
            while (contador < posicao ­ 1) {
                itemAnteriorAoNovo = itemAnteriorAoNovo.getProximoItem();
                contador++;
            }
            novoNo.setProximoItem(itemAnteriorAoNovo.getProximoItem());
            itemAnteriorAoNovo.setProximoItem(novoNo);
            tamanho++;
        }
        return true;
    }
    return false;
}
Se o item foi inserido com 
sucesso, o método retorna o 
valor true indicando o fato.
Tec. em Sistemas para Internet - IFMS 48
Inserindo um novo item em qualquer posição
public boolean adicionarNaPosicao(Integer novoItem, int posicao) {
    if (posicao >= 1 && posicao <= tamanho + 1) {
        if (posicao == 1) {
            adicionarNoInicio(novoItem);
        } else if (posicao == tamanho + 1) {adicionarNoFinal(novoItem);
        } else {
            No novoNo = new No();
            novoNo.setItem(novoItem);
            int contador = 1;
            No itemAnteriorAoNovo = primeiroItem;
            while (contador < posicao ­ 1) {
                itemAnteriorAoNovo = itemAnteriorAoNovo.getProximoItem();
                contador++;
            }
            novoNo.setProximoItem(itemAnteriorAoNovo.getProximoItem());
            itemAnteriorAoNovo.setProximoItem(novoNo);
            tamanho++;
        }
        return true;
    }
    return false;
}
Caso contrário, a posição desejada 
era inválida e portanto o item não foi 
inserido. Assim, o método retorna o 
valor false indicando tal fato.
Tec. em Sistemas para Internet - IFMS 49
Removendo um item
public boolean remover(int posicao) {
    if (tamanho > 0 && posicao >= 1 && posicao <= tamanho) {
        No item = primeiroItem;
        No anterior = null;
        int contador = 1;
        while (contador < posicao) {
            anterior = item;
            item = item.getProximoItem();
            contador++;
        }
        No proximo = item.getProximoItem();
        if (anterior != null) {
            anterior.setProximoItem(proximo);
        } else {
            primeiroItem = proximo;
        }
        tamanho­­;
        if (tamanho <= 1) {
            primeiroItem = proximo;
            ultimoItem = primeiroItem;
        }
        return true;
    }
    return false;
}
Tec. em Sistemas para Internet - IFMS 50
Removendo um item
public boolean remover(int posicao) {
    if (tamanho > 0 && posicao >= 1 && posicao <= tamanho) {
        No item = primeiroItem;
        No anterior = null;
        int contador = 1;
        while (contador < posicao) {
            anterior = item;
            item = item.getProximoItem();
            contador++;
        }
        No proximo = item.getProximoItem();
        if (anterior != null) {
            anterior.setProximoItem(proximo);
        } else {
            primeiroItem = proximo;
        }
        tamanho­­;
        if (tamanho <= 1) {
            primeiroItem = proximo;
            ultimoItem = primeiroItem;
        }
        return true;
    }
    return false;
}
Se a posição é válida, ou seja, 
existe um item em tal posição, 
então o item pode ser removido.
Tec. em Sistemas para Internet - IFMS 51
Removendo um item
public boolean remover(int posicao) {
    if (tamanho > 0 && posicao >= 1 && posicao <= tamanho) {
        No item = primeiroItem;
        No anterior = null;
        int contador = 1;
        while (contador < posicao) {
            anterior = item;
            item = item.getProximoItem();
            contador++;
        }
        No proximo = item.getProximoItem();
        if (anterior != null) {
            anterior.setProximoItem(proximo);
        } else {
            primeiroItem = proximo;
        }
        tamanho­­;
        if (tamanho <= 1) {
            primeiroItem = proximo;
            ultimoItem = primeiroItem;
        }
        return true;
    }
    return false;
}
O item a ser removido é 
encontrado.
Tec. em Sistemas para Internet - IFMS 52
Removendo um item
public boolean remover(int posicao) {
    if (tamanho > 0 && posicao >= 1 && posicao <= tamanho) {
        No item = primeiroItem;
        No anterior = null;
        int contador = 1;
        while (contador < posicao) {
            anterior = item;
            item = item.getProximoItem();
            contador++;
        }
        No proximo = item.getProximoItem();
       if (anterior != null) {
            anterior.setProximoItem(proximo);
        } else {
            primeiroItem = proximo;
        }
        tamanho­­;
        if (tamanho <= 1) {
            primeiroItem = proximo;
            ultimoItem = primeiroItem;
        }
        return true;
    }
    return false;
}
Se o item a ser removido não for 
o primeiro, então o seu vizinho 
anterior é ligado ao seu vizinho 
posterior.
Tec. em Sistemas para Internet - IFMS 53
Removendo um item
public boolean remover(int posicao) {
    if (tamanho > 0 && posicao >= 1 && posicao <= tamanho) {
        No item = primeiroItem;
        No anterior = null;
        int contador = 1;
        while (contador < posicao) {
            anterior = item;
            item = item.getProximoItem();
            contador++;
        }
        No proximo = item.getProximoItem();
        if (anterior != null) {
            anterior.setProximoItem(proximo);
        } else {
            primeiroItem = proximo;
        }
        tamanho­­;
        if (tamanho <= 1) {
            primeiroItem = proximo;
            ultimoItem = primeiroItem;
        }
        return true;
    }
    return false;
}
Se o item a ser removido for o 
primeiro, então o seu vizinho 
posterior se torna o novo primeiro 
item da lista.
Tec. em Sistemas para Internet - IFMS 54
Removendo um item
public boolean remover(int posicao) {
    if (tamanho > 0 && posicao >= 1 && posicao <= tamanho) {
        No item = primeiroItem;
        No anterior = null;
        int contador = 1;
        while (contador < posicao) {
            anterior = item;
            item = item.getProximoItem();
            contador++;
        }
        No proximo = item.getProximoItem();
        if (anterior != null) {
            anterior.setProximoItem(proximo);
        } else {
            primeiroItem = proximo;
        }
        tamanho­­;
        if (tamanho <= 1) {
            primeiroItem = proximo;
            ultimoItem = primeiroItem;
        }
        return true;
    }
    return false;
}
Após o item ser removido, o 
tamanho da lista é decrementado 
em uma unidade. Se a lista ficou 
vazia, então os ponteiros do 
primeiro e último itens apontam 
para null. Se a lista ficou com 
apenas um item, então os 
ponteiros do primeiro e último 
ítens apontam para o único item 
da lista. Se o item foi removido 
com sucesso, o valor true é 
retornado indicando tal fato.
Tec. em Sistemas para Internet - IFMS 55
Removendo um item
public boolean remover(int posicao) {
    if (tamanho > 0 && posicao >= 1 && posicao <= tamanho) {
        No item = primeiroItem;
        No anterior = null;
        int contador = 1;
        while (contador < posicao) {
            anterior = item;
            item = item.getProximoItem();
            contador++;
        }
        No proximo = item.getProximoItem();
        if (anterior != null) {
            anterior.setProximoItem(proximo);
        } else {
            primeiroItem = proximo;
        }
        tamanho­­;
        if (tamanho <= 1) {
            primeiroItem = proximo;
            ultimoItem = primeiroItem;
        }
        return true;
    }
    return false;
}
Se a posição for inválida, então o 
valor false é retornado indicando 
tal fato.
Tec. em Sistemas para Internet - IFMS 56
Pegando um item da lista
public No pegarItem(int posicao) {
    if (tamanho > 0 && posicao >= 1 && posicao <= tamanho) {
        No item = primeiroItem;
        int contador = 1;
        while (posicao < contador) {
            item = item.getProximoItem();
            contador++;
        }
        return item;
    }
    return null;
}
Tec. em Sistemas para Internet - IFMS 57
Pegando um item da lista
public No pegarItem(int posicao) {
    if (tamanho > 0 && posicao >= 1 && posicao <= tamanho){
        No item = primeiroItem;
        int contador = 1;
        while (posicao < contador) {
            item = item.getProximoItem();
            contador++;
        }
        return item;
    }
    return null;
}
Se a posição é válida, ou seja, 
existe um item em tal posição, 
então o item pode ser retornado.
Tec. em Sistemas para Internet - IFMS 58
Pegando um item da lista
public No pegarItem(int posicao) {
    if (tamanho > 0 && posicao >= 1 && posicao <= tamanho) {
        No item = primeiroItem;
       int contador = 1;
       while (posicao < contador) {
           item = item.getProximoItem();
           contador++;
       }
       return item;
    }
    return null;
}
A lista encadeada é percorrida até se 
chegar na posição desejada. 
Quando a posição é alcançada, 
então o item correto é retornado.
Tec. em Sistemas para Internet - IFMS 59
Pegando um item da lista
public No pegarItem(int posicao) {
    if (tamanho > 0 && posicao >= 1 && posicao <= tamanho) {
        No item = primeiroItem;
        int contador = 1;
        while (posicao < contador) {
            item = item.getProximoItem();
            contador++;
        }
        return item;
    }
    return null;
}
Se a posição desejada for inválida, 
então o valor null é retornado.
Tec. em Sistemas para Internet - IFMS 60
Utilizando a classe ListaEncadeada
ListaEncadeada listaEncadeada = new ListaEncadeada();
listaEncadeada.adicionarNoInicio(­13);
listaEncadeada.adicionarNoInicio(78);
listaEncadeada.adicionarNoInicio(19823);
listaEncadeada.adicionarNoFinal(500);
listaEncadeada.adicionarNaPosicao(457, 2);
No item = listaEncadeada.pegarItem(1);
// Imprime na tela:
// 19823 457 78 ­13 500
while (item != null) {
    System.out.print(item.getItem() + " ");
    item = item.getProximoItem();
}
Tec. em Sistemas para Internet - IFMS 61
Listas duplamente encadeadas
● Similares às listas encadeadas
● Porém, cada item possui um ponteiro para os 
ítens anterior e posterior a si na lista
Tec. em Sistemas para Internet - IFMS 62
Representação da lista duplamente encadeada
item
pr
ox
im
oI
te
m
item
pr
ox
im
oI
te
m
item
pr
ox
im
oI
te
m
item
pr
ox
im
oI
te
m
No No No No
ite
m
A
nt
er
io
r
ite
m
A
nt
er
io
r
ite
m
A
nt
er
io
r
ite
m
A
nt
er
io
r
Tec. em Sistemas para Internet - IFMS 63
Exemplo: Lista duplamente encadeada
Classes NoDuplo e 
ListaDuplamenteEncadeada
(abaixo no post)
Tec. em Sistemas para Internet - IFMS 64
Exemplo: Lista duplamente encadeada
Classes NoDuplo e 
ListaDuplamenteEncadeada
(abaixo no post)?
Tec. em Sistemas para Internet - IFMS 65
Exercício
Implemente as classes NoDuplo e 
ListaDuplamenteEncadeada.
Tec. em Sistemas para Internet - IFMS 66
That's not all, folks!
Na próxima aula falaremos mais sobre listas, mas 
de uma forma mais suave...
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65
	Slide 66