Explicación detallada de las funciones básicas de Java implementando listas vinculadas unidireccionales

1. Prefacio

Recientemente, al revisar las estructuras de datos y los algoritmos, algunos problemas de algoritmos utilizan la idea de las pilas y cuando se trata de pilas, tenemos que hablar sobre listas vinculadas. Las matrices y las listas vinculadas son la base de estructuras de almacenamiento lineal, y las pilas y las colas son aplicaciones de estructuras de almacenamiento lineal ~

Este artículo explica principalmente los puntos de conocimiento básico de las listas unidas y hace una introducción simple. Si hay algún error, corrígelo.

2. Revisión y conocimiento

Hablando de listas vinculadas, mencionemos primero la matriz. Compararlos con matrices le hace comprender muy bien la estructura de almacenamiento de las listas vinculadas.

2.1 Revise la matriz

Hemos aprendido matrices en C y Java:

• Las matrices son una estructura lineal de almacenamiento continuo, con el mismo tipo de elemento y el mismo tamaño

Ventajas de las matrices:

• Velocidad de acceso rápido

Desventajas de las matrices:

• Debes saber la longitud de la matriz por adelantado
• Es lento insertar y eliminar elementos
• El espacio suele ser limitado
• Necesita un gran bloque continuo de memoria
• Insertar y eliminar elementos es ineficiente

2.2 Descripción de la lista de enlaces

Después de leer la matriz, regrese a nuestra lista vinculada:

• Las listas vinculadas son estructuras lineales de almacenamiento discreto

Los N nodos N se asignan discretamente y se conectan entre sí a través de punteros. Cada nodo tiene solo un nodo predecesor, cada nodo tiene solo un nodo posterior, el primer nodo no tiene nodo predecesor y el nodo de cola no tiene nodo posterior.

Ventajas de la lista vinculada:

• Sin restricciones de espacio
• Insertar y eliminar elementos es rápido

Desventajas de las listas vinculadas:

• La velocidad de acceso es muy lenta

Explicaré los términos relacionados con la lista vinculada a través de la imagen anterior:

Para determinar una lista vinculada, solo necesitamos un puntero de cabeza, y toda la lista vinculada se puede deducir a través del puntero de la cabeza ~

Hay varias categorías de listas vinculadas:

1. Tabla de enlaces unidireccionales

• Un nodo apunta al siguiente nodo

2. Tabla de enlace bidireccional

• Un nodo tiene dos campos de puntero

3. Lista de enlaces de reciclaje

• Todos los demás nodos se pueden encontrar a través de cualquier nodo, y el último nodo de las dos listas vinculadas (bidireccionales/unidireccionales) apuntan al primer nodo para realizar un bucle

Lo que debe recordar al operar una lista vinculada es:

¡El campo de puntero en el nodo apunta a un nodo!

3. Lista de enlaces de implementación de Java

algoritmo:

• Traversal
• Encontrar
• Claro
• destruir
• Encuentra la longitud
• Clasificar
• Eliminar nodos
• Insertar nodo

Primero, definimos una clase como un nodo

• Dominio de datos
• Campo del puntero

Para la conveniencia de la operación, lo definí directamente como público.

 Public Class Node {// Data Domain Public int Data; // dominio del puntero, señalando el siguiente nodo público del nodo siguiente; public nodo () {} public nodo (int data) {this.data = data; } nodo público (int data, nodo siguiente) {this.data = data; this.next = siguiente; }}

3.1 Crear una lista vinculada (agregar nodos)

Inserte datos en la lista vinculada:

• Encuentra el nodo de cola para la inserción
• Incluso si el nodo de cabeza.next es nulo y no pasa por el bucle while, conectará el nodo de la cabeza al nuevo nodo (he inicializado el nodo de la cabeza, por lo que no es necesario determinar si el nodo de la cabeza es nulo) ~

 /*** Agregar datos a la lista vinculada** @param Los datos de valor a agregar*/public static void addData (int value) {// Inicializar el nodo que se agregará newnode = new Node (valor); // nodo temporal de nodo temp = head; // Encuentra el nodo de cola while (temp.next! = Null) {temp = temp.next; } // El caso donde el nodo de cabeza.next es nulo ha sido incluido ~ temp.next = newnode; }

3.2 atravesando la lista vinculada

Hemos escrito el método de adición anterior, y ahora lo revisaremos para ver si es correcto ~~~

Comience desde el primer nodo y siga buscando hasta que no haya datos en el nodo posterior:

 / *** atravesando la lista vinculada** @param nodo del cabezal head head*/ public static void traverse (cabezal de nodo) {// nodo temporal, inicio desde el primer nodo nodo temp = head.next; while (temp! = null) {system.out.println ("Siga la cuenta oficial java3y:" + temp.data); // Continuar con el siguiente temp = temp.next; }}

resultado:

3.3 Insertar nodo

• Inserte un nodo en la lista vinculada, primero debe determinar si esta posición es legal antes de insertarla ~
• Solo encuentre el nodo anterior donde desea insertar ~

 /*** Insertar nodo** @param Puntinero de cabeza de cabeza* @param El índice de índice se insertará* @param Value Value para ser insertado*/public static void InsertNode (node head, int index, int value) {// Primero de todo, debe determinar si la posición especificada es legal, si (índice <1 || índice> linkListLength (head) + 1) {System.out. devolver; } // nodo temporal, comience desde el nodo de nodo inicial temp = head; // Haga clic en la posición actual de la traversal int currentPos = 0; // Inicializar el nodo que se insertará nodo insertNode = nuevo nodo (valor); while (temp.next! = null) {// La ubicación del nodo anterior se encontró si ((index - 1) == CurrentPos) {// TEMP representa el nodo anterior // apunta el puntero original desde el nodo anterior al nodo insertado a InsertNode.Next = Temp.Next; // Apunte el campo Pointer del nodo anterior al nodo que se insertará temp.next = insertNode; devolver; } currentPos ++; temp = temp.next; }}

3.4 Obtenga la longitud de la lista vinculada

Es muy simple obtener la longitud de la lista vinculada. Se puede hacer atravesando y obteniendo +1 para cada nodo ~

 / *** Obtenga la longitud de la lista vinculada* @Param Head Pointer*/ public static int LinkListLength (nodo head) {int longitud = 0; // nodo temporal, comience desde el primer nodo de nodo temp = head.next; // Encuentra el nodo de cola mientras (temp! = Null) {longitud ++; temp = temp.next; } Longitud de retorno; }

3.5 Eliminar nodos

Eliminar un nodo en una ubicación determinada es en realidad muy similar al nodo de inserción, y también necesita encontrar el nodo anterior. Cambie el campo Pointer del nodo anterior y puede eliminarlo ~

 /** * Eliminar nodos de acuerdo con la ubicación * * @Param Head Head Puntiner * @Param Index La ubicación que se eliminará */public static void deletenode (nodo head, int index) {// Primero de todos, debe determinar si la ubicación especificada es legal, si (index <1 || linklistlength (head) + 1) {System.out.println ("la deletera es ilegal. devolver; } // nodo temporal, comience desde el nodo de nodo inicial temp = head; // La ubicación actual del registro transversal es int currentPos = 0; while (temp.next! = null) {// La ubicación del nodo anterior se encuentra si ((index - 1) == CurrentPos) {// TEMP representa el nodo anterior // temp.next representa el nodo que desea eliminar // almacenamiento del nodo que desea eliminar el nodo deletenode = temp.next; // El siguiente nodo que desea eliminar el nodo se entrega al nodo anterior para controlar temp.next = deletenode.next; // Java lo reciclará, y no debería tener mucho sentido establecerlo en NULL (personalmente creo que, si no es correcto, apuntarlo ~) deletenode = nulo; devolver; } currentPos ++; temp = temp.next; }}

3.6 Ordene la lista vinculada

Ya he hablado de 8 algoritmos de clasificación [Resumen de ocho algoritmos de clasificación]. Elegiré una simple clasificación de burbujas esta vez (en realidad, quiero escribir un tipo rápido, pero se siente un poco difícil probarla ...)

 / ** * Ordene la lista vinculada * * @param head * */ public static void sortLinkList (nodo head) {node currentNode; Nodo nextNode; for (currentNode = head.next; currentNode.next! = null; currentNode = currentNode.next) {for (nextNode = head.next; nextNode.next! = null; nextNode = nextNode.next) {if (nextNode.data> nextNode.next.Data) {int temp = nextNode.data; nextNode.data = nextNode.next.data; nextNode.next.data = temp; }}}}

3.7 Encuentra el nodo K-LaT en la lista vinculada

Este algoritmo es bastante interesante: establece dos punteros P1 y P2 para hacer nodos P2 K más rápido que P1, y atraviesa hacia atrás al mismo tiempo. Cuando P2 está vacío, P1 es el último nodo K

 / *** Encuentre el k-th hasta el último nodo en la lista vinculada (establece dos punteros p1 y p2, haz p2 k más rápido que p1 y atraviesa hacia atrás al mismo tiempo. Cuando p2 está vacío, p1 es el k-th hasta el último nodo** @param cot. @Param k k-th hasta el último nodo*/ público nodo estático. LinkListLengs (head)) return null; regresar P1;

3.8 Eliminar datos duplicados en la lista vinculada

Es similar al tipo de burbuja, siempre que sea igual, se puede eliminar ~

 / ** * Eliminar datos duplicados en la lista vinculada (similar a burbujeante, es equivalente a la deleción) * * @param nodo head head nodo */ public static void deletedupplecate (nodo de nodo) {// nodo temporal, (comenzando desde el primer nodo-> nodo con datos reales) nodo temp = head.next; // siguiente nodo del nodo actual (primer nodo) nodo nextNode = temp.next; while (temp.next! = null) {while (nextnode.next! = null) {if (nextNode.next.data == nextNode.data) {// Eliminar el siguiente nodo (el nodo actual apunta al siguiente nodo) nextNode.next = nextNode.next.next; } else {// Continuar con el siguiente NextNode = nextNode.next; }} // Siguiente ronda de comparación temp = temp.next; }}

3.9 consulta los nodos intermedios de la lista vinculada

Este algoritmo también es bastante interesante: un puntero que toma 1 paso cada vez, un puntero que da 2 pasos cada vez, y luego da un paso, ese es el nodo intermedio

 / *** Consulta el nodo intermedio de una única lista vinculada*/ public static nodo SearchMid (cabezal de nodo) {nodo p1 = head; Nodo p2 = cabeza; // Da un paso y un paso dos pasos hasta que esté nulo. El nodo central que alcanza (p2! = Null && p2.next! = Null && p2.next.next! = Null) {p1 = p1.next; p2 = p2.next.next; } return p1; }

3.10 Salida recursivamente Tablas de una sola cola en cabeza

 / *** Salida Lista única vinculada de cola a cabeza por recursivamente** @param nodo head head*/ public static void printListerSely (nodo head) {if (head! = Null) {printlisterSely (head.next); System.out.println (head.data); }}

3.11 Lista de enlaces inversos

 / *** Implementar la inversión de la lista vinculada** @param nodo El nodo principal de la lista vinculada*/ public static nodo reverseLinkList (nodo nodo) {nodo anterior; if (node == null || node.next == null) {prev = node; } else {nodo tmp = ReverselinkList (node.next); node.next.next = node; node.next = null; anterior = tmp; } return prev; }

Referencia a la lista de enlaces inverso desde: //www.vevb.com/article/136185.htm

4. Finalmente

No es difícil entender la lista vinculada en sí, pero puede causar dolores de cabeza al hacer operaciones relacionadas. head.next siguiente Siguiente siguiente ... (todavía estoy débil en el algoritmo ... No tengo suficiente cerebro ...) Escribí esta pequeña cosa después de dos días ...

Puede hacer cualquier cosa simplemente conociendo su puntero de la cabeza cuando opera una lista vinculada.

1. Agregue datos a la lista vinculada

• Transversal y busque el nodo de cola, inserte (justo mientras (temp.next! = Nulo), y salga del bucle y busque el nodo de cola)

2. Traverse la lista vinculada

• A partir del primer nodo (nodo válido), siempre que no sea nulo, salida

3. Inserte nodos en la lista vinculada en una ubicación determinada

• Primero, determine si la posición es válida (dentro del rango de la longitud de la lista vinculada)
• Encuentre el nodo anterior donde desea insertar, y el puntero original del nodo anterior se transfiere desde el nodo insertado para apuntar al punto de nodo anterior al nodo que desea insertar.

4. Obtenga la longitud de la lista vinculada

• Cada vez que se accede a un nodo, se puede utilizar la operación variable ++.

5. Eliminar el nodo en la ubicación dada

• Primero, determine si la posición es válida (dentro del rango de la longitud de la lista vinculada)
• Encuentre el nodo anterior donde desea insertarlo y apuntarlo desde el nodo anterior al siguiente nodo.

6. Ordene la lista vinculada

• Ordeneslos usando un algoritmo de burbujas

7. Encuentre el nodo K-LaT en la lista vinculada

• Establezca dos punteros P1 y P2 para hacer nodos P2 K más rápido que P1, y atraviese hacia atrás al mismo tiempo. Cuando P2 está vacío, P1 es el último nodo K

8. Eliminar datos duplicados en la lista vinculada

• La operación es similar al tipo de burbuja, siempre que sea igual, se puede eliminar ~

9. Consulte los nodos intermedios de la lista vinculada

• Este algoritmo también es bastante interesante: un puntero que toma 1 paso cada vez, un puntero que da 2 pasos cada vez, y luego da un paso, ese es el nodo intermedio

10. Salida recursivamente de una mesa unida de cola a cabeza

• Mientras todavía haya datos a continuación, mira hacia abajo y la recursión es voltear desde el final.

11. Lista de enlaces inversos

• Hay dos formas de recursión y no recursión, lo que creo que es bastante difícil. Puedes verlo en el enlace que di ~

PD: La implementación de todos será diferente, por lo que algunos pequeños detalles inevitablemente cambiarán, y no hay una manera fija de escribirla, por lo que puede darse cuenta de las funciones correspondientes ~

Resumir

Lo anterior es todo el contenido de este artículo. Espero que el contenido de este artículo tenga cierto valor de referencia para el estudio o el trabajo de todos. Si tiene alguna pregunta, puede dejar un mensaje para comunicarse. Gracias por su apoyo a Wulin.com.

Referencias:

• http://www.cnblogs.com/whgk/p/6589920.html
• https://www.cnblogs.com/bywallance/p/6726251.html