Uma lista vinculada é uma estrutura de dados complexa. A relação entre os dados faz uma lista vinculada dividida em três tipos: lista vinculada única, lista vinculada circular e lista vinculada bidirecional . O seguinte será introduzido um por um. As listas vinculadas são os pontos de conhecimento básicos e importantes na estrutura de dados. Aqui falaremos sobre a implementação de listas vinculadas em Java.
Operações de lista vinculadas ao Java: lista de ligações únicas e lista de ligações duplas
Alguns pontos falam principalmente sobre:
1. Introdução à lista vinculada
2. Princípios e necessidades para a implementação de listas vinculadas
3. Exemplo de fita única
4. Exemplo de ligação dupla
1. Introdução à lista vinculada
As listas vinculadas são uma estrutura de dados relativamente comum. Embora as listas vinculadas sejam mais complicadas de armazenar, elas são mais convenientes ao consultar. Eles são usados em vários idiomas do computador de acordo. Existem muitas categorias de listas vinculadas. Os artigos são analisados para listas de ligações únicas e listas de ligações duplas. Os dados na lista vinculada são como ser conectado por uma cadeia, permitindo fácil acesso aos dados.
2. Princípios e necessidades para a implementação de listas vinculadas
Somente listas de ligação única e listas de ligamento duplo são analisadas aqui. O processo de implementação das listas vinculadas é um pouco complicado, mas trará muitos benefícios. Por exemplo, com a chegada de compras on -line, os comerciantes geralmente embalam as mercadorias em uma caixa e escrevem as informações de endereço na caixa. A empresa expressa pode encontrar o comprador através das informações na caixa e as mercadorias chegam intactas. Sem a proteção da caixa, o produto pode ser danificado ao longo do caminho. A lista vinculada é como a caixa com informações de endereço escritas, que não apenas protegem as informações do produto, mas também grava informações de logística. Há um nó de cabeça na lista vinculada, semelhante à "locomotiva". Enquanto o nó da cabeça correspondente for encontrado, você poderá operar na lista vinculada. Nesta análise, o nó da cabeça atua apenas como um cabeçalho de dados e não salva dados válidos.
O princípio da implementação da lista vinculada única é mostrada na figura:
Princípio de implementação da lista de ligações duplas:
3. Exemplo de fita única
ICOMOPERATE <T> Interface Operação Classe:
pacote linkListTest; importar java.util.map; interface pública ICommoperate <t> {public boolean insertNode (nó t); insertpossnode booleano público (int pos, t nó); public boolean DeLetenode (int pos, mapa <string, objeto> map); public void printLink ();}Nó de lista vinculada única:
pacote linkListTest; // Nó de tabela de uma unidade única classe pública snode {private string data; Snode Private NextNode; public snode () {} public snode (dados da string) {this.data = data; this.NextNode = new Snode (); } public string getData () {return data; } public void setData (dados da string) {this.data = data; } public snode getNextNode () {return nextNode; } public void setNextNode (snode nextNode) {this.NextNode = nextNode; } @Override public string tostring () {return "snode [data =" + data + "]"; }}Classe de operação de link único:
pacote linkListTest; importar java.util.hashmap; importar java.util.map; public class singlelinklist implementa ICommoperate <node> {private snode head = new snode ("head"); // ponteiro de cabeçalho público, inalterado após a declaração private int size = 0; public int getSize () {return this.size; } / * * Insira a lista vinculada, insira -a até o final cada vez que * / @Override public boolean InsertNode (nó Snode) {sinalizador booleano = false; Snode corrente = this.head; if (this.size == 0) {// Lista vinculada vazia this.head.setNextNode (nó); node.setNextNode (NULL); } else {// nó na lista vinculada while (current.getNextNode ()! } current.setNextNode (nó); node.setNextNode (NULL); } this.size ++; bandeira = true; bandeira de retorno; } / * * Insira a posição especificada do POS na lista vinculada, a partir de 1, e POS é maior que o tamanho, insira o final da lista vinculada * * / @Override public boolean insertposnode (int pos, snode nó) {sinalizador booleano = true; Snode corrente = this.head.getNextNode (); if (this.size == 0) {// a lista vinculada vazia this.head.setNextNode (nó); node.setNextNode (NULL); this.size ++; } else if (this.size <pos) {// A posição POS é maior que o comprimento da lista vinculada, insertNode (nó); } else if (pos> 0 && pos <= this.size) {// nó na lista vinculada // 1. Encontre o nó e o nó frontal a ser inserido int find = 0; Snode prenode = this.head; // nó frontal snode currentNode = current; // nó atual while (encontre <pos-1 && currentNode.getNextNode ()! = Null) {prenode = current; // O nó frontal se move para trás CurrentNode = CurrentNode.getNextNode (); // O nó atual se move para trás, encontre ++; } // System.out.println (prenode); // System.out.println (CurrentNode); // 2. Insira o nó prenode.setNextNode (nó); node.setNextNode (CurrentNode); this.size ++; System.out.println ("O nó foi inserido na lista vinculada"); } else {System.out.println ("Erro de informação da posição"); bandeira = false; } retornar sinalizador; } / * * Especifique o nó pos da lista vinculada e exclua o nó correspondente. Método: encontre os nós dianteiros e traseiros para excluir e excluir. A partir de 1 * */ @Override public boolean DeLetenode (int pos) {sinalizador booleano = false; Snode corrente = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {System.out.println ("Posicionar erro de informação ou nenhuma informação na lista vinculada"); } else {// 1. Encontre os nós dianteiros e traseiros para excluir int find = 0; Snode prenode = this.head; // nó frontal snode nextNode = current.getNextNode (); // Nó de volta enquanto (encontre <pos-1 && nextNode.getNextNode ()! = Null) {prenode = current; // O nó frontal é movido para trás nextNode = nextNode.getNextNode (); // O nó traseiro é movido de volta Find ++; } // System.out.println (prenode); // System.out.println (NextNode); // 2. Exclua o nó prenode.setNextNode (NextNode); System.gc (); this.size--; bandeira = true; } retornar sinalizador; } / * * Especifique o POS do nó da lista vinculada e modifique o nó correspondente. Começando de 1 * */ @Override public boolean updateNode (int pos, map <string, objeto> map) {bandeira booleana = false; Nó snode = getNode (pos, mapa); // Obtenha o nó na posição correspondente if (node! = Null) {string data = (string) map.get ("dados"); node.setData (dados); bandeira = true; } retornar sinalizador; } / * * Encontre o nó pos da lista vinculada especificada, começando de 1 * * / @Override public snode getNode (int pos, map <string, object> map) {snode Current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {System.out.println ("As informações de posição estão incorretas ou a lista vinculada não existe"); retornar nulo; } int find = 0; while (encontre <Pos-1 && Current! = null) {current = current.getNextNode (); encontre ++; } retornar atual; } / * * Imprima lista vinculada * * / @Override public void printLink () {int length = this.size; if (comprimento == 0) {System.out.println ("A lista vinculada está vazia!"); retornar ; } Snode atual = this.head.getNextNode (); int find = 0; System.out.println ("Número total de nós:" + comprimento + "outros"); while (atual! = null) {System.out.println ("th" + (++ find) + "nós:" + corrente); current = current.getNextNode (); }} public static void main (string [] args) {singleLinkList sll = new singleLinkList (); Snode node1 = new snode ("node1"); Snode node2 = new snode ("node2"); Snode node3 = new snode ("node3"); Snode node4 = new snode ("node4"); Snode node5 = new snode ("node5"); Snode node6 = new snode ("inserir posição especificada"); sll.insertposnode (sll.getSize ()+1, node1); sll.insertposnode (sll.getSize ()+1, node2); sll.insertposnode (sll.getSize ()+1, node3); sll.insertposnode (sll.getSize ()+1, node4); sll.insertposnode (sll.getSize ()+1, node5); // sll.insertNode (node1); // sll.insertNode (node2); // sll.insertNode (node3); // sll.insertNode (node4); // sll.insertNode (node5); System.out.println ("******************************"); sll.printlink (); System.out.println ("*********************************"); int pos = 2; System.out.println ("Get os dados de posição"+pos+"da lista vinculada:"+sll.getNode (pos, nulo)); System.out.println ("****************************** Insira nós na posição especificada da lista vinculada ************************************"); int pos1 = 2; System.out.println ("Insira dados em"+pos1+"nós:"); sll.insertposnode (POS1, Node6); sll.printlink (); System.out.println ("*************************************************************** int pos2 = 2; System.out.println ("Delete"+POS2+"nós:"); sll.deletenode (POS2); sll.printlink (); System.out.println ("************************************* int pos3 = 2; System.out.println ("modifique os nós"+pos3+":"); Mapa <string, object> map = new hashmap <> (); map.put ("dados", "este é um teste"); sll.updatenode (POS3, mapa); sll.printlink (); }}4. Exemplo de ligação dupla
ICOMOPERATE <T> Interface Operação Classe:
pacote linkListTest; importar java.util.map; interface pública ICommoperate <t> {public boolean insertNode (nó t); insertpossnode booleano público (int pos, t nó); public boolean DeLetenode (int pos, mapa <string, objeto> map); public void printLink ();}Nó da lista de ligações duplas:
pacote linklistTest; // nó de tabela de contíguo duplo dnode {private dnode priorNode; dados de string privada; Dnode privado NextNode; public dnode () {} public dnode (string data) {this.priornode = new dnode (); this.data = dados; this.NextNode = new Dnode (); } public dnode getPriornode () {return PriorNode; } public void SetPriNorNode (DNODE PRIORNODE) {this.priornode = PriorNode; } public string getData () {return data; } public void setData (dados da string) {this.data = data; } public dnode getNextNode () {return nextNode; } public void setNextNode (dnode nextNode) {this.NextNode = nextNode; } @Override public string tostring () {return "dnode [data =" + data + "]"; }}Classe de implementação da lista de ligações duplas:
pacote linkListTest; importar java.util.hashmap; importar java.util.map; classe pública DoubleLinklist implementa o ICOMOPERERO <DNODE> {private dnode head = new dnode ("head"); private int tamanho = 0; public int getSize () {return this.size; } / * * Insira a lista vinculada, insira -a até o final toda vez que * * / @Override public boolean InsertNode (nó dnode) {sinalizador booleano = false; DNode Current = this.head; if (this.size == 0) {// Lista vinculada vazia this.head.setNextNode (nó); node.setPriorNode (this.head); node.setNextNode (NULL); } else {// nó na lista vinculada while (current.getNextNode ()! } current.setNextNode (nó); node.setNextNode (NULL); node.setPriorNode (atual); } this.size ++; bandeira = true; bandeira de retorno; } / * * Insira a posição especificada do POS na lista vinculada, a partir de 1, e POS é maior que o tamanho, insira o final da lista vinculada * * / @Override public boolean insertposnode (int pos, dnode node) {sinalizador booleano = true; DNode Current = this.head.getNextNode (); if (this.size == 0) {// A lista vinculada está vazia this.head.setNextNode (nó); node.setNextNode (NULL); node.setPriorNode (this.head); this.size ++; } else if (pos> this.size) {// A posição POS é maior que o comprimento da lista vinculada, insira o InsertNode final (nó); } else if (pos> 0 && pos <= this.size) {// nó na lista vinculada // 1. Encontre o nó pos a ser inserido, insira o nó pos POS Localização Int Find = 0; while (encontre <Pos-1 && current.getNextNode ()! encontre ++; } // 2. Insira o nó if (current.getNextNode () == null) {// Tail Node Node.setPriNorDODE (Current); node.setNextNode (NULL); current.setNextNode (nó); } else if (current.getNextNode ()! = null) {// intermediário node.setPriornode (current.getPriorNode ()); node.setNextNode (Current); current.getPriorNode (). SetNextNode (nó); current.setPriorNode (nó); } this.size ++; } else {System.out.println ("Erro de informação da posição"); bandeira = false; } retornar sinalizador; } / * * Especifique o nó pos da lista vinculada, exclua o nó correspondente, começando de 1 * * / @Override public boolean deletenode (int pos) {sinalizador booleano = false; DNode Current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {System.out.println ("As informações de posição estão incorretas ou a lista vinculada não existe"); } else {// 1. Encontre o local a ser excluído POS Node int find = 0; while (encontre <Pos-1 && current.getNextNode ()! encontre ++; } // 2. Exclua o nó if (current.getNextNode () == null) {// o nó da cauda Current.getPriornode (). SetNextNode (null); } else if (current.getNextNode ()! = null) {// o nó intermediário current.getPriornode (). SetNextNode (current.getNextNode ()); current.getNextNode (). SetPriornode (current.getPriornode ()); } System.gc (); this.size--; bandeira = true; } retornar sinalizador; } / * * Especifique o POS do nó da lista vinculada e modifique o nó correspondente. Comece em 1 * */ @Override public boolean updateNode (int pos, mapa <string, objeto> map) {bandeira booleana = false; Nó dnode = getNode (pos, mapa); if (node! = null) {string data = (string) map.get ("dados"); node.setData (dados); bandeira = true; } retornar sinalizador; } / * * Encontre o nó pos da lista vinculada especificada, inicie em 1 * * / @Override public dnode getNode (int pos, map <string, object> map) {dnode atual = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {System.out.println ("As informações de posição estão incorretas ou a lista vinculada não existe"); retornar nulo; } int find = 0; while (encontre <Pos-1 && Current! = null) {current = current.getNextNode (); encontre ++; } retornar atual; } / * * Imprima lista vinculada * * / @Override public void printLink () {int length = this.size; if (comprimento == 0) {System.out.println ("A lista vinculada está vazia!"); retornar ; } DNode Current = this.head.getNextNode (); int find = 0; System.out.println ("Número total de nós:" + comprimento + "outros"); while (atual! = null) {System.out.println ("th" + (++ find) + "nós:" + corrente); current = current.getNextNode (); }} public static void main (string [] args) {DoubleLinkList dll = new DoublelinkList (); Dnode node1 = new dnode ("node1"); Dnode node2 = novo dnode ("node2"); Dnode node3 = novo dnode ("node3"); Dnode node4 = novo dnode ("node4"); Dnode node5 = novo dnode ("node5"); Dnode node6 = novo dnode ("Inserir posição especificada"); dll.insertposnode (10, node1); dll.insertposnode (10, node2); dll.insertposnode (10, node3); dll.insertposnode (10, node4); dll.insertposnode (10, node5); // dll.insertNode (node1); // dll.insertNode (node2); // dll.insertNode (node3); // dll.insertnode (node4); // dll.insertNode (node5); System.out.println ("******************************"); dll.printlink (); System.out.println ("************************************"); int pos = 2; System.out.println ("Obtenha os dados de posição"+pos+"da lista vinculada:"+dll.getNode (pos, nulo)); System.out.println ("****************************** Insira nós na posição especificada da lista vinculada ************************************"); int pos1 = 2; System.out.println ("Insira dados nos nós"+pos1+":"); dll.insertposnode (POS1, Node6); dll.printlink (); System.out.println ("******************************* int pos2 = 7; System.out.println ("Delete"+POS2+"nós:"); dll.deletenode (POS2); dll.printlink (); System.out.println ("*************************************** int pos3 = 2; System.out.println ("modifique os nós"+pos3+":"); Mapa <string, object> map = new hashmap <> (); map.put ("dados", "este é um teste"); dll.updatenode (POS3, mapa); dll.printlink (); }}Obrigado pela leitura, espero que isso possa ajudá -lo. Obrigado pelo seu apoio a este site!