Implementaciones de la interfaz List

"Si cree que ya hemos terminado con la interfaz List, entonces está equivocado. Apenas estamos comenzando. Déjame contarte sobre las colecciones LinkedList y ArrayList ".

"Comenzaré con la colección ArrayList".

"Así es como se ve el diagrama de herencia de esta colección:"

"Las interfaces son verdes".

"Las clases abstractas son moradas".

"Las clases ordinarias son rojas".

"Las líneas continuas representan herencia y las líneas discontinuas representan implementaciones de interfaz".

"Esta es la colección más simple. Dentro de una ArrayList , los elementos se almacenan en una matriz simple".

"La principal ventaja de esta colección sobre una matriz es su capacidad de expansión, es decir, su capacidad para aumentar su longitud según sea necesario".

"Si la matriz se queda sin espacio, entonces se crea una segunda matriz más grande y todos los elementos de la primera matriz se copian en ella. Luego, la segunda matriz toma el lugar de la primera y la primera se descarta (será destruido por el recolector de basura)".

"¿Cuánto más grande se vuelve la matriz?"

"La longitud de la nueva matriz se calcula como (3*n)/2+1, donde n es la longitud de la matriz anterior. En otras palabras, si la matriz anterior tenía 100 elementos, entonces la nueva será 300/2+1 = 151".

"Al agregar un elemento en el medio de una ArrayList, todos los elementos a la derecha de donde se insertará el nuevo elemento se copian 1 posición a la derecha y luego el nuevo elemento se agrega a la celda vacía".

"Al eliminar un elemento del medio, todos los elementos a la derecha de ese elemento se copian 1 posición a la izquierda".

"¿Está diciendo que ArrayList se alarga cuando le agrega elementos y que se acorta cuando elimina elementos?"

"No, la matriz dentro de una ArrayList nunca se acorta por sí misma; sin embargo, puede obligar a una ArrayList a reducir su matriz interna al tamaño más pequeño posible llamando al método trimToSize ()".

"Y, por supuesto, les contaré sobre LinkedList".

"Así es como se ve su diagrama de herencia:"

"Las interfaces son verdes".

"Las clases abstractas son moradas".

"Las clases ordinarias son rojas".

"Las líneas continuas representan herencia y las líneas discontinuas representan implementaciones de interfaz".

"Como ya sabe, LinkedList almacena elementos como una lista enlazada".

"Escucho eso todo el tiempo, pero ¿podría decirme qué es?"

"Claro. "Es simple".

"Una lista enlazada consta de elementos que a) almacenan datos yb) almacenan referencias a los elementos siguientes y anteriores".

"Así es como se vería la clase de dicho elemento si almacenara cadenas:"

class LinkedListElement
{
String data;
LinkedListElement next;
LinkedListElement previous;
}

"Y si usamos una declaración de tipo genérico, se vería así:"

class LinkedListElement<T>
{
 T data;
 LinkedListElement<T> next;
 LinkedListElement<T> previous;
}

"Tiene sentido."

"Para entenderlo mejor, escribamos un código donde agreguemos 10 elementos a una lista doblemente enlazada:"

public static void main(String[] args)
{
 LinkedListElement<Integer> tail; // The tail (very last element) of the list

 for(int i = 0; i < 10; i++)
 {
  LinkedListElement<Integer> element = new LinkedListElement<Integer>();
  element.data = i;

  if (tail == null) // If the tail doesn't exist, then make our element the last element
  {
   tail = element;
  }
  else // if there is a tail, add the element
  {
   tail.next = element; // Set the next field on the tail element
   element.previous = tail; // Add a reference to the tail to the new element
   tail = element; // Make the new element the tail
  }
 }
}

"Imagínese que tenemos 10 elementos en la lista. Así es como se inserta un elemento en el medio:"

"Los enlaces que han cambiado están resaltados en rojo brillante . Ahora apuntan al nuevo elemento".

"Los nuevos enlaces se resaltan en púrpura brillante . Son los enlaces del nuevo elemento a sus vecinos".

"Y ahora como código:"

// This field stores the element that is the head of the list
LinkedListElement<Integer> head = …

// Get the 4th element (counting from zero)
LinkedListElement<Integer> element4 = head.next.next.next.next;
// Get the 5th element
LinkedListElement<Integer> element5 = element4.next;

// Create the new element that we will insert
LinkedListElement<Integer> newElement = new LinkedListElement<Integer>();
newElement.data = -18;

// Replace the references in the element on the left
newElement.previous = element4;
element4.next = newElement;

// Replace the references in the element on the right
newElement.next = element5;
element5.previous = newElement;

"Gracias, Ellie. Definitivamente aprendí muchas cosas nuevas sobre las listas".