Aula 10: Lista - estrutura sequencial indexada

Tópicos

Aulas a distância - Google Meet:

Para verem os vídeos, vocês devem estar logados no e-mail da usp.

Listas

Até aqui, trabalhamos com variáveis simples, capazes de armazenar apenas um tipo, como bool, float e int.

Uma lista (tipo list) em Python é uma sequência de valores de qualquer tipo ou classe tais como int, float, bool, str e até mesmo o próprio list, entre outros.

Existem várias maneiras de criarmos uma lista. A maneira mais simples é envolver os elementos da lista por colchetes ([ e ]). Por exemplo, podemos criar uma lista contendo os anos de obtenção das cinco primeiras conquistas do Brasil em Copas do Mundo de Futebol da seguinte maneira:

>>> anos_conquistas = [1958, 1962, 1970, 1994, 2002]

Observe o uso de colchetes de abertura ([) para marcar o início e o colchetes de fechamento (]) para marcar o final da lista, e os elementos separados por vígula.

Ao contrário do conceito de vetores em linguagem C, que são coleções indexadas homogêneas de dados (todos elementos do vetor são de um mesmo tipo), as listas em Python podem conter vários tipos de dados, sendo, portanto, possível armazenar coleções heterogêneas de dados. Exemplo:

>>> filme = ["De Volta Para O Futuro", 1985, "Robert Zemeckis", ["ficção científica", "aventura"]]

Na lista filme acima, o primeiro elemento representa o nome do filme "De Volta Para O Futuro" do tipo str, o segundo elemento representa o ano 1985 de estréia do filme do tipo int, o terceiro elemento representa o diretor do filme "Robert Zemeckis" do tipo str e o quarto elemento ["ficção científica", "aventura"] representa a lista de gêneros do filme do tipo list.

Índices

Lista são estruturas sequenciais indexadas pois seus elementos podem ser acessados sequencialmente utilizando índices. Por convenção do Python, o primeiro elemento da lista tem índice 0, o segundo tem índice 1, e assim por diante. Observe que, por começar pelo índice zero, o último elemento da lista anos_conquistas, o ano 2002, tem índice 4, sendo que essa lista tem comprimento 5.

O acesso a elementos da lista pode ser feito através da sintaxe: nome_da_lista[índice].

Veja os exemplos abaixo digitados no Python Shell:

>>> anos_conquistas[0]
1958
>>> anos_conquistas[1]
1962
>>> anos_conquistas[2]
1970
>>> anos_conquistas[3]
1994
>>> anos_conquistas[4]
2002
>>> filme[0]
'De Volta Para O Futuro'
>>> filme[1]
1985
>>> filme[2]
'Robert Zemeckis'
>>> filme[3]
['ficção científica', 'aventura']

Índices negativos indicam elementos em ordem inversa, ou seja, da direita para a esquerda ao invés de da esquerda para a direita, sendo o último elemento indicado pelo índice -1. Veja os exemplos abaixo digitados no Python Shell:

>>> anos_conquistas[-1]
2002
>>> anos_conquistas[-2]
1994
>>> anos_conquistas[-3]
1970
>>> anos_conquistas[-4]
1962
>>> anos_conquistas[-5]
1958
>>> filme[-1]
['ficção científica', 'aventura']
>>> filme[-2]
'Robert Zemeckis'
>>> filme[-3]
1985
>>> filme[-4]
'De Volta Para O Futuro'

Um erro comum em programas é a utilização de índices inválidos, o que gera a mensagem de erro: list index out of range. Veja os exemplos abaixo digitados no Python Shell:

>>> anos_conquistas[5]
Traceback (most recent call last):
File "<pyshell#89>", line 1, in <module>
anos_conquistas[5]
IndexError: list index out of range
>>> anos_conquistas[-6]
Traceback (most recent call last):
File "<pyshell#98>", line 1, in <module>
anos_conquistas[-6]
IndexError: list index out of range
>>> filme[4]
Traceback (most recent call last):
File "<pyshell#108>", line 1, in <module>
filme[4]
IndexError: list index out of range
>>> filme[-5]
Traceback (most recent call last):
File "<pyshell#124>", line 1, in <module>
filme[-5]
IndexError: list index out of range

Comprimento de uma lista

O número de elementos (comprimento) de uma lista pode ser obtido pela função len().

>>> len(anos_conquistas)
5
>>> len(filme)
4

Modificando elementos de uma lista

Para modificar um elemento de uma lista, basta realizar um comando de atribuição.
Por exemplo, se quisermos mudar o nome do filme para a sua versão em inglês, podemos usar:

>>> filme[0] = "Back to the Future"
>>> print(filme)
['Back to the Future', 1985, 'Robert Zemeckis', ['ficção científica', 'aventura']]

Adicionando elementos a uma lista (método append)

Para adicionar mais elementos a uma lista existente, podemos usar o método append(). Por exemplo, podemos adicionar a companhia produtora ao filme usando:

>>> filme.append("Amblin Entertainment")
>>> print(filme)
['Back to the Future', 1985, 'Robert Zemeckis', ['ficção científica', 'aventura'], 'Amblin Entertainment']
>>> len(filme)
5

Referências VS clones

A atribuição de uma lista em uma variável A a uma segunda variável B não cria uma nova lista. As duas variáveis estarão referenciando a mesma lista na memória. Isto significa que alterações na lista A afetam B e vice-versa:

>>> A = ["Bento Gonçalves", "Campos do Jordão", "Gramado"]
>>> B = A
>>> B.append("Ouro Preto")
>>> print(B)
['Bento Gonçalves', 'Campos do Jordão', 'Gramado', 'Ouro Preto']
>>> print(A)
['Bento Gonçalves', 'Campos do Jordão', 'Gramado', 'Ouro Preto']
>>> id(A)
139789181142280
>>> id(B)
139789181142280
>>> id(A) == id(B)
True
>>> A is B
True

Cada objeto em Python, incluindo listas, possui um identificador exclusivo (número inteiro único) que pode ser acessado usando a função id() do Python. Observe que no exemplo acima, as listas A e B possuem o mesmo identificador, confirmando que elas correspondem à mesma lista na memória.
O teste id(A) == id(B) pode ser igualmente obtido através do comando A is B.

Em algumas situações, no entanto, precisamos, de fato, criar uma réplica/clone na memória de uma lista existente.
Para isso podemos usar o comando B = list(A). Note que nesse caso alterações posteriores em uma das listas não afetam a sua cópia.

>>> A = ["Bento Gonçalves", "Campos do Jordão", "Gramado"]
>>> B = list(A)
>>> B.append("Ouro Preto")
>>> print(B)
['Bento Gonçalves', 'Campos do Jordão', 'Gramado', 'Ouro Preto']
>>> print(A)
['Bento Gonçalves', 'Campos do Jordão', 'Gramado']
>>> id(A)
139789180697672
>>> id(B)
139789156561992
>>> id(A) == id(B)
False
>>> A is B
False

Concatenação de listas usando +

Um Python, podemos gerar uma nova lista a partir da concatenação de duas listas existentes usando o operador de adição +. Note que as listas originais são preservadas e uma nova lista é criada com um total de elementos igual a soma dos comprimentos das duas primeiras. Veja os exemplos abaixo digitados no Python Shell:

>>> A = ["Bento Gonçalves", "Campos do Jordão", "Gramado"]
>>> B = ["Ouro Preto", "Fortaleza", "Maceió", "Rio de Janeiro"]
>>> C = A + B
>>> print(A)
['Bento Gonçalves', 'Campos do Jordão', 'Gramado']
>>> print(B)
['Ouro Preto', 'Fortaleza', 'Maceió', 'Rio de Janeiro']
>>> print(C)
['Bento Gonçalves', 'Campos do Jordão', 'Gramado', 'Ouro Preto', 'Fortaleza', 'Maceió', 'Rio de Janeiro']
>>> len(C) == len(A) + len(B)     #7 == 3 + 4
True

Note que a concatenação não possui propriedade comutativa, pois a ordem dos elementos na lista de saída depende da ordem dos operandos.

>>> sabores = ["baunilha", "chocolate", "morango"] + ["napolitano", "flocos"]
>>> print(sabores)
['baunilha', 'chocolate', 'morango', 'napolitano', 'flocos']
>>> sabores = ["napolitano", "flocos"] + ["baunilha", "chocolate", "morango"]
>>> print(sabores)
['napolitano', 'flocos', 'baunilha', 'chocolate', 'morango']

Se as duas listas A e B possuem elementos em comum, após a concatenação, estes serão repetidos na lista produzida (veja o caso dos elementos 3, 5 e 7 no exemplo abaixo).

>>> impares = [1, 3, 5, 7, 9]    #cinco primeiros números ímpares
>>> primos = [2, 3, 5, 7, 11]    #cinco primeiros números primos
>>> uniao = impares + primos
>>> print(uniao)
[1, 3, 5, 7, 9, 2, 3, 5, 7, 11]

Método append VS concatenação de listas

Observe que os seguintes três trechos de código produzem o mesmo efeito:

>>> sabores = ["baunilha", "chocolate", "morango"]
>>> sabores = sabores + ["flocos"]
>>> print(sabores)
['baunilha', 'chocolate', 'morango', 'flocos']

>>> sabores = ["baunilha", "chocolate", "morango"]
>>> sabores += ["flocos"]
>>> print(sabores)
['baunilha', 'chocolate', 'morango', 'flocos']

>>> sabores = ["baunilha", "chocolate", "morango"]
>>> sabores.append("flocos")
>>> print(sabores)
['baunilha', 'chocolate', 'morango', 'flocos']

Apesar deles produzirem o mesmo resultado, nesse caso é preferível utilizar o método append(), pois a concatenação gera uma cópia da lista toda e a variável sabores passa a referenciar essa nova lista criada, sendo, portanto, uma operação mais custosa.

Repetição de listas usando *

Em Python podemos multiplicar uma lista por um número inteiro. O efeito é a criação de uma nova lista contendo a repetição dos elementos da primeira pelo número de vezes indicado. Veja o exemplo abaixo:

>>> [0, 1]*3        #O mesmo que: [0, 1] + [0, 1] + [0, 1]
[0, 1, 0, 1, 0, 1]

Laços para percorrer os elementos de uma lista

Como vimos, o acesso a elementos de uma lista pode ser feito através da sintaxe nome_da_lista[índice].

Note, no entanto, que podemos usar um variável inteira para indicar o índice, de modo que podemos usar a seguinte construção para percorrer os elementos da lista anos_conquistas = [1958, 1962, 1970, 1994, 2002].

?
1
2
3
4
i = 0
while i < len(anos_conquistas):
    print(anos_conquistas[i])
    i += 1
No programa acima, observe que a variável i recebe o valor zero que corresponde ao primeiro índice e, enquanto o índice for menor que o comprimento da lista (= len(anos_conquistas)), o elemento de índice i é impresso.

Repetições com for

O Python possui uma segunda estrutura de repetição mais compacta que pode ser empregada para acessar diretamente os elementos de uma lista sem mencionar explicitamente os seus índices.
?
1
2
for ano in anos_conquistas:
    print(ano)

Em programas em que se faz necessário o uso de índices, ainda podemos usar o comando de repetição for. Por exemplo, com relação à lista anos_conquistas, se quisermos imprimir o texto abaixo:

1o. título: 1958
2o. título: 1962
3o. título: 1970
4o. título: 1994
5o. título: 2002

podemos usar o seguinte código.
?
1
2
3
for i in [0,1,2,3,4]:
    print("%do. título:"%(i+1),anos_conquistas[i])
#fim
A ideia acima é usar uma lista dos índices no laço for, porém, uma limitação evidente do código acima é a dificuldade de se ajustar a listas de diferentes tamanhos. Por exemplo, no caso de uma lista com centenas de elementos, teríamos que criar uma lista grande, sendo inviável a sua digitação. Fora que muitas vezes só conseguimos descobrir o tamanho de uma lista em tempo de execução.

Felizmente, o Python possui um comando que permite a construção de uma lista de inteiros de tamanho arbitrário, com elementos seguindo uma regra de formação de acordo com uma progressão aritmética. Teste no Python Shell os seguintes comandos:

>>> list(range(10))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> list(range(5,15))
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
>>> list(range(5,10))
[5, 6, 7, 8, 9]
>>> list(range(4,20,2))
[4, 6, 8, 10, 12, 14, 16, 18]
>>> list(range(20,10,-1))
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11]
>>> list(range(20,10,-2))
[20, 18, 16, 14, 12]

Os comandos acima possuem uma dentre três possíveis formas:

  1. list(range(fim))
  2. list(range(início, fim))
  3. list(range(início, fim, passo))
Caso você não informe, será considerado o valor 0 (zero) para o início e 1 para o passo. Note que o parâmetro passo corresponde à razão da PA. O valor de início corresponde sempre ao primeiro elemento da lista gerada e o valor de fim nunca é incluído na listagem, que sempre termina no elemento anterior.

Com o uso do novo comando acima, podemos então reescrever o código anterior da seguinte forma:

?
1
2
3
for i in list(range(len(anos_conquistas))):
    print("%do. título:"%(i+1),anos_conquistas[i])
#fim
A solução acima funciona para listas de tamanho arbitrário, porém, no caso de listas grandes, ainda teremos o problema do desperdício de memória. Note que se a lista contiver milhares de elementos, o comando list(range(len(lista))) vai gerar uma segunda lista do mesmo tamanho da primeira, gerando um desperdício de milhares de elementos, em comparação com a solução via laço while que utiliza uma única variável de controle.

Para resolver esse problema podemos usar simplesmente:

?
1
2
3
for i in range(len(anos_conquistas)):
    print("%do. título:"%(i+1),anos_conquistas[i])
#fim

A série retornada pelo comando range(len(lista)) é um objeto iterável do tipo range e os elementos nela contidos serão gerados sob demanda durante o for, evitando o desperdício de memória.

Problema 1:

Dados n > 0 e uma sequência com n números reais, imprimí-los na ordem inversa a da leitura.

Dica: Criar uma lista vazia (seq = []) e usar append.

Solução 1:

Vamos fazer do modo tradicional, imprimindo dentro de um while.

?
1
2
3
4
5
6
7
8
9
10
11
12
n = int(input("Digite n: "))
seq = []
i = 0
while i < n:
    num = float(input("Digite o %do. num: "%(i+1)))
    seq.append(num)
    i += 1
 
i = n-1
while i >= 0:
    print(seq[i])
    i -= 1

Solução 2:

Solução alternativa usando índices negativos.

?
1
2
3
4
5
6
7
8
9
10
11
12
n = int(input("Digite n: "))
seq = []
i = 0
while i < n:
    num = float(input("Digite o %do. num: "%(i+1)))
    seq.append(num)
    i += 1
 
i = -1
while i >= -n:
    print(seq[i])
    i -= 1

Solução 3:

Solução alternativa usando o comando for.

?
1
2
3
4
5
6
7
8
9
n = int(input("Digite n: "))
 
seq = []
for i in range(n):
    num = float(input("Digite o %do. num: "%(i+1)))
    seq.append(num)
 
for i in range(n-1, -1, -1):
    print(seq[i])

Solução 4:

Outra solução alternativa usando o comando for com índices negativos.

?
1
2
3
4
5
6
7
8
9
n = int(input("Digite n: "))
 
seq = []
for i in range(n):
    num = float(input("Digite o %do. num: "%(i+1)))
    seq.append(num)
 
for i in range(-1, -n-1, -1):
    print(seq[i])

Solução 5:

No Python, é possível fazer: print(seq.reverse()).

?
1
2
3
4
5
6
7
8
9
10
n = int(input("Digite n: "))
 
seq = []
for i in range(n):
    num = float(input("Digite o %do. num: "%(i+1)))
    seq.append(num)
 
seq.reverse()
for x in seq:
    print(x)

Problema 2:

Dados n > 0 lançamentos de uma roleta (números entre 0 e 36), calcular a frequência de cada número.

Dica: Criar uma lista com 37 zeros.

Solução 1:

Solução usando o comando while.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n = int(input("Digite n: "))
 
freq = []
i = 0
while i < 37:
    freq.append(0)
    i += 1
 
i = 0
while i < n:
    num = int(input("roleta: "))
    freq[num] += 1      
    i += 1
 
i = 0
while i < 37:
    print("freq.rel.(%d): %f"%(i,freq[i]/n))
    i += 1

Solução 2:

Solução mais compacta usando freq = [0]*37 para a criação da lista com 37 zeros.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
n = int(input("Digite n: "))
 
freq = [0]*37
i = 0
while i < n:
    num = int(input("roleta: "))
    freq[num] += 1      
    i += 1
 
i = 0
while i < 37:
    print("freq.rel.(%d): %f"%(i,freq[i]/n))
    i += 1

Solução 3:

Solução alternativa usando o comando for.

?
1
2
3
4
5
6
7
8
9
10
11
12
n = int(input("Digite n: "))
 
freq = [0]*37
 
for i in range(n):
    num = int(input("roleta: "))
    freq[num] += 1
 
i = 0
for x in freq:
    print("freq.rel.(%d): %f"%(i,x/n))
    i += 1   

Solução 4:

Solução alternativa que simula a roleta usando o gerador de números pseudo-aleatórios do módulo random do Python, ao invés de solicitar a entrada manual dos n lançamentos.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
import random
n = int(input("Digite n: "))
 
freq = [0]*37
 
for i in range(n):
    num = random.randrange(0, 37)
    freq[num] += 1
 
i = 0
for x in freq:
    print("freq.rel.(%d): %f"%(i,x/n))
    i += 1   

Problema 3:

Dada uma sequência de n > 0 números reais, imprimi-los eliminando as repetições.

Solução 1:

Solução usando while.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int(input("Digite n: "))
 
seq = []
for i in range(n):
    num = float(input("Digite o %do. num: "%(i+1)))
    rep = False
    j = 0
    while j < len(seq) and rep == False:
        if seq[j] == num:
            rep = True
        j += 1
    if rep == False: # if not rep:
        seq.append(num)
 
print(seq)

Solução 2:

Solução usando for.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
n = int(input("Digite n: "))
 
seq = []
for i in range(n):
    num = float(input("Digite o %do. num: "%(i+1)))
    rep = False
    for x in seq:
        if x == num:
            rep = True
    if rep == False: # if not rep:
        seq.append(num)
 
print(seq)

Solução 3:

Solução compacta, aproveitando o fato de que o Python permite testar diretamente se um elemento não faz parte de uma lista,
através do comando if num not in seq:

?
1
2
3
4
5
6
7
8
9
n = int(input("Digite n: "))
 
seq = []
for i in range(n):
    num = float(input("Digite o %do. num: "%(i+1)))
    if num not in seq:
        seq.append(num)
 
print(seq)

Problema 4:

Dados dois números naturais n e m e duas sequências ordenadas com n > 0 e m > 0 números inteiros, criar uma lista contendo a sequência ordenada com todos os elementos das duas sequências originais sem repetição.

Sugestão: Imagine uma situação real, por exemplo, dois fichários de uma biblioteca.

Solução 1:

Cada sequência ordenada fornecida é lida em uma lista correspondente já eliminando possíveis elementos repetidos, usando a solução empregada no problema anterior. As duas listas resultantes seq1 e seq2 são então percorridas, usando as variáveis i e j como seus respectivos índices, copiando de modo intercalado para uma lista de saída seq3 sempre o menor valor entre seq1[i] e seq2[j].

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
n = int(input("Digite n: "))
seq1 = []
for i in range(n):
    num = int(input("Digite o %do. num: "%(i+1)))
    if num not in seq1:
        seq1.append(num)   
 
m = int(input("Digite m: "))
seq2 = []
for i in range(m):
    num = int(input("Digite o %do. num: "%(i+1)))
    if num not in seq2:
        seq2.append(num)   
 
seq3 = []
i,j = 0,0
while i < len(seq1) and j < len(seq2):
    if seq1[i] < seq2[j]:
        seq3.append(seq1[i])
        i += 1
    elif seq2[j] < seq1[i]:
        seq3.append(seq2[j])
        j += 1
    else:   # seq1[i] == seq2[j]
        seq3.append(seq1[i])
        i += 1
        j += 1
 
while i < len(seq1):
    seq3.append(seq1[i])
    i += 1
 
while j < len(seq2):
    seq3.append(seq2[j])
    j += 1
 
print(seq3)

Solução 2:

Solução similar à anterior, porém durante o processo de intercalação, os casos em que i ou j excedem o último índice válido de suas respectivas listas é tratado diretamente dentro do mesmo laço que trata os demais casos em que os dois índices são válidos.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
n = int(input("Digite n: "))
seq1 = []
for i in range(n):
    num = int(input("Digite o %do. num: "%(i+1)))
    if num not in seq1:
        seq1.append(num)   
 
m = int(input("Digite m: "))
seq2 = []
for i in range(m):
    num = int(input("Digite o %do. num: "%(i+1)))
    if num not in seq2:
        seq2.append(num)   
 
seq3 = []
i,j = 0,0
while i < len(seq1) or j < len(seq2):
    if i == len(seq1):
        seq3.append(seq2[j])
        j += 1
    elif j == len(seq2):
        seq3.append(seq1[i])
        i += 1
    elif seq1[i] < seq2[j]:
        seq3.append(seq1[i])
        i += 1
    elif seq2[j] < seq1[i]:
        seq3.append(seq2[j])
        j += 1
    else:   # seq1[i] == seq2[j]
        seq3.append(seq1[i])
        i += 1
        j += 1
 
print(seq3)

Solução 3:

Idêntica à solução anterior, exceto que exploramos o fato de que as duas sequências fornecidas estão ordenadas, de modo que para eliminar seus elementos repetidos durante o laço de leitura, basta comparar com o último valor já lido na lista.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
n = int(input("Digite n: "))
num = int(input("Digite o 1o. num: "))
seq1 = [num]
for i in range(1,n):
    num = int(input("Digite o %do. num: "%(i+1)))
    if num != seq1[len(seq1)-1]:  #compara com o último valor inserido em seq1.
        seq1.append(num)   
  
m = int(input("Digite m: "))
num = int(input("Digite o 1o. num: "))
seq2 = [num]
for i in range(1,m):
    num = int(input("Digite o %do. num: "%(i+1)))
    if num != seq2[len(seq2)-1]:  #compara com o último valor inserido em seq2.
        seq2.append(num)   
  
seq3 = []
i,j = 0,0
while i < len(seq1) or j < len(seq2):
    if i == len(seq1):
        seq3.append(seq2[j])
        j += 1
    elif j == len(seq2):
        seq3.append(seq1[i])
        i += 1
    elif seq1[i] < seq2[j]:
        seq3.append(seq1[i])
        i += 1
    elif seq2[j] < seq1[i]:
        seq3.append(seq2[j])
        j += 1
    else:   # seq1[i] == seq2[j]
        seq3.append(seq1[i])
        i += 1
        j += 1
         
print(seq3)