Estás en:   ArielOrtiz.info > Estructura de datos > Listas encadenadas

Estructura de datos

• Noticias
• Asesoría
• Calificaciones
• Exámenes semanales
• Reglas del juego
• Recursos en línea
• Bibliografía
• Temario

Listas encadenadas

Objetivos

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

• Implementar en Java 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 tc1018.util.LinkedList<E> elaborada en clase (ver código fuente) escribe los métodos que se describen a continuación. Todos los métodos deben ir en el archivo LinkedList.java. 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: 14-Abr-2013
 * Autores:
 *           1166611 Pepper Pots  
 *           1160611 Anthony Stark
 *--------------------------------------------------------------------*/

Prueba tu código usando la siguiente clase de JUnit:

package tc1018.util;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

import java.util.NoSuchElementException;

import org.junit.Before;
import org.junit.Test;

public class TestLinkedList {

    private LinkedList<String> emptyStringList;
    private LinkedList<String> stringList;
    private LinkedList<Integer> integerList;

    // Este método se ejecuta siempre antes de cada "Test".
    @Before
    public void setUp() throws Exception {
        emptyStringList = new LinkedList<>();
        stringList = new LinkedList<>();
        for (char c = 'a'; c <= 'z'; c++) {
            stringList.addLast(Character.toString(c));
        }
        integerList = new LinkedList<>();
        integerList.addLast(4);
        integerList.addLast(8);
        integerList.addLast(15);
        integerList.addLast(16);
        integerList.addLast(23);
        integerList.addLast(42);
    }

    @Test
    public void testAddFirst() {
        stringList.addFirst("#");
        stringList.addFirst("*");
        stringList.addFirst("&");
        assertEquals(29, stringList.size());
        assertEquals("[&, *, #, a, b, c, d, e, f, g, h, i, j, "
                + "k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z]",
                stringList.toString());
        integerList.addFirst(1);
        integerList.addFirst(2);
        integerList.addFirst(3);
        assertEquals(9, integerList.size());
        assertEquals("[3, 2, 1, 4, 8, 15, 16, 23, 42]", integerList.toString());
        emptyStringList.addFirst("aa");
        emptyStringList.addFirst("bb");
        emptyStringList.addFirst("cc");
        assertEquals(3, emptyStringList.size());
        assertEquals("[cc, bb, aa]", emptyStringList.toString());
    }

    @Test
    public void testRemoveFirst() {
        assertEquals("a", stringList.removeFirst());
        assertEquals("b", stringList.removeFirst());
        assertEquals("c", stringList.removeFirst());
        assertEquals(23, stringList.size());
        assertEquals("[d, e, f, g, h, i, j, k, l, m, n, o, p, "
                + "q, r, s, t, u, v, w, x, y, z]", stringList.toString());
        assertEquals(Integer.valueOf(4), integerList.removeFirst());
        assertEquals(Integer.valueOf(8), integerList.removeFirst());
        assertEquals(Integer.valueOf(15), integerList.removeFirst());
        assertEquals(Integer.valueOf(16), integerList.removeFirst());
        assertEquals(2, integerList.size());
        assertEquals("[23, 42]", integerList.toString());
        try {
            emptyStringList.removeFirst();
            fail();
        } catch (NoSuchElementException e) {
        }
    }

    @Test
    public void testGet() {
        assertEquals("a", stringList.get(0));
        assertEquals("z", stringList.get(25));
        assertEquals(Integer.valueOf(16), integerList.get(3));
        assertEquals(Integer.valueOf(42), integerList.get(5));
        try {
            emptyStringList.get(0);
            fail();
        } catch (IndexOutOfBoundsException e) {
        }
        try {
            stringList.get(-1);
            fail();
        } catch (IndexOutOfBoundsException e) {
        }
        try {
            integerList.get(10);
            fail();
        } catch (IndexOutOfBoundsException e) {
        }
    }

    @Test
    public void testSet() {
        assertEquals("a", stringList.set(0, "#"));
        assertEquals("z", stringList.set(25, "*"));
        assertEquals("n", stringList.set(13, "&"));
        assertEquals("[#, b, c, d, e, f, g, h, i, j, k, l, m, "
                + "&, o, p, q, r, s, t, u, v, w, x, y, *]",
                stringList.toString());
        assertEquals(Integer.valueOf(16), integerList.set(3, 1));
        assertEquals(Integer.valueOf(42), integerList.set(5, 2));
        assertEquals("[4, 8, 15, 1, 23, 2]", integerList.toString());
        try {
            emptyStringList.set(0, "a");
            fail();
        } catch (IndexOutOfBoundsException e) {
        }
        try {
            stringList.set(-1, "r");
            fail();
        } catch (IndexOutOfBoundsException e) {
        }
        try {
            integerList.set(10, 4);
            fail();
        } catch (IndexOutOfBoundsException e) {
        }
    }

    @Test
    public void testContains() {
        assertTrue(stringList.contains("a"));
        assertTrue(stringList.contains("z"));
        assertTrue(integerList.contains(8));
        assertTrue(integerList.contains(42));
        assertFalse(emptyStringList.contains("a"));
        assertFalse(stringList.contains("aa"));
        assertFalse(stringList.contains("cc"));
        assertFalse(integerList.contains(9));
        assertFalse(integerList.contains(43));
    }

    @Test
    public void testCount() {
        stringList.addLast("z");
        stringList.addLast("a");
        stringList.addLast("z");
        assertEquals(2, stringList.count("a"));
        assertEquals(1, stringList.count("b"));
        assertEquals(3, stringList.count("z"));
        assertEquals(0, stringList.count("*"));
        integerList.addLast(4);
        integerList.addLast(23);
        assertEquals(2, integerList.count(4));
        assertEquals(2, integerList.count(23));
        assertEquals(1, integerList.count(42));
        assertEquals(0, integerList.count(43));
    }

    @Test
    public void testIndexOf() {
        assertEquals(0, stringList.indexOf("a"));
        assertEquals(25, stringList.indexOf("z"));
        assertEquals(1, integerList.indexOf(8));
        assertEquals(5, integerList.indexOf(42));
        assertEquals(-1, emptyStringList.indexOf("a"));
        assertEquals(-1, stringList.indexOf("*"));
        assertEquals(-1, integerList.indexOf(43));
    }

    @Test
    public void testLastIndexOf() {
        stringList.addLast("a");
        stringList.addLast("z");
        assertEquals(26, stringList.lastIndexOf("a"));
        assertEquals(1, stringList.lastIndexOf("b"));
        assertEquals(27, stringList.lastIndexOf("z"));
        integerList.addLast(8);
        assertEquals(0, integerList.lastIndexOf(4));
        assertEquals(6, integerList.lastIndexOf(8));
        assertEquals(5, integerList.lastIndexOf(42));
        assertEquals(-1, emptyStringList.lastIndexOf("a"));
        assertEquals(-1, stringList.lastIndexOf("*"));
        assertEquals(-1, integerList.lastIndexOf(43));
    }

    @Test
    public void testAdd() {
        stringList.add(26, "*");
        stringList.add(0, "#");
        stringList.add(13, "&");
        assertEquals(29, stringList.size());
        assertEquals("[#, a, b, c, d, e, f, g, h, i, j, k, l, &, "
                + "m, n, o, p, q, r, s, t, u, v, w, x, y, z, *]",
                stringList.toString());
        integerList.add(3, 1);
        integerList.add(5, 2);
        assertEquals(8, integerList.size());
        assertEquals("[4, 8, 15, 1, 16, 2, 23, 42]", integerList.toString());
        emptyStringList.add(0, "a");
        emptyStringList.add(1, "b");
        emptyStringList.add(2, "c");
        assertEquals("[a, b, c]", emptyStringList.toString());
        try {
            emptyStringList.add(4, "b");
            fail();
        } catch (IndexOutOfBoundsException e) {
        }
        try {
            stringList.add(-1, "aa");
            fail();
        } catch (IndexOutOfBoundsException e) {
        }
        try {
            integerList.add(10, 4);
            fail();
        } catch (IndexOutOfBoundsException e) {
        }
    }

    @Test
    public void testRemove() {
        assertEquals("a", stringList.remove(0));
        assertEquals("z", stringList.remove(24));
        assertEquals("e", stringList.remove(3));
        assertEquals("b", stringList.remove(0));
        assertEquals(22, stringList.size());
        assertEquals("[c, d, f, g, h, i, j, k, l, m, "
                + "n, o, p, q, r, s, t, u, v, w, x, y]", stringList.toString());
        assertEquals(Integer.valueOf(8), integerList.remove(1));
        assertEquals(Integer.valueOf(15), integerList.remove(1));
        assertEquals(4, integerList.size());
        assertEquals("[4, 16, 23, 42]", integerList.toString());
        try {
            emptyStringList.remove(0);
            fail();
        } catch (IndexOutOfBoundsException e) {
        }
        try {
            stringList.remove(-1);
            fail();
        } catch (IndexOutOfBoundsException e) {
        }
        try {
            integerList.remove(10);
            fail();
        } catch (IndexOutOfBoundsException e) {
        }
    }

    @Test
    public void testRemoveFirstOccurrence() {
        stringList.addLast("a");
        assertTrue(stringList.removeFirstOccurrence("z"));
        assertTrue(stringList.removeFirstOccurrence("a"));
        assertTrue(stringList.removeFirstOccurrence("m"));
        assertEquals(24, stringList.size());
        assertEquals("[b, c, d, e, f, g, h, i, j, k, l, n, "
                + "o, p, q, r, s, t, u, v, w, x, y, a]", stringList.toString());
        integerList.addLast(23);
        integerList.addLast(4);
        integerList.addLast(15);
        assertTrue(integerList.removeFirstOccurrence(4));
        assertTrue(integerList.removeFirstOccurrence(23));
        assertTrue(integerList.removeFirstOccurrence(15));
        assertTrue(integerList.removeFirstOccurrence(8));
        assertEquals(5, integerList.size());
        assertEquals("[16, 42, 23, 4, 15]", integerList.toString());
        assertFalse(emptyStringList.removeFirstOccurrence("a"));
        assertFalse(stringList.removeFirstOccurrence("z"));
        assertFalse(stringList.removeFirstOccurrence("aa"));
    }

    @Test
    public void testRemoveLastOccurrence() {
        stringList.addLast("a");
        assertTrue(stringList.removeLastOccurrence("z"));
        assertTrue(stringList.removeLastOccurrence("a"));
        assertTrue(stringList.removeLastOccurrence("m"));
        assertEquals(24, stringList.size());
        assertEquals("[a, b, c, d, e, f, g, h, i, j, k, l, n, "
                + "o, p, q, r, s, t, u, v, w, x, y]", stringList.toString());
        integerList.addLast(23);
        integerList.addLast(4);
        integerList.addLast(15);
        assertTrue(integerList.removeLastOccurrence(4));
        assertTrue(integerList.removeLastOccurrence(23));
        assertTrue(integerList.removeLastOccurrence(15));
        assertTrue(integerList.removeLastOccurrence(8));
        assertEquals(5, integerList.size());
        assertEquals("[4, 15, 16, 23, 42]", integerList.toString());
        assertFalse(emptyStringList.removeLastOccurrence("a"));
        assertFalse(stringList.removeLastOccurrence("z"));
        assertFalse(stringList.removeLastOccurrence("aa"));
    }
}

1. public void addFirst(E value)

   Inserta un nuevo nodo con value al inicio de esta lista.

2. public E removeFirst()

   Elimina el nodo del inicio esta lista. Devuelve el valor del nodo eliminado. Arroja NoSuchElementException en caso de que la lista esté vacía.

3. public E get(int index)

   Devuelve el elemento en la posición index de esta lista (el primer elemento está en la posición 0). Arroja IndexOutOfBoundsException si el índice está fuera de rango (index < 0 || index >= size()).

4. public E set(int index, E value)

   Asigna value a esta lista en la posición index (el primer elemento está en la posición 0). Arroja IndexOutOfBoundsException si el índice está fuera de rango (index < 0 || index >= size()).

5. public boolean contains(E value)

   Devuelve true si value está contenido en esta lista, o false en caso contrario. Utiliza el método equals() para realizar la comparación entre value y los objetos contenidos en la lista.

6. public int count(E value)

   Devuelve el número de veces que aparece value en esta lista. Utiliza el método equals() para realizar la comparación entre value y los objetos contenidos en la lista.

7. public int indexOf(E value)

   Devuelve el índice de la primera ocurrencia de value en esta lista. Devuelve -1 si la lista no contiene a value. Utiliza el método equals() para realizar la comparación entre value y los objetos contenidos en la lista.

8. public int lastIndexOf(E value)

   Devuelve el índice de la última ocurrencia de value en esta lista. Devuelve -1 si la lista no contiene a value. Utiliza el método equals() para realizar la comparación entre value y los objetos contenidos en la lista.

9. public void add(int index, E 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. value se inserta al final de la lista si index == size(). Arroja IndexOutOfBoundsException si el índice está fuera de rango (index < 0 || index > size()).

10. public E remove(int index)

    Elimina de esta lista el nodo en la posición index. Los elementos de la posición index+1 en adelante se recorren una posición hacia abajo. Devuelve el valor del nodo eliminado. Arroja IndexOutOfBoundsException si el índice está fuera de rango (index < 0 || index >= size()).

11. public boolean removeFirstOccurrence(E value)

    Elimina de esta lista el nodo que contiene la primera ocurrencia de value. Devuelve true si se encontró (y eliminó) el valor indicado, o false en caso contrario. Utiliza el método equals() para realizar la comparación entre value y los objetos contenidos en la lista.

12. public boolean removeLastOccurrence(E value)

    Elimina de esta lista el nodo que contiene la última ocurrencia de value. Devuelve true si se encontró (y eliminó) el valor indicado, o false en caso contrario. Utiliza el método equals() para realizar la comparación entre value y los objetos contenidos en la lista.

¿Qué se debe entregar?

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

Fecha límite: Domingo, 14 de abril.

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.