Implementações da interface List

"Se você acha que já terminamos com a interface List, então você está enganado. Estamos apenas começando. Deixe-me falar sobre as coleções LinkedList e ArrayList ."

"Vou começar com a coleção ArrayList."

"Aqui está a aparência do diagrama de herança desta coleção:"

"As interfaces são verdes."

"Aulas abstratas são roxas."

"Aulas comuns são vermelhas."

"Linhas sólidas representam herança e linhas tracejadas representam implementações de interface."

"Esta é a coleção mais simples. Dentro de uma ArrayList , os elementos são armazenados em uma matriz simples."

"A principal vantagem desta coleção sobre uma matriz é sua capacidade de expansão, ou seja, sua capacidade de aumentar seu comprimento conforme necessário."

"Se o array ficar sem espaço, então um segundo array maior é criado e todos os elementos do primeiro array são copiados para ele. Então o segundo array toma o lugar do primeiro, e o primeiro é descartado (será destruído pelo coletor de lixo)."

"Quanto maior o array fica?"

"O comprimento da nova matriz é calculado como (3*n)/2+1, onde n é o comprimento da matriz antiga. Em outras palavras, se a matriz antiga tiver 100 elementos, a nova terá 300/2+1 = 151."

"Ao adicionar um elemento no meio de um ArrayList, todos os elementos à direita de onde o novo elemento será inserido são copiados 1 posição à direita e, em seguida, o novo elemento é adicionado à célula vazia."

"Ao remover um elemento do meio, todos os elementos à direita desse elemento são copiados 1 posição à esquerda."

"Você está dizendo que o ArrayList se torna mais longo quando você adiciona elementos a ele e que se torna mais curto quando você remove elementos?"

"Não, o array dentro de um ArrayList nunca se torna mais curto sozinho; no entanto, você pode forçar um ArrayList a encolher seu array interno para o menor tamanho possível chamando o método trimToSize (). "

"E, claro, falarei sobre o LinkedList."

"Aqui está a aparência do diagrama de herança:"

"As interfaces são verdes."

"Aulas abstratas são roxas."

"Aulas comuns são vermelhas."

"Linhas sólidas representam herança e linhas tracejadas representam implementações de interface."

"Como você já sabe, LinkedList armazena elementos como uma lista encadeada."

"Eu ouço isso o tempo todo, mas você poderia me dizer o que é?"

"Claro. "É simples."

"Uma lista encadeada consiste em elementos que a) armazenam dados e b) armazenam referências aos elementos seguintes e anteriores."

"É assim que a classe para tal elemento ficaria se armazenasse Strings:"

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

"E se usarmos uma declaração de tipo genérico, seria mais ou menos assim:"

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

"Faz sentido."

"Para entender melhor, vamos escrever um código onde adicionamos 10 elementos a uma lista duplamente vinculada:"

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
  }
 }
}

"Imagine que temos 10 elementos na lista. Veja como inserir um elemento no meio:"

"Os links que foram alterados são destacados em vermelho brilhante . Eles agora apontam para o novo elemento."

"Novos links são destacados em roxo brilhante . Eles são os links do novo elemento para seus vizinhos."

"E agora 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;

"Obrigado, Ellie. Eu definitivamente aprendi muitas coisas novas sobre listas."