Una lista vinculada es una estructura de datos compleja. La relación entre los datos hace que una lista vinculada se divida en tres tipos: lista única vinculada, lista de enlace circular y lista vinculada bidireccional . Lo siguiente será introducido uno por uno. Las listas vinculadas son los puntos de conocimiento básicos e importantes en la estructura de datos. Aquí hablaremos sobre la implementación de listas vinculadas en Java.
Operaciones de la lista vinculada Java: lista unida y lista de doble enlace
Algunos puntos hablan principalmente de:
1. Introducción a la lista vinculada
2. Principios y necesidades para la implementación de listas vinculadas
3. Ejemplo monocatenario
4. Ejemplo de doble enlace
1. Introducción a la lista vinculada
Las listas vinculadas son una estructura de datos relativamente común. Aunque las listas vinculadas son más complicadas de almacenar, son más convenientes al consultar. En consecuencia, se utilizan en múltiples lenguajes de computadora. Hay muchas categorías de listas vinculadas. Los artículos se analizan para listas vinculadas únicas y listas de doble enlace. Los datos en la lista vinculada son como ser conectados juntos por una cadena, lo que permite un fácil acceso a los datos.
2. Principios y necesidades para la implementación de listas vinculadas
Aquí solo se analizan listas ligadas únicas y listas de doble enlace aquí. El proceso de implementación de las listas vinculadas es un poco complicado, pero traerá muchos beneficios. Por ejemplo, con la llegada de las compras en línea, los comerciantes generalmente empacan los productos en una caja y escriben la información de la dirección en el cuadro. La compañía expresa puede encontrar al comprador a través de la información en el cuadro, y los bienes llegan intactos. Sin la protección de la caja, el producto puede dañarse en el camino. La lista vinculada es como el cuadro con información de dirección escrita, que no solo protege la información del producto, sino que también escribe información logística. Hay un nodo principal en la lista vinculada, similar a la "locomotora". Mientras se encuentre el nodo principal correspondiente, puede operar en la lista vinculada. En este análisis, el nodo principal solo actúa como un encabezado de datos y no guarda datos válidos.
El principio de implementación de la lista vinculada única se muestra en la figura:
Principio de implementación de la lista de doble enlace:
3. Ejemplo monocatenario
ICMMOPERATE <T> Clase de operación de la interfaz:
paquete LinkListTest; import java.util.map; interfaz pública icMomMoperate <t> {public boolean insertNode (t nodo); Public Boolean InsertPosnode (int POS, nodo t); public boolean deletenode (int pos, map <string, object> map); public void printLink ();}Nodo de lista vinculada única:
Paquete LinkListTest; // Nodo de tabla con un solo Nodo Public Class Snode {Datos de cadena privada; privado Snode NextNode; public snode () {} public snode (string data) {this.data = data; this.nextnode = new Snode (); } public string getData () {return data; } public void setData (string data) {this.data = data; } public snode getNextNode () {return nextNode; } public void setNextNode (snode nextNode) {this.nextNode = nextNode; } @Override public string toString () {return "snode [data =" + data + "]"; }}Clase de operación de enlace único:
Paquete LinkListTest; import java.util.hashmap; import java.util.map; public class SingLelinkList implementa IComMoperate <node> {private snode head = new Snode ("Head"); // puntero de encabezado público, sin cambios después de la declaración privada int tamiz = 0; public int getsize () {return this.size; } / * * Inserte la lista vinculada, inserte al final cada vez * / @Override public boolean InsertNode (node snode) {boolean flag = false; Snode Current = this.head; if (this.size == 0) {// vacío Link List this.head.setNextNode (nodo); node.setNextNode (nulo); } else {// nodo en la lista vinculada while (current.getNextNode ()! = null) {current = current.getNextNode (); } current.setNextNode (nodo); node.setNextNode (nulo); } this.size ++; bandera = verdadero; Bandera de regreso; } / * * Inserte la posición especificada de POS en la lista vinculada, a partir de 1, y POS es mayor que el tamaño, luego inserte el extremo de la lista vinculada * * / @Override public boolean InsertPosNode (int POS, Node Snode) {Boolean Flag = True; Snode Current = this.head.getNextNode (); if (this.size == 0) {// La lista vinculada vacía this.head.setNextNode (nodo); node.setNextNode (nulo); this.size ++; } else if (this.size <pos) {// La posición POS es mayor que la longitud de la lista vinculada, InsertNode (nodo); } else if (pos> 0 && pos <= this.size) {// nodo en la lista vinculada // 1. Busque el nodo y el nodo frontal que se insertará int Find = 0; Snode prenode = this.head; // Nodo delantero SnodeinDentNode = Current; // Current Node while (busque <pos-1 && currentNode.getNextNode ()! = NULL) {prenode = current; // El nodo delantero se mueve hacia atrás CurrentNode = currentNode.getNextNode (); // El nodo actual se mueve hacia atrás Find ++; } // system.out.println (prenode); // system.out.println (currentNode); // 2. Inserte el nodo prenode.setNextNode (nodo); node.setNextNode (CurrentNode); this.size ++; System.out.println ("El nodo se ha insertado en la lista vinculada"); } else {System.out.println ("Error de información de posición"); bandera = falso; } Bandera de retorno; } / * * Especifique el nodo POS de la lista vinculada y elimine el nodo correspondiente. Método: Encuentre los nodos delanteros y traseros para eliminar y eliminar. A partir de 1 * */ @Override public boolean deletenode (int pos) {boolean flag = false; Snode Current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {system.out.println ("Error de información de posición o ninguna información en la lista vinculada"); } else {// 1. Encuentre los nodos delanteros y posteriores para eliminar int fin fins = 0; Snode prenode = this.head; // Nodo frontal snode nextNode = current.getNextNode (); // Back Node while (busque <pos-1 && nextNode.getNextNode ()! = NULL) {prenode = Current; // El nodo delantero se mueve hacia atrás nextNode = nextNode.getNextNode (); // El nodo posterior se mueve hacia atrás Find ++; } // system.out.println (prenode); // system.out.println (nextNode); // 2. Elimine el nodo prenode.setNextNode (nextNode); System.gc (); esto.size--; bandera = verdadero; } Bandera de retorno; } / * * Especifique el nodo POS de la lista vinculada y modifique el nodo correspondiente. A partir de 1 * */ @Override public boolean updateTenode (int pos, map <string, object> map) {boolean flag = false; Snode node = getNode (pos, map); // Obtenga el nodo en la posición correspondiente if (nodo! = Null) {string data = (string) map.get ("data"); node.setData (datos); bandera = verdadero; } Bandera de retorno; } / * * Encuentre el nodo POS de la lista vinculada especificada, comenzando desde 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 ("La información de posición es incorrecta o la lista vinculada no existe"); regresar nulo; } int find = 0; while (encontrar <pos-1 && current! = null) {current = current.getNextNode (); encontrar ++; } retorno actual; } / * * Imprima la lista vinculada * * / @Override public void printLink () {int longitud = this.size; if (longitud == 0) {System.out.println ("¡La lista vinculada está vacía!"); devolver ; } Snode Current = this.head.getNextNode (); int encontrar = 0; System.out.println ("Número total de nodos:" + Longitud + "Ones"); while (current! = null) {system.out.println ("th" + (++ find) + "nodos:" + corriente); 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 ("Insertar la posición especificada"); sll.insertPosNode (sll.getSize ()+1, nodo1); sll.insertposnode (sll.getSize ()+1, nodo2); Sll.insertPosNode (Sll.getSize ()+1, nodo3); sll.insertPosNode (sll.getSize ()+1, nodo4); sll.insertposnode (sll.getSize ()+1, nodo5); // sll.insertnode (nodo1); // sll.insertnode (nodo2); // sll.insertnode (nodo3); // sll.insertnode (nodo4); // sll.insertnode (nodo5); System.out.println ("****************************"); sll.printlink (); System.out.println ("*********************************"); int pos = 2; System.out.println ("Obtenga los datos de posición"+POS+"de la lista vinculada:"+Sll.getNode (pos, null)); System.out.println ("************************************** A los nodos a la posición especificada de la lista vinculada **********************************"); int pos1 = 2; System.out.println("Insert data into "+pos1+"" nodes: "); sll.insertPosNode(pos1, node6); sll.printLink(); System.out.println("************************************Delete the specified location node of the linked list*************************************"); int pos2 = 2; Pos3 = 2;4. Ejemplo de doble enlace
ICMMOPERATE <T> Clase de operación de la interfaz:
paquete LinkListTest; import java.util.map; interfaz pública icMomMoperate <t> {public boolean insertNode (t nodo); Public Boolean InsertPosnode (int POS, nodo t); public boolean deletenode (int pos, map <string, object> map); public void printLink ();}Nodo de lista de dos enlaces:
Paquete LinkListTest; // Nodo de tabla de doble contiguo Clase pública DNode {private dnode priornode; datos de cadena privada; DNode privado NextNode; public dnode () {} public dnode (string data) {this.priornode = new dnode (); this.data = data; this.nextnode = new Dnode (); } public dnode getPriornode () {return priornode; } public void setPriornode (dnode priornode) {this.priornode = priornode; } public string getData () {return data; } public void setData (string data) {this.data = data; } public dnode getNextNode () {return nextNode; } public void setNextNode (dnode nextNode) {this.nextNode = nextNode; } @Override public String toString () {return "dnode [data =" + data + "]"; }}Clase de implementación de la lista de doble enlace:
paquete LinkListTest; import java.util.hashmap; import java.util.map; public class DoubleLinkList implementa ICMMOPERATE <DNODE> {private dnode head = new dnode ("head"); Tamaño privado int = 0; public int getsize () {return this.size; } / * * Inserte la lista vinculada, inserte al final cada vez * * / @Override public boolean InsertNode (nodo dnode) {boolean flag = false; Dnode corriente = this.head; if (this.size == 0) {// vacío Link List this.head.setNextNode (nodo); node.setPriornode (this.head); node.setNextNode (nulo); } else {// nodo en la lista vinculada while (current.getNextNode ()! = null) {current = current.getNextNode (); } current.setNextNode (nodo); node.setNextNode (nulo); node.setPriornode (actual); } this.size ++; bandera = verdadero; Bandera de regreso; } / * * Inserte la posición especificada de POS en la lista vinculada, a partir de 1, y POS es mayor que el tamaño, inserte el extremo de la lista vinculada * * / @Override public boolean InsertPosNode (int POS, nodo dnode) {boolean flag = true; Dnode current = this.head.getNextNode (); if (this.size == 0) {// La lista vinculada está vacía this.head.setNextNode (nodo); node.setNextNode (nulo); node.setPriornode (this.head); this.size ++; } else if (pos> this.size) {// La posición POS es mayor que la longitud de la lista vinculada, inserte el end InsertNode (nodo); } else if (pos> 0 && pos <= this.size) {// nodo en la lista vinculada // 1. Encuentre el nodo POS a insertar, inserte la ubicación de corriente de nodo POS int Find = 0; while (busque <pos-1 && current.getNextNode ()! = null) {current = current.getNextNode (); encontrar ++; } // 2. Inserte el nodo if (current.getNextNode () == null) {// nodo de cola.setPriornode (actual); node.setNextNode (nulo); current.setNextNode (nodo); } else if (current.getNextNode ()! = NULL) {// NODO INTERMEDIATE NODO.SETPRIERNODE (Current.getPriornode ()); node.setNextNode (actual); current.getPriornode (). setNextNode (nodo); current.setPriornode (nodo); } this.size ++; } else {System.out.println ("Error de información de posición"); bandera = falso; } Bandera de retorno; } / * * Especifique el nodo POS de la lista vinculada, elimine el nodo correspondiente, comenzando desde 1 * * / @Override public boolean deletenode (int pos) {boolean flag = false; Dnode current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {system.out.println ("La información de posición es incorrecta o la lista vinculada no existe"); } else {// 1. Encuentre la ubicación que se eliminará POS node int find = 0; while (busque <pos-1 && current.getNextNode ()! = null) {current = current.getNextNode (); encontrar ++; } // 2. Eliminar el nodo if (current.getNextNode () == null) {// el nodo de cola actual.getPriornode (). SetNextNode (null); } else if (current.getNextNode ()! = NULL) {// El nodo intermedio Current.getPriOrnode (). SetNextNode (current.getNextNode ()); current.getNextNode (). SetPriornode (current.getPriornode ()); } System.gc (); esto.size--; bandera = verdadero; } Bandera de retorno; } / * * Especifique el nodo POS de la lista vinculada y modifique el nodo correspondiente. Comience en 1 * */ @Override public boolean UpdateTenode (int pos, map <string, object> map) {boolean flag = false; Dnode node = getNode (pos, map); if (node! = null) {string data = (string) map.get ("data"); node.setData (datos); bandera = verdadero; } Bandera de retorno; } / * * Encuentre el nodo POS de la lista vinculada especificada, comience en 1 * * / @Override public dnode getNode (int pos, map <string, object> map) {dnode current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {system.out.println ("La información de posición es incorrecta o la lista vinculada no existe"); regresar nulo; } int find = 0; while (encontrar <pos-1 && current! = null) {current = current.getNextNode (); encontrar ++; } retorno actual; } / * * Imprima la lista vinculada * * / @Override public void printLink () {int longitud = this.size; if (longitud == 0) {System.out.println ("¡La lista vinculada está vacía!"); devolver ; } Dnode current = this.head.getNextNode (); int encontrar = 0; System.out.println ("Número total de nodos:" + Longitud + "Ones"); while (current! = null) {system.out.println ("th" + (++ find) + "nodos:" + corriente); current = current.getNextNode (); }} public static void main (string [] args) {doubleLinkList dll = new DoubleLinkList (); Dnode node1 = new DNode ("node1"); Dnode node2 = new DNode ("node2"); Dnode node3 = new DNode ("node3"); Dnode node4 = new DNode ("node4"); Dnode node5 = new DNode ("node5"); Dnode node6 = new DNode ("Insertar la posición especificada"); dll.insertposnode (10, nodo1); dll.insertposnode (10, nodo2); dll.insertposnode (10, nodo3); dll.insertposnode (10, nodo4); 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 ("Obtenga los datos de posición"+POS+"de la lista vinculada:"+dll.getNode (pos, null)); System.out.println ("************************************** A los nodos a la posición especificada de la lista vinculada **********************************"); int pos1 = 2; System.out.println ("Inserte datos en los nodos"+Pos1+":"); dll.insertposnode (POS1, nodo6); dll.printlink (); System.out.println ("******************************************* Elimine los nodos especificados en la lista vinculada ***************************************"); int pos2 = 7; System.out.println ("Eliminar"+pos2+"nodos:"); dll.deletenode (pos2); dll.printlink (); System.out.println ("*************************************************** Modifique los nodos especificados en la lista vinculada *************************************"); int pos3 = 2; System.out.println ("Modifique los nodos"+Pos3+":"); Map <string, object> map = new HashMap <> (); map.put ("datos", "Esta es una prueba"); dll.updatenode (pos3, mapa); dll.printlink (); }}Gracias por leer, espero que pueda ayudarte. ¡Gracias por su apoyo para este sitio!