Estruturas de Dados em C++
Aula 11
Prof. Anderson da Cruz
Listas Simplesmente
Encadeadas
Pessoa *pessoa;
Aqui é criada uma variável que conterá uma
referência a um objeto
pessoa = new Pessoa();
Aqui um objeto é criado
Pessoa *pessoa = new Pessoa();
Tudo em uma única linha
2
Listas Simplesmente
Encadeadas
Pessoa *pessoa = new Pessoa( João );
pessoa = new Pessoa( Pedro );
João
Pessao
Pedro
3
Listas Simplesmente
Encadeadas
Pessoa *pessoa = new Pessoa( João );
pessoa = new Pessoa( Pedro );
João
A memória continua
alocada
Pessao
Pedro
4
Tipos de Armazenamento
Com alocação estática de memória
Posições de memória contíguas
Array
Com alocação dinâmica de memória
Alocação de memória de acordo com a
necessidade
O dados estão em posições aleatórias na memória
e ligadas por ponteiros
5
Listas Simplesmente
Encadeadas
Uma lista encadeadas básica deve conter
head: referência para o primeiro elemento da lista
tail: referência para o último elemento da lista
node: representa um item da lista
> element: o informação
> next: um atributo para o próximo elemento da lista
6
Listas Simplesmente
Encadeadas
Exemplo de uma lista encadeada
7
Listas Simplesmente
Encadeadas
Inserção uma lista encadeada
8
Listas Simplesmente
Encadeadas
Exclusão do 1º nó de uma lista
encadeada
9
Listas Simplesmente
Encadeadas
Exclusão de um nó no meio da lista
encadeada
10
Listas Simplesmente
Encadeadas
Inserção em uma posição específica da
lista encadeada
11
Listas Simplesmente
Encadeadas
Para tornar a lista encadeada mais efeiciente,
podemos colocar uma variável tail para
determinar a última posição da lista
12
Classe Node
class Node {
O que
string element;
criar
Node *next;
public:
Node(string element, Node *n){
this->element = element;
this->next = n;
}
Node(string element){
this->element = element;
this->next = NULL;
}
string getElement() { return this->element; }
void setElement(string element) { this->element = element; }
Node* getNext() { return this->next; }
void setNext(Node *next) { this->next = next; }
};
permite
a lista
13
Classe No Genérica
public class Node<E>{
private E element;
private Node<E> next;
public Node(E s, Node<E> n){
element = s;
next = n;
}
public Node( E element ) { this( element, null ); }
public E getElement(){ return element; }
public Node<E> getNext(){ return next; }
public void setElement(E newElem){ element = newElem; }
public void setNext(Node<E> newNext){ next = newNext; }
}
14
Inserção no início da lista
bool empty = this->isEmpty();
Node *node = new Node(element);
node->setNext(this->head);
this->head = node;
if (empty) this->tail = node;
this->count++;
15
Inserção no final da lista
bool empty = this->isEmpty();
Node *node = new Node(element);
node->setNext(NULL);
this->tail->setNext(node);
this->tail = node;
if (empty) this->head = node;
this->count++;
16
Exclusão do primeiro elemento
da lista
Node *node = this->head;
this->head = this->head->getNext();
delete node;
this->count--;
17
Exclusão do último elemento da
lista
Node *current = this->head;
while (current->getNext() != this->tail)
current = current->getNext();
Node *node = this->tail;
current->setNext(NULL);
this->tail = current;
delete node;
this->count--;
18
Percorrendo uma lista
Node* current = list.begin();
while (current != NULL) {
cout << current->getElement() << endl;
current = current->getNext();
}
19
Percorrendo uma lista
for (Node* c = list.begin(); c != list.end(); c = c->getNext()) {
cout << c->getElement() << endl;
}
20
Exercício 01
Implementar uma lista de inteiros
Implementar uma lista de float
Implementar uma lista de char
21
Exercício 02
Implementar uma lista genérica
22