Lista de links ordenados:
Classificar por valores -chave. Ao excluir o cabeçalho da corrente, o valor mínimo (/máximo) é excluído. Ao inserir, procure a posição de inserção.
Ao inserir, você precisa comparar o (n), médio (n/2) e, ao excluir os dados mínimos (/máximos) na cabeça da corrente, a eficiência é O (1),
Se um aplicativo exigir acesso frequente (insira/encontre/excluir) nos itens de dados menores (/máximos), as listas vinculadas ordenadas serão uma boa escolha. Filas prioritárias podem usar listas vinculadas ordenadas para implementar a classificação de inserção de listas vinculadas ordenadas:
Para uma matriz não ordenada, classifique -a com uma lista vinculada ordenada e o nível de comparação é o (n^2)
O nível de tempo de cópia é O (2*n). Como o número de cópias é pequeno, os dados na lista vinculada são movidos N vezes pela primeira vez e depois copiaram da lista vinculada para a matriz. N vezes, cada vez que um novo link é inserido, não há necessidade de copiar os dados em movimento, apenas um ou dois links precisam alterar o domínio do link.
importar java.util.arrays; importar java.util.random; / *** Inserir matrizes de classificação em uma lista vinculada ordenada* @author stone*/ public class LinkedListInsert <t estende comparável <t>> {private link <t> primeiro; // primeiro nó public linkedListInsertSort () {} public boolean isEmpty () {return primeiro == null; } public void SortList (t [] ary) {if (ary == null) {return; } // Insira elementos de matriz na lista vinculada e classifique -os em uma lista vinculada ordenada para (t dados t: ary) {insert (dados); } //} public void insert (t data) {// insira no cabeçalho da corrente, classifique de pequeno a grande link <t> newlink = new link <t> (dados); Link <t> atual = primeiro, anterior = null; while (atual! = null && data.compareto (current.data)> 0) {anterior = current; current = current.next; } if (anterior == null) {primeiro = newlink; } else {anterior.Next = newlink; } newlink.Next = Current; } link público <t> deletefirst () {// excluir o link do cabeçalho da corrente <T> temp = primeiro; primeiro = primeiro.next; // altere o primeiro nó para retornar temp; } link público <T> encontre (t) {link <T> encontre = primeiro; while (encontre! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} retornar encontre; } link público <t> delete (t t) {if (isEmpty ()) {return null; } else {if (primeiro.data.equals (t)) {link <t> temp = primeiro; primeiro = primeiro.next; // altere o primeiro nó para o próximo nó retorno temp; }} Link <T> p = primeiro; Link <t> q = primeiro; while (! } else {q = p; p = p.next; }} q.next = p.next; retornar p; } public void DisplayList () {// Travel System.out.println ("List (First-> last):"); Link <t> atual = primeiro; while (atual! = null) {current.displaylink (); current = current.next; }} public void DisplayListerSe () {// Link de travessia inverso <T> p = primeiro, q = primeiro.next, t; while (q! = null) {// ponteiro é revertido, a ordem de dados atravessada é atrasada t = q.next; // no3 if (p == primeiro) {// Quando é o cabeçalho original, o .next do cabeçalho deve estar vazio p.next = null; } q.next = p; // no3 -> no1 ponteiro reverso p = q; // Start é reverso q = t; // NO3 START} // No if no loop acima, primeiro.next está vazio e quando q é nulo e não executa o loop, p é o item mais original de dados. Após a inversão, P é atribuído a primeiro = P; displaylist (); } classe link <T> {// Dados do ponto de link T; // Link do campo de dados <T> Em seguida; // ponteiro subsequente, link de domínio da cadeia de nó (dados t) {this.data = data; } void DisplayLink () {System.out.println ("Os dados são" + data.toString ()); }} public static void main (string [] args) {LinkedListInsertSort <Teger> list = new LinkedListInsertSort <Teger> (); Aleatório aleatório = novo aleatório (); int len = 5; Inteiro [] ary = novo número inteiro [len]; for (int i = 0; i <len; i ++) {ary [i] = aleatória.nextint (1000); } System.out.println ("--------------"); System.out.println (Arrays.toString (ARY)); System.out.println ("-----------------------------------------------------------); list.sortlist (ary); list.displayList ();}}
Imprimir
--- Antes de classificar ---- [595, 725, 310, 702, 444] --- Após a classificação da lista vinculada ---
Inversão da lista vinculada única:
classe pública SingleLinkedListerSe {public static void main (string [] args) {nó head = new node (0); Nó temp = nulo; Nó cur = null; for (int i = 1; i <= 10; i ++) {temp = novo nó (i); if (i == 1) {head.setNext (temp); } else {cur.setNext (temp); } cur = temp; } // 10.next = null; Nó h = cabeça; while (h! = null) {System.out.print (h.getData () + "/t"); h = h.getNext (); } System.out.println (); // inverter 1 // h = node.ververse1 (cabeça); // while (h! = null) {// System.out.print (h.getData () + "/t"); // h = h.getNext (); //} // inverter 2 h = node.versever1 (cabeça); while (h! = null) {System.out.print (h.getData () + "/t"); h = h.getNext (); }}}/** Cada nó de uma única lista vinculada contém atributos apontando para o próximo nó*/classe nó {dados do objeto; // Nó do objeto de dados a seguir; // Próximo nó do nó (objeto d) {this.data = d; } Node (objeto d, nó n) {this.data = d; this.Next = n; } public Object getData () {return data; } public void setData (dados do objeto) {this.data = data; } public node getNext () {return a seguir; } public void SetNext (nó próximo) {this.Next = Next; } // Método 1 A cabeça é redefinida estática no nó reverse1 (cabeça do nó) {nó p = null; // a nova cabeça após o nó de inversão q = head; // Resultado da rotação: 012.123.234, ...... 10 nulo nulo while (head.next! = Null) {p = head.next; // o primeiro é substituído pelo segundo e, em seguida, P representa a próxima cabeça.Next = P.Next; // O segundo é substituído pelo terceiro, e o próximo que já chegou à primeira posição se tornará o primeiro, e o primeiro se tornará o primeiro; // o novo é substituído pelo primeiro} retornar p; } // Método 2 Cabeça não redefina o nó estático reverse2 (cabeça do nó) {// apontar o ponteiro do nó intermediário para o nó anterior, você ainda pode continuar a atravessar a lista vinculada para trás do nó p1 = cabeça, p2 = head.next, p3; // resultado dianteiro, médio e traseiro/rotação: 012, 123, 234, 345, 456 .... 9 10 NULL While (P2! = NULL) {p3 = p2.next; p2.next = p1; // aponta para trás e aponta para frente p1 = p2; // 2, 3 avança para a frente p2 = p3; } head.Next = null; // Head não mudou. Quando a saída atingir 0, solicite 0.Next a 1 retornar P1; }}