No artigo anterior, analisamos a implementação subjacente do Arraylist e sabíamos que a implementação subjacente da Arraylist é baseada em matrizes, por isso tem as características de pesquisa e modificação rápidas, enquanto a inserção e a exclusão lentas. O LinkedList introduzido neste artigo é outra implementação da interface da lista. Sua camada subjacente é baseada em uma lista vinculada bidirecional. Portanto, possui as características de inserção e exclusão rápidas, durante a pesquisa e modificação lentas. Além disso, as funções de filas e pilhas podem ser realizadas através da operação da lista vinculada bidirecional. A estrutura subjacente do LinkedList é mostrada na figura abaixo.
F representa a referência do nó da cabeça, L representa a referência do nó da cauda e cada nó na lista vinculado possui três elementos, a saber, a referência do nó direto (P), o valor do elemento do nó (e) e a referência subsequente do nó (n). O nó é representado pelo nó da classe interna, vejamos sua estrutura interna.
// Nó classe interna classe estática privada nó <E> {e item; // Nó do elemento <E> Em seguida; // Nó Próximo Nó <E> ANTES; // Nó anterior Nó (nó <E> prev, e elemento, nó <e> a seguir) {this.item = element; this.Next = Next; this.prev = prev; }}O nó da classe interna é realmente muito simples, com apenas três variáveis de membros e um construtor. O item representa o valor do nó, a seguir é a referência ao próximo nó, e o ANTRE é a referência ao nó anterior. Esses três valores são passados através do construtor. Em seguida, vamos dar uma olhada nas variáveis e construtores de membros do LinkedList.
// O número de elementos definidos é traduzido int size = 0; // O nó do cabeçalho faz referência ao nó transitório <E> primeiro; // O nó da cauda faz referência ao nó transitório <E> Último; // O construtor sem parâmetros Public LinkedList () {} // O construtor passou para a coleção externa LinkList (coleção <? addall (c);}O LinkedList mantém uma referência ao nó do cabeçalho e uma referência ao nó da cauda. Possui dois construtores, um é um construtor sem parâmetros e o outro é um construtor passado para a coleção externa. Ao contrário do ArrayList, o LinkedList não especifica o construtor de tamanho inicial. Confira seus métodos para adicionar, excluir, modificar e pesquisar.
// add (add (add) public boolean add (e e) {// add linklast (e); return true;} // add (insert) public void add (int index, e elemento) {checkPositionIndex (index); if (index == size) {// add linkLast (elemento); } else {// insira linkBefore (elemento, nó (index)); }} // excluir (dar Índice) public e remover (int index) {// verifique se o subscrito é o checkElementIntex legal (índice); Retorne desvincular (nó (índice));} // excluir (elemento dado) public boolean Remover (objeto o) {if (o == null) {for (node <e> x = primeiro; x! retornar true; }}} else {// Lista de link de tranquilidade para (nó <e> x = primeiro; x! = null; x = x.next) {if (o.equals (x.item)) {// excluir uncenar (x); retornar true; }}} return false;} // altere o conjunto público e (int index, e elemento) {// verifique se o subscrito é o checkElementElementsindex legal (index); // Obtenha a referência do nó do nó subscrito especificado <E> x = nó (índice); // obtém o valor do nó subscrito especificado e OldVal = x.item; // Defina o elemento do nó como o novo valor x.item = elemento; // Retorna o valor anterior retorna antigo;} // Verifique public e get (int index) {// verifique se o subscrito é o checkElementIndex legal (índice); // retorna o valor do nó do nó de retorno do subscrito especificado (index) .item;}O método de adicionar elementos no LinkedList é principalmente chamar os dois métodos Linklast e LinkBe antes. O método LinkLast é vincular um elemento por trás da lista vinculada, e o método LinkBefore é inserir um elemento no meio da lista vinculada. O método de exclusão do LinkedList remove um elemento da lista vinculada chamando o método desvinculado. Vamos dar uma olhada no código central das operações de inserção e exclusão da lista vinculada.
// Antes de vincular ao nó especificado LinkBe antes (e, nó <e> succ) {// Obtenha a referência anterior do nó do nó final dado o nó <E> pred = succ.prev; // Crie um novo nó, a referência anterior do nó do novo nó aponta para o nó anterior do nó dado // a referência do próximo nó do novo nó aponta para o nó final dado <e> newNode = new Node <> (pred, e, succ); // apontar a referência anterior do nó do nó dado ao novo nó succ.prev = newNode; // Se o nó anterior do nó especificado estiver vazio, significa que o nó fornecido é o nó do cabeçalho se (pred == null) {// apontar a referência do nó do cabeçalho para o novo nó primeiro = newNode; } else {// Caso contrário, aponte a próxima referência do nó para o novo nó pred.Next = newNode; } // Adicione o número de elementos de conjunto um tamanho ++; // Adicione o número de modificações um modcount ++; } // Descarregue o nó especificado e desvincular (nó <E> x) {// obtenha o elemento do nó dado ELEMT E FINAL E ELEMT = X.Item; // Obtenha a referência ao próximo nó do nó dado nó final <E> next = x.next; // Obtenha a referência ao nó anterior do nó dado nó final <E> prev = x.prev; // Se o nó anterior do nó especificado estiver vazio, explicação: o nó especificado é um nó de cabeçalho se (prev == null) {// apontar a referência do nó do cabeçalho para o próximo nó do nó dado primeiro = a seguir; } else {// Reference o nó sucessor do nó anterior apontando para o nó subsequente do nó dado prev.Next = next; // Reference o nó anterior do nó dado x.prev = null; } // Se o próximo nó do nó especificado estiver vazio, significa que o nó fornecido é um nó de cauda se (a seguir == null) {// apontar a referência do nó da cauda para o nó anterior do nó dado last = prev; } else {// Reference o nó avançado do próximo nó apontando para o nó anterior do nó dado a seguir.prev = prev; x.next = null; } // esvaziar o elemento do nó dado x.item = null; // subtraia o número de elementos definidos por tamanho--; // Adicione modCount ++; elemento de retorno;} O LinkBe antes e o desvincular são operações representativas de vincular nós e desinstalar nós. Outros métodos para vincular e desinstalar nós em ambas as extremidades são semelhantes; portanto, focamos nos métodos LinkBe e Unbink.
Diagrama de processos do método LinkBefore:
Diagrama de processos do método desvinculado:
Através da ilustração acima, a complexidade do tempo das operações de inserção e exclusão da lista vinculada é O (1), e as operações de pesquisa e modificação da lista vinculada requerem percorrer a lista vinculada para localizar elementos. Ambas as operações são chamadas de método Node (Int Index) para localizar elementos para ver como ele localiza elementos por meio de subscritos.
// Obtenha o nó do nó <E> nó (int index) {// Se o índice estiver na primeira metade da lista vinculada, verifique desde o início if (índice <(size >> 1)) {node <e> x = primeiro; for (int i = 0; i <index; i ++) {x = x.next; } retornar x; } else {// Se o índice estiver na segunda metade da lista vinculada, verifique no nó final <E> x = last; for (int i = size-1; i> índice; i--) {x = x.prev; } retornar x; }} Ao posicionar o subscrito, primeiro determine se está na metade superior ou na metade inferior da lista vinculada. Se estiver na metade superior, comece do início e, se for a metade inferior, comece a partir do final. Portanto, a complexidade do tempo da operação de pesquisa e modificação do subscrito é O (N/2). Através da operação da lista vinculada bidirecional, as funções de filas de itens únicos, filas e pilhas de mão dupla também podem ser realizadas.
Operação de fila unidirecional:
// Obtenha o nó do cabeçalho public e peek () {Final Node <e> f = primeiro; retornar (f == null)? null: f.item;} // Obtenha o nó de cabeçalho public e elemento () {return getfirst ();} // coloque o nó de cabeçalho public e poll () {Final Node <e> f = primeiro; retornar (f == null)? null: UNLINKFIRST (f);} // Remova o nó do cabeçalho public e remover () {return removefirst ();} // Adicione nó no final da fila public boolean Oferta (e e) {return add (e);}Operação de fila de duas vias:
// Adicione public boolean Offerfirst (e e) {addfirst (e); return true;} // Adicione public boolean OfferLast (e e) {addlast (e); retornar true;} // Obtenha o nó do cabeçalho public e peekfirst () {Final Node <e> f = primeiro; retornar (f == null)? NULL: F.Item; } // Obtenha o nó da cauda public e peeklast () {Final Node <e> l = last; retornar (l == nulo)? nulo: L.Item;}Operação de pilha:
// colocando a pilha public void push (e e) {addfirst (e);} // colocando a pilha pública e pop () {return removefirst ();} Seja uma fila de mão única, uma fila de mão dupla ou uma pilha, eles realmente operam nos nós da cabeça e da cauda da lista vinculada. Suas implementações são baseadas nos quatro métodos: addfirst (), addlast (), removefirst () e removelast (). Suas operações são semelhantes a LinkBefore () e Unbink (), exceto que uma deve operar nas duas extremidades da lista vinculada, e a outra é operar no meio da lista vinculada. Pode -se dizer que esses quatro métodos são casos especiais dos métodos LinkBefore () e Unbink (), portanto, não é difícil entender suas implementações internas, para que não as apresenteei aqui. Neste ponto, nossa análise da LinkedList está prestes a terminar, e resumiremos os pontos -chave em todo o texto:
1. O LinkedList é implementado com base em uma lista vinculada de mão dupla. Seja o método de adição, exclusão, modificação e pesquisa ou a implementação de filas e pilhas, ela pode ser implementada por meio de nós de operação.
2. O LinkedList não precisa especificar a capacidade com antecedência, porque com base nas operações da lista vinculada, a capacidade da coleção aumentará automaticamente com a adição de elementos.
3. A memória ocupada pela coleção depois que o LinkedList é excluída é automaticamente reduzida e não há necessidade de chamar o método TRIMTOSIZE () como ArrayList
4. Todos os métodos do LinkedList não são sincronizados, portanto, não são seguros de threads e devem ser evitados em ambientes multithread.
5. A análise acima é baseada no JDK1.7, e outras versões terão algumas diferenças, portanto não podem ser generalizadas.
O exposto acima é todo o conteúdo deste artigo. Espero que seja útil para o aprendizado de todos e espero que todos apoiem mais o wulin.com.