Listas encadenadas

Objetivos

Durante esta actividad, los alumnos serán capaces de:

Implementar diversas operaciones sobre listas encadenadas.

Esta actividad promueve las siguientes habilidades, valores y actitudes: análisis y síntesis, capacidad de resolver problemas, creatividad, y uso eficiente de la informática y las telecomunicaciones.

Descripción

Esta actividad puede ser elaborada de manera individual o en parejas.

A partir de la clase LinkedList elaborada en clase (ver código fuente) escribe los métodos que se describen a continuación. Coloca todos los métodos en un archivo llamado linked_list.py. En la parte superior del archivo coloca en comentarios los datos personales de los autores de la tarea. Por ejemplo:

#--------------------------------------------------------------------
# Actividad de programación: Listas encadenadas
# Fecha: 12-Oct-2012
# Autores:
#           1166611 Pepper Pots  
#           1160611 Anthony Stark
#--------------------------------------------------------------------

__getitem__(self, index): Devuelve el elemento en la posición index de esta lista (el primer elemento está en la posición 0). Este método es invocado automáticamente por Python cuando se evalúa la expresión: self[index]. Arroja la excepción TypeError si index no es de tipo entero. Arroja la excepción IndexError si index < 0 o si index ≥ len(self).

Ejemplos:
```
>>> x = LinkedList()
>>> x.insert_back('a')
>>> x.insert_back('b')
>>> x.insert_back('c')
>>> x[0]
'a'
>>> x[2]
'c'
>>> x[True]
...
TypeError: El índice debe ser un número entero
>>> x[3]
...
IndexError: El índice está fuera de rango
```

__setitem__(self, index, value): Asigna value a esta lista en la posición index (el primer elemento está en la posición 0). Este método es invocado automáticamente por Python cuando se ejecuta el enunciado: self[index]=value. Arroja las mismas excepciones que __getitem__.

Ejemplos:

>>> x = LinkedList()
>>> x.insert_back('a')
>>> x.insert_back('b')
>>> x.insert_back('c')
>>> x
['a', 'b', 'c']
>>> x[1] = 'z'
>>> x
['a', 'z', 'c']
>>> x[True] = 'w'
...
TypeError: El índice debe ser un número entero
>>> x[3] = 'w'
...
IndexError: El índice está fuera de rango

__contains__(self, item): Devuelve True si item está contenido en esta lista, o False en caso contrario. Este método es invocado automáticamente por Python cuando se evalúa la expresión: item in self.

Ejemplos:
```
>>> x = LinkedList()
>>> x.insert_back('a')
>>> x.insert_back('b')
>>> x.insert_back('c')
>>> 'b' in x
True
>>> 'z' in x
False
```

index(self, item): Devuelve el índice de la primera ocurrencia de item en esta lista. Arroja la excepción ValueError si la lista no contiene a item.

Ejemplos:

>>> x = LinkedList()
>>> x.insert_back('a')
>>> x.insert_back('b')
>>> x.insert_back('c')
>>> x.index('b')
1
>>> x.index('z')
...
ValueError: 'z' no está en la lista

count(self, item): Devuelve el número de veces que aparece item en esta lista.

Ejemplos:

>>> x = LinkedList()
>>> x.insert_back('a')
>>> x.insert_back('b')
>>> x.insert_back('a')
>>> x.insert_back('c')
>>> x.insert_back('a')
>>> x.count('a')
3
>>> x.count('z')
0

__delitem__(self, index): Elimina de esta lista el elemento en la posición index. Los elementos de la posición index+1 en adelante se recorren una posición hacia abajo. Este método es invocado automáticamente por Python cuando se evalúa la expresión: del self[index]. Arroja las mismas excepciones que __getitem__.

Ejemplos:
```
>>> x = LinkedList()
>>> x.insert_back('a')
>>> x.insert_back('b')
>>> x.insert_back('c')
>>> x
['a', 'b', 'c']
>>> del x[0]
>>> x
['b', 'c']
>>> del x[1]
>>> x
['b']
>>> del x[0]
>>> x
[]
>>> del x[True]
...
TypeError: El índice debe ser un número entero
>>> del x[0]
...
IndexError: El índice está fuera de rango
```

insert(self, index, value): Inserta en esta lista un nuevo nodo con value en la posición index. Los elementos de la posición index en adelante se recorren una posición hacia arriba. Si index ≥ len(self) se inserta value al final. Si index < 0 se inserta value al inicio.

Ejemplos:

>>> x = LinkedList()
>>> x.insert_back('a')
>>> x.insert_back('b')
>>> x.insert_back('c')
>>> x
['a', 'b', 'c']
>>> x.insert(1, 'z')
>>> x
['a', 'z', 'b', 'c']
>>> x.insert(10, 'w')
>>> x
['a', 'z', 'b', 'c', 'w']
>>> x.insert(-10, 'u')
>>> x
['u', 'a', 'z', 'b', 'c', 'w']

remove(self, item): Elimina de esta lista el nodo que contiene la primera ocurrencia del elemento item. Arroja la excepción ValueError si la lista no contiene a item.

Ejemplos:

>>> x = LinkedList()
>>> x.insert_back('a')
>>> x.insert_back('b')
>>> x.insert_back('c')
>>> x
['a', 'b', 'c']
>>> x.remove('c')
>>> x
['a', 'b']
>>> x.remove('a')
>>> x
['b']
>>> x.remove('b')
>>> x
[]
>>> x.remove('a')
...
ValueError: 'a' no está en la lista

¿Qué se debe entregar?

Sube el archivo linked_list.py usando el Sistema de Entrega de Tareas Automatizado. No se aceptan tareas por ningún otro medio.

Fecha límite: Viernes, 12 de octubre.

Evaluación

Esta actividad será evaluada usando los siguientes criterios:

100	La actividad cumple con todos los requerimientos.
-10	No se incluyó en comentario los datos de los autores.
10	El programa fuente contiene errores sintácticos.
50-90	El programa produce algunos errores al momento de correrlo.
DA	La solución es un plagio.

Estructura de datos

Listas encadenadas

Objetivos

Descripción

¿Qué se debe entregar?

Evaluación