IWI131 Programación


Estructuras de Datos: Listas



Departamento de Informática
Universidad Técnica Federico Santa María

Listas

  • Colección o secuencia de valores
  • Pueden contener básicamente cualquier cosa

Creación de Listas

  • Usando corchetes []
  • Usando la función list()

Lista vacía

In [1]:
a = []
b = list()
print(a)
print(b)

[]
[]

Lista con elementos

In [6]:
a = [1,2,3,4]
palabra = "hola"
b = list([palabra,2,[1,2],'3'])
print(a)
print(b)

[1, 2, 3, 4]
['hola', 2, [1, 2], '3']

¿Qué hace la siguiente operación?

In [9]:
c = list("abc")
print(c)

['a', 'b', 'c']
In [7]:
d = list([1,2,3,4])
print(d)

[1, 2, 3, 4]

La función list(ite) convierte a lista al tipo de dato dado por la variable ite. Cada elemento de ite es agregado a una lista.

Rangos

La función range genera una secuencia de números ordenados.

  • Existen varias formas de usar esta función.
  • Se pueden crear listas a partir de las secuencias de range.

range(fin) genera una secuencia de fin números ordenados desde 0 hasta fin-1.

In [11]:
#rango de 3 numeros
a = range(3)
print(a)

range(0, 3)
In [12]:
#usando la funcion list para convertir una secuencia a lista
b = list(a)
print(b)

[0, 1, 2]

range(inicio,fin) genera una secuencia de números ordenados, iniciada en inicio y terminada en fin-1.

In [13]:
#rango de numeros desde el 2 al 7
c = range(2,7)
print(c)

range(2, 7)
In [14]:
#usando la funcion list para convertir una secuencia a lista
d = list(range(2,7))
print(d)

[2, 3, 4, 5, 6]

range(inicio, fin, salto) genera una secuencia de números ordenados, iniciada en inicio, hasta antes de llegar a fin, con saltos entre cada número de la secuencia de salto.

In [16]:
#rango de numeros desde el 2 hasta el 10 con saltos de 3
range(2,10,3)
Out[16]:
range(2, 10, 3)
In [19]:
#usando la funcion list para convertir una secuencia a lista
f = list(range(2,10,3))
print(f)

[2, 5, 8]

Indexación en listas

Las listas tienen índices para enumerar sus elementos, de manera similar que con strings.

In [20]:
a = [1,2,3,4]
print(a[1])

2
In [21]:
print(a[10])

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-21-45a6398849db> in <module>()
----> 1 print(a[10])

IndexError: list index out of range

A diferencia de los strings, las listas son tipos de datos mutables. El índice puede ser usado para modificar un elemento de la lista

In [22]:
colores = ["azul", "rojo", "verde", "amarillo"]
print("Lista antes de modificar un elemento por el indice")
print(colores)
colores[0] = "fucsia"
print("Lista despues de modificar un elemento por el indice")
print(colores)

Lista antes de modificar un elemento por el indice
['azul', 'rojo', 'verde', 'amarillo']
Lista despues de modificar un elemento por el indice
['fucsia', 'rojo', 'verde', 'amarillo']

Las listas también poseen índices negativos.

In [23]:
a = [1,2,3,4]
#imprime por pantalla el penultimo elemento de la lista
print(a[-2])

3

La notación l[inicio:fin] también es válida para listas, solo que obtiene una lista con los elementos desde el índice inicio hasta el índice fin-1.

In [24]:
a = list(range(2,20))
print(a[4:15])

[6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

Operaciones sobre listas

Algunas operaciones de listas son análogas a las operaciones de strings:

  • Concatenación de lista (+)
  • Repetición de listas (*)
  • Verificar si un elemento está en en la lista
  • Eliminar el elemento i-ésimo de una lista

Concatenación de listas

El operador suma (+) permite juntar dos listas

In [25]:
a = [1,2,3]
b = [4,6,8]
c = a + b
d = b + a
print(c)
print(d)

[1, 2, 3, 4, 6, 8]
[4, 6, 8, 1, 2, 3]
In [26]:
[1,2] + [2,6]
Out[26]:
[1, 2, 2, 6]

Repetición de listas

El operador multiplicación (*) permite repetir una lista

In [27]:
a = [1,4,6]
c = a*3
print(c)

[1, 4, 6, 1, 4, 6, 1, 4, 6]

Verificar si elemento se encuentra en la lista

La instrucción in permite verificar si un elemento está contenido en la lista.

In [28]:
a = [1,2,3,4]
In [29]:
10 not in a
Out[29]:
True
In [30]:
6 in a
Out[30]:
False

¿Se muéstra el mensaje en el siguiente ejemplo?

In [31]:
a = [1,2,3,4]
verificar = 3 in a
if verificar:
    print("correcto")

correcto

Eliminar un elemento de la lista

  • Utilizando la instrucción del, es posible eliminar un elemento de la lista.
  • Se debe indicar el índice de la lista a eliminar.
In [32]:
a = [1,2,3,4,2]
print("lista antes de eliminar el elemento a[-3]")
print(a)
del a[-3]
print("lista despues de eliminar a[-3]")
print(a)

lista antes de eliminar el elemento a[-3]
[1, 2, 3, 4, 2]
lista despues de eliminar a[-3]
[1, 2, 4, 2]

Funciones que aceptan listas como parámetros

Longitud de una lista

La función len(lista) entrega la cantidad de elementos de la lista ingresada como parámetro.

In [33]:
a = [1,2,3,4]
c = len(a)
print("La cantidad de elementos de la lista es",c)

La cantidad de elementos de la lista es 4
In [35]:
b = [[1,2,3,4]]
d = len(b[0])
print("La cantidad de elementos de la lista es",d)

La cantidad de elementos de la lista es 4

¿Qué ocurre con la cantidad de elementos de las listas vacías?

In [36]:
print(len([]))

0
In [37]:
print(len(list()))

0

Suma de los valores de una lista

Usando la función sum(lista), se puede determinar la suma de los elementos de una lista.

In [38]:
sum([1,5,3])
Out[38]:
9
In [39]:
sum([1.0,5.4,3])
Out[39]:
9.4

¿Que hace el siguiente programa?

In [40]:
b = 5
a = [1,2,4,b]
c = sum(a)/len(a)
print(round(c))

3

Mínimo en una lista de elementos

La función min(lista) entrega el valor mínimo en la lista ingresada como parámetro.

In [41]:
m = min([1,6,2,-1])
print(m)

-1

Máximo en una lista de elementos

La función max(lista) entrega el valor máximo en la lista ingresada como parámetro.

In [42]:
m = max([1,6,2,-1])
print(m)

6

Métodos para listas

  • Agregar un elemento x: l.append(x)
  • Agregar un elemento x en una posición pos: l.insert(pos,x)
  • Contar la aparición de un elemento x: l.count(x)
  • Obtener el índice de un elemento x: l.index(x)
  • Eliminar un elemento x: l.remove(x)
  • Invertir una lista: l.reverse()
  • Ordenar una lista: l.sort()

Importante: recordar que los métodos operan sobre una variable que es de cierto tipo. En este caso l es una lista.

Agregar un elemento

  • Usando append, se agregará un elemento al final de la lista.
In [48]:
a = [1,2,3,4]
print("lista antes de agregar un elemento")
print(a)
#agregar un 4 al final de la lista
a.append(4)
print("lista despues de agregar un elemento")
print(a)

lista antes de agregar un elemento
[1, 2, 3, 4]
lista despues de agregar un elemento
[1, 2, 3, 4, 4]

Agregar un elemento en una posición

Usando el método insert se puede agregar un elemento en la lista en la posición i-ésima ingresada como parámetro.

In [52]:
a = [1,2,3,4]
print("lista antes de agregar un elemento")
print(a)
#agregar un 10 en a[2]
a.insert(2,10)
print("lista despues de agregar un elemento")
print(a)

lista antes de agregar un elemento
[1, 2, 3, 4]
lista despues de agregar un elemento
[1, 2, 10, 3, 4]

Contar la aparición de un elemento en una lista

El método count cuenta cuántas veces aparece un elemento en la lista.

In [53]:
a = list("paralelepipedo")
b = a.count("p")
print(b)

3

Índice de un elemento

  • El método index entrega la posición de un elemento en la lista
  • Si hay más de un elemento en la lista, entrega la posición del primer elemento (sentido izquierda - derecha).
  • El elemento debe existir.
In [54]:
a = [1,2,3,4,3]
In [55]:
a.index(3)
Out[55]:
2
In [56]:
a.index(214)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-56-732a7ae971c1> in <module>()
----> 1 a.index(214)

ValueError: 214 is not in list

¿Cómo se puede asegurar que al usar index no habrá error?

In [57]:
a = [1,2,3,4,3]
if 214 in a:
    print("El elemento 214 esta en el indice",a.index(214))

if 3 in a:
    print("El elemento 3 esta en el indice",a.index(3))

El elemento 3 esta en el indice 2

Eliminar un elemento de una lista

  • El método remove elimina el elemento ingresado como parámetro
  • Si hay más de un elemento en la lista, elimina el primer elemento (sentido izquierda - derecha).
  • El elemento debe existir en la lista
In [58]:
a = [1,2,3,5,3]
print("lista antes de eliminar el elemento 3")
print(a)
#eliminar el elemento 3 de la lista
a.remove(3)
print("lista despues de eliminar")
print(a)

lista antes de eliminar el elemento 3
[1, 2, 3, 5, 3]
lista despues de eliminar
[1, 2, 5, 3]
In [59]:
a.remove(7)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-59-f5d8d6a28254> in <module>()
----> 1 a.remove(7)

ValueError: list.remove(x): x not in list

¿Cómo se puede evitar este error al intentar eliminar un elemento?

In [60]:
a = [1,2,3,5,3]
if 7 in a:
    a.remove(7)

Invertir una lista

El método reverse invierte el orden de los elementos de una lista.

In [61]:
a = [4,1,10,5]
print("lista antes de invertir")
print(a)
a.reverse()
print("lista despues de invertir")
print(a)

lista antes de invertir
[4, 1, 10, 5]
lista despues de invertir
[5, 10, 1, 4]

Ordenar una lista

El método sort ordena los elementos de una lista en orden creciente.

In [ ]:
a = [4,1,10,6]
print("lista antes de ordenar")
print(a)
a.sort()
print("lista despues de ordenar")
print(a)

¿Cómo ordenar los elementos de una lista en orden decreciente?

In [62]:
a = [4,1,10,6]
print("lista antes de ordenar")
print(a)
a.sort()
a.reverse()
print("lista despues de ordenar")
print(a)

lista antes de ordenar
[4, 1, 10, 6]
lista despues de ordenar
[10, 6, 4, 1]

Ciclo for en listas

  • Un ciclo for puede ser usado para iterar sobre listas.
In [63]:
lista = [1,4,"s",[1,5]]
for elem in lista:
    print("elem =",elem)

elem = 1
elem = 4
elem = s
elem = [1, 5]

Utilizando range en un ciclo for

In [64]:
suma = 0
for k in range(3,6):
    suma += k**2
print(suma)

50
In [67]:
for i in range(5):
    print("hola persona "+str(i+1))

hola persona 1
hola persona 2
hola persona 3
hola persona 4
hola persona 5
In [68]:
for i in range(2,5):
    print(i)

2
3
4

Iterables (hasta el momento):

  • Strings
  • Listas
  • range

Equivalencia entre ciclo while y ciclo for

¿Son equivalentes los siguientes códigos?

In [69]:
contador = 0
suma = 0
while contador < 5:
    suma += contador
    contador += 1
print("La suma es igual a",suma)

La suma es igual a 10
In [70]:
suma = 0
for contador in range(5):
    suma += contador
print("La suma es igual a",suma)

La suma es igual a 10

Iteración de listas usando ciclo while y ciclo for

In [71]:
ramos = ["Progra", "Mate", "Fisica"]
i = 0
while i < len(ramos):
    print("Tengo clases de",ramos[i])
    i += 1

Tengo clases de Progra
Tengo clases de Mate
Tengo clases de Fisica
In [72]:
ramos = ["Progra", "Mate", "Fisica"]
for ramo in ramos:
    print("Tengo clases de",ramo)

Tengo clases de Progra
Tengo clases de Mate
Tengo clases de Fisica
In [73]:
ramos = ["Progra", "Mate", "Fisica"]
horas = ["8:00", "10:00", "12:00"]
i = 0
while i < len(ramos):
    print("Tengo clases de",ramos[i],"a las", horas[i])
    i += 1

Tengo clases de Progra a las 8:00
Tengo clases de Mate a las 10:00
Tengo clases de Fisica a las 12:00
In [78]:
ramos = ["Progra", "Mate", "Fisica"]
horas = ["8:00", "10:00", "12:00"]
print(list(range(len(ramos))))
for i in range(len(ramos)):
    print("Tengo clases de",ramos[i],"a las", horas[i])

[0, 1, 2]
Tengo clases de Progra a las 8:00
Tengo clases de Mate a las 10:00
Tengo clases de Fisica a las 12:00

Ejercicios

1. La desviación estándar es una medida que se usa para cuantificar la variación o dispersión de un conjunto de datos numéricos.

$$ \sigma = \sqrt{\sum_{i}^n \frac{(x_i-\mu)^2}{n-1}} $$

Donde n es la cantidad de datos, μ es el promedio y los xᵢ son cada uno de los datos. Esto significa que hay que hacerlo siguiendo estos pasos:

  • Calcular el promedio de los valores;
  • a cada valor hay que restarle el promedio, y el resultado elevarlo al cuadrado;
  • sumar todos los valores obtenidos;
  • dividir la suma por la cantidad de valores; y
  • sacar la raíz cuadrada del resultado.

Desarrolle la función desviacion_estandar(valores) cuyo parámetro valores sea una lista de números reales. La función debe retornar la desviación estándar de los valores.

>>> desviacion_estandar([1.3, 1.3, 1.3])
0.0
>>> desviacion_estandar([4.0, 1.0, 11.0, 13.0, 2.0, 7.0])
4.88535225615
>>> desviacion_estandar([1.5, 9.5])
5.65685424949

2. La búsqueda secuencial (o lineal) es un método para encontrar un valor en una lista desordenada verificando cada elemento secuencialmente desde el primero hasta que el elemento buscado se encuentra o se llega al final de la lista.

Escriba la función búsqueda_secuencial(lista, elemento) que recibe una lista desordenada y un elemento que se desea encontrar. La función debe retornar la posición del elemento en la lista utilizando una búsqueda secuencial. Si no se encuentra retornar False.

>>> búsqueda_secuencial([11,23,58,31,56,77,43,12,65,19], 31)
3
>>> búsqueda_secuencial([11,23,58,31,56,77,43,12,65,19], 13)
False

3. La búsqueda binaria encuentra la posición de un elemento en una lista ordenada, comparando el elemento con el valor de al medio de la lista, si no son iguales, la mitad en la cual el valor no puede estar es eliminada y la búsqueda continúa en la mitad restante hasta que el valor se encuentre.

Por ejemplo, se desea encontrar el 10 en la siguiente lista:

4 6 10 12 17 25 29

Comparar el elemento buscado con el valor central: 10 < 12, es menor, entonces descartar el lado derecho.

4 6 10            

Comparar el elemento buscado con el valor central: 10 > 6, es mayor, entonces descartar el lado izquierdo.

   6               

Comparar el elemento buscado con el valor central: 10 = 10, es igual, entonces se encontró.

Si hubiesen sido distintos, como no quedan más elementos, el valor buscado no está en la lista.

Escriba la función busqueda_binaria(lista, elemento)que recibe una lista ordenada y un elemento que se desea encontrar. La función debe retornar True si encuentra el elemento en la lista utilizando una búsqueda binaria. Si no se encuentra retornar False.

>>> búsqueda_binaria([0, 1, 3, 8, 14, 18, 19, 34, 52], 3)
True
>>> búsqueda_binaria([0, 1, 3, 8, 14, 18, 19, 34, 52], 17)
False
In [ ]: