Requisito previo: estructura de datos de lista enlazada
Al igual que las arrays, la lista enlazada es una estructura de datos lineal. A diferencia de las arrays, los elementos de la lista vinculada no se almacenan en la ubicación contigua, los elementos se vinculan mediante punteros como se muestra a continuación.
En Java, LinkedList se puede representar como una clase y un Node como una clase separada. La clase LinkedList contiene una referencia del tipo de clase Node.
Java
class LinkedList { Node head; // head of list /* Linked list Node*/ class Node { int data; Node next; // Constructor to create a new node // Next is by default initialized // as null Node(int d) { data = d; } } }
Creación e Inserción
En este artículo, la inserción en la lista se realiza al final, es decir, el nuevo Node se agrega después del último Node de la lista enlazada dada. Por ejemplo, si la lista enlazada dada es 5->10->15->20->25 y se va a insertar 30, entonces la lista enlazada se convierte en 5->10->15->20->25->30 .
Dado que una lista enlazada generalmente se representa mediante el puntero principal de la misma, se requiere recorrer la lista hasta el último Node y luego cambiar el penúltimo Node al nuevo Node.
Java
import java.io.*; // Java program to implement // a Singly Linked List public class LinkedList { Node head; // head of list // Linked list Node. // This inner class is made static // so that main() can access it static class Node { int data; Node next; // Constructor Node(int d) { data = d; next = null; } } // Method to insert a new node public static LinkedList insert(LinkedList list, int data) { // Create a new node with given data Node new_node = new Node(data); // If the Linked List is empty, // then make the new node as head if (list.head == null) { list.head = new_node; } else { // Else traverse till the last node // and insert the new_node there Node last = list.head; while (last.next != null) { last = last.next; } // Insert the new_node at last node last.next = new_node; } // Return the list by head return list; } // Method to print the LinkedList. public static void printList(LinkedList list) { Node currNode = list.head; System.out.print("LinkedList: "); // Traverse through the LinkedList while (currNode != null) { // Print the data at current node System.out.print(currNode.data + " "); // Go to next node currNode = currNode.next; } } // Driver code public static void main(String[] args) { /* Start with the empty list. */ LinkedList list = new LinkedList(); // // ******INSERTION****** // // Insert the values list = insert(list, 1); list = insert(list, 2); list = insert(list, 3); list = insert(list, 4); list = insert(list, 5); list = insert(list, 6); list = insert(list, 7); list = insert(list, 8); // Print the LinkedList printList(list); } }
LinkedList: 1 2 3 4 5 6 7 8
El recorrido
Para el recorrido, a continuación se muestra una función de propósito general printList() que imprime cualquier lista dada atravesando la lista desde el Node principal hasta el último.
Java
import java.io.*; // Java program to implement // a Singly Linked List public class LinkedList { Node head; // head of list // Linked list Node. // Node is a static nested class // so main() can access it static class Node { int data; Node next; // Constructor Node(int d) { data = d; next = null; } } // Method to insert a new node public static LinkedList insert(LinkedList list, int data) { // Create a new node with given data Node new_node = new Node(data); new_node.next = null; // If the Linked List is empty, // then make the new node as head if (list.head == null) { list.head = new_node; } else { // Else traverse till the last node // and insert the new_node there Node last = list.head; while (last.next != null) { last = last.next; } // Insert the new_node at last node last.next = new_node; } // Return the list by head return list; } // Method to print the LinkedList. public static void printList(LinkedList list) { Node currNode = list.head; System.out.print("LinkedList: "); // Traverse through the LinkedList while (currNode != null) { // Print the data at current node System.out.print(currNode.data + " "); // Go to next node currNode = currNode.next; } } // **************MAIN METHOD************** // method to create a Singly linked list with n nodes public static void main(String[] args) { /* Start with the empty list. */ LinkedList list = new LinkedList(); // // ******INSERTION****** // // Insert the values list = insert(list, 1); list = insert(list, 2); list = insert(list, 3); list = insert(list, 4); list = insert(list, 5); list = insert(list, 6); list = insert(list, 7); list = insert(list, 8); // Print the LinkedList printList(list); } }
LinkedList: 1 2 3 4 5 6 7 8
Eliminación por CLAVE
El proceso de eliminación se puede entender de la siguiente manera:
Para acabar:
Dada una ‘clave’, elimine la primera aparición de esta clave en la lista vinculada .
Cómo hacerlo:
Para eliminar un Node de la lista vinculada, realice los siguientes pasos.
- Buscar la clave por su primera aparición en la lista
- Ahora, cualquiera de las 3 condiciones puede estar allí:
- Caso 1: La llave se encuentra en la cabecera
- En este caso, Cambie la cabeza del Node al siguiente Node de la cabeza actual.
- Libera la memoria del Node principal reemplazado.
- En este caso, Cambie la cabeza del Node al siguiente Node de la cabeza actual.
- Caso 2: La clave se encuentra en el medio o último, excepto en la cabeza
- En este caso, busque el Node anterior del Node que desea eliminar.
- Cambia el siguiente Node anterior al siguiente Node del Node actual.
- Libera la memoria del Node reemplazado.
- En este caso, busque el Node anterior del Node que desea eliminar.
- Caso 3: La clave no se encuentra en la lista
- En este caso, no es necesario realizar ninguna operación.
- En este caso, no es necesario realizar ninguna operación.
- Caso 1: La llave se encuentra en la cabecera
Java
import java.io.*; // Java program to implement // a Singly Linked List public class LinkedList { Node head; // head of list // Linked list Node. // Node is a static nested class // so main() can access it static class Node { int data; Node next; // Constructor Node(int d) { data = d; next = null; } } // Method to insert a new node public static LinkedList insert(LinkedList list, int data) { // Create a new node with given data Node new_node = new Node(data); new_node.next = null; // If the Linked List is empty, // then make the new node as head if (list.head == null) { list.head = new_node; } else { // Else traverse till the last node // and insert the new_node there Node last = list.head; while (last.next != null) { last = last.next; } // Insert the new_node at last node last.next = new_node; } // Return the list by head return list; } // Method to print the LinkedList. public static void printList(LinkedList list) { Node currNode = list.head; System.out.print("LinkedList: "); // Traverse through the LinkedList while (currNode != null) { // Print the data at current node System.out.print(currNode.data + " "); // Go to next node currNode = currNode.next; } System.out.println(); } // **************DELETION BY KEY************** // Method to delete a node in the LinkedList by KEY public static LinkedList deleteByKey(LinkedList list, int key) { // Store head node Node currNode = list.head, prev = null; // // CASE 1: // If head node itself holds the key to be deleted if (currNode != null && currNode.data == key) { list.head = currNode.next; // Changed head // Display the message System.out.println(key + " found and deleted"); // Return the updated List return list; } // // CASE 2: // If the key is somewhere other than at head // // Search for the key to be deleted, // keep track of the previous node // as it is needed to change currNode.next while (currNode != null && currNode.data != key) { // If currNode does not hold key // continue to next node prev = currNode; currNode = currNode.next; } // If the key was present, it should be at currNode // Therefore the currNode shall not be null if (currNode != null) { // Since the key is at currNode // Unlink currNode from linked list prev.next = currNode.next; // Display the message System.out.println(key + " found and deleted"); } // // CASE 3: The key is not present // // If key was not present in linked list // currNode should be null if (currNode == null) { // Display the message System.out.println(key + " not found"); } // return the List return list; } // **************MAIN METHOD************** // method to create a Singly linked list with n nodes public static void main(String[] args) { /* Start with the empty list. */ LinkedList list = new LinkedList(); // // ******INSERTION****** // // Insert the values list = insert(list, 1); list = insert(list, 2); list = insert(list, 3); list = insert(list, 4); list = insert(list, 5); list = insert(list, 6); list = insert(list, 7); list = insert(list, 8); // Print the LinkedList printList(list); // // ******DELETION BY KEY****** // // Delete node with value 1 // In this case the key is ***at head*** deleteByKey(list, 1); // Print the LinkedList printList(list); // Delete node with value 4 // In this case the key is present ***in the // middle*** deleteByKey(list, 4); // Print the LinkedList printList(list); // Delete node with value 10 // In this case the key is ***not present*** deleteByKey(list, 10); // Print the LinkedList printList(list); } }
LinkedList: 1 2 3 4 5 6 7 8 1 found and deleted LinkedList: 2 3 4 5 6 7 8 4 found and deleted LinkedList: 2 3 5 6 7 8 10 not found LinkedList: 2 3 5 6 7 8
Eliminación en la posición
Este proceso de borrado se puede entender de la siguiente manera:
Por hacer:
Dada una ‘posición’ , borre el Node en esta posición de la lista enlazada .
Cómo hacerlo:
Los pasos para hacerlo son los siguientes:
- Recorrer la lista contando el índice de los Nodes
- Para cada índice, haga coincidir el índice para que sea igual a la posición
- Ahora, cualquiera de las 3 condiciones puede estar allí:
- Caso 1: La posición es 0, es decir, la cabeza debe borrarse
- En este caso, cambie la cabeza del Node al siguiente Node de la cabeza actual.
- Libere la memoria del Node principal reemplazado.
- En este caso, cambie la cabeza del Node al siguiente Node de la cabeza actual.
- Caso 2: La posición es mayor que 0 pero menor que el tamaño de la lista, es decir, en el medio o al final, excepto en la cabecera
- En este caso, busque el Node anterior del Node que se eliminará.
- Cambia el siguiente del Node anterior al siguiente Node del Node actual.
- Libera la memoria del Node reemplazado.
- En este caso, busque el Node anterior del Node que se eliminará.
- Caso 3: La posición es mayor que el tamaño de la lista, es decir, la posición no se encuentra en la lista
- En este caso, no es necesario realizar ninguna operación.
- En este caso, no es necesario realizar ninguna operación.
- Caso 1: La posición es 0, es decir, la cabeza debe borrarse
Java
import java.io.*; // Java program to implement // a Singly Linked List public class LinkedList { Node head; // head of list // Linked list Node. // Node is a static nested class // so main() can access it static class Node { int data; Node next; // Constructor Node(int d) { data = d; next = null; } } // Method to insert a new node public static LinkedList insert(LinkedList list, int data) { // Create a new node with given data Node new_node = new Node(data); new_node.next = null; // If the Linked List is empty, // then make the new node as head if (list.head == null) { list.head = new_node; } else { // Else traverse till the last node // and insert the new_node there Node last = list.head; while (last.next != null) { last = last.next; } // Insert the new_node at last node last.next = new_node; } // Return the list by head return list; } // Method to print the LinkedList. public static void printList(LinkedList list) { Node currNode = list.head; System.out.print("LinkedList: "); // Traverse through the LinkedList while (currNode != null) { // Print the data at current node System.out.print(currNode.data + " "); // Go to next node currNode = currNode.next; } System.out.println(); } // Method to delete a node in the LinkedList by POSITION public static LinkedList deleteAtPosition(LinkedList list, int index) { // Store head node Node currNode = list.head, prev = null; // // CASE 1: // If index is 0, then head node itself is to be // deleted if (index == 0 && currNode != null) { list.head = currNode.next; // Changed head // Display the message System.out.println( index + " position element deleted"); // Return the updated List return list; } // // CASE 2: // If the index is greater than 0 but less than the // size of LinkedList // // The counter int counter = 0; // Count for the index to be deleted, // keep track of the previous node // as it is needed to change currNode.next while (currNode != null) { if (counter == index) { // Since the currNode is the required // position Unlink currNode from linked list prev.next = currNode.next; // Display the message System.out.println( index + " position element deleted"); break; } else { // If current position is not the index // continue to next node prev = currNode; currNode = currNode.next; counter++; } } // If the position element was found, it should be // at currNode Therefore the currNode shall not be // null // // CASE 3: The index is greater than the size of the // LinkedList // // In this case, the currNode should be null if (currNode == null) { // Display the message System.out.println( index + " position element not found"); } // return the List return list; } // **************MAIN METHOD************** // method to create a Singly linked list with n nodes public static void main(String[] args) { /* Start with the empty list. */ LinkedList list = new LinkedList(); // // ******INSERTION****** // // Insert the values list = insert(list, 1); list = insert(list, 2); list = insert(list, 3); list = insert(list, 4); list = insert(list, 5); list = insert(list, 6); list = insert(list, 7); list = insert(list, 8); // Print the LinkedList printList(list); // // ******DELETION AT POSITION****** // // Delete node at position 0 // In this case the key is ***at head*** deleteAtPosition(list, 0); // Print the LinkedList printList(list); // Delete node at position 2 // In this case the key is present ***in the // middle*** deleteAtPosition(list, 2); // Print the LinkedList printList(list); // Delete node at position 10 // In this case the key is ***not present*** deleteAtPosition(list, 10); // Print the LinkedList printList(list); } }
LinkedList: 1 2 3 4 5 6 7 8 0 position element deleted LinkedList: 2 3 4 5 6 7 8 2 position element deleted LinkedList: 2 3 5 6 7 8 10 position element not found LinkedList: 2 3 5 6 7 8
Todas las operaciones
A continuación se muestra el programa completo que aplica cada operación en conjunto:
Java
import java.io.*; // Java program to implement // a Singly Linked List public class LinkedList { Node head; // head of list // Linked list Node. // Node is a static nested class // so main() can access it static class Node { int data; Node next; // Constructor Node(int d) { data = d; next = null; } } // **************INSERTION************** // Method to insert a new node public static LinkedList insert(LinkedList list, int data) { // Create a new node with given data Node new_node = new Node(data); new_node.next = null; // If the Linked List is empty, // then make the new node as head if (list.head == null) { list.head = new_node; } else { // Else traverse till the last node // and insert the new_node there Node last = list.head; while (last.next != null) { last = last.next; } // Insert the new_node at last node last.next = new_node; } // Return the list by head return list; } // **************TRAVERSAL************** // Method to print the LinkedList. public static void printList(LinkedList list) { Node currNode = list.head; System.out.print("\nLinkedList: "); // Traverse through the LinkedList while (currNode != null) { // Print the data at current node System.out.print(currNode.data + " "); // Go to next node currNode = currNode.next; } System.out.println("\n"); } // **************DELETION BY KEY************** // Method to delete a node in the LinkedList by KEY public static LinkedList deleteByKey(LinkedList list, int key) { // Store head node Node currNode = list.head, prev = null; // // CASE 1: // If head node itself holds the key to be deleted if (currNode != null && currNode.data == key) { list.head = currNode.next; // Changed head // Display the message System.out.println(key + " found and deleted"); // Return the updated List return list; } // // CASE 2: // If the key is somewhere other than at head // // Search for the key to be deleted, // keep track of the previous node // as it is needed to change currNode.next while (currNode != null && currNode.data != key) { // If currNode does not hold key // continue to next node prev = currNode; currNode = currNode.next; } // If the key was present, it should be at currNode // Therefore the currNode shall not be null if (currNode != null) { // Since the key is at currNode // Unlink currNode from linked list prev.next = currNode.next; // Display the message System.out.println(key + " found and deleted"); } // // CASE 3: The key is not present // // If key was not present in linked list // currNode should be null if (currNode == null) { // Display the message System.out.println(key + " not found"); } // return the List return list; } // **************DELETION AT A POSITION************** // Method to delete a node in the LinkedList by POSITION public static LinkedList deleteAtPosition(LinkedList list, int index) { // Store head node Node currNode = list.head, prev = null; // // CASE 1: // If index is 0, then head node itself is to be // deleted if (index == 0 && currNode != null) { list.head = currNode.next; // Changed head // Display the message System.out.println( index + " position element deleted"); // Return the updated List return list; } // // CASE 2: // If the index is greater than 0 but less than the // size of LinkedList // // The counter int counter = 0; // Count for the index to be deleted, // keep track of the previous node // as it is needed to change currNode.next while (currNode != null) { if (counter == index) { // Since the currNode is the required // position Unlink currNode from linked list prev.next = currNode.next; // Display the message System.out.println( index + " position element deleted"); break; } else { // If current position is not the index // continue to next node prev = currNode; currNode = currNode.next; counter++; } } // If the position element was found, it should be // at currNode Therefore the currNode shall not be // null // // CASE 3: The index is greater than the size of the // LinkedList // // In this case, the currNode should be null if (currNode == null) { // Display the message System.out.println( index + " position element not found"); } // return the List return list; } // **************MAIN METHOD************** // method to create a Singly linked list with n nodes public static void main(String[] args) { /* Start with the empty list. */ LinkedList list = new LinkedList(); // // ******INSERTION****** // // Insert the values list = insert(list, 1); list = insert(list, 2); list = insert(list, 3); list = insert(list, 4); list = insert(list, 5); list = insert(list, 6); list = insert(list, 7); list = insert(list, 8); // Print the LinkedList printList(list); // // ******DELETION BY KEY****** // // Delete node with value 1 // In this case the key is ***at head*** deleteByKey(list, 1); // Print the LinkedList printList(list); // Delete node with value 4 // In this case the key is present ***in the // middle*** deleteByKey(list, 4); // Print the LinkedList printList(list); // Delete node with value 10 // In this case the key is ***not present*** deleteByKey(list, 10); // Print the LinkedList printList(list); // // ******DELETION AT POSITION****** // // Delete node at position 0 // In this case the key is ***at head*** deleteAtPosition(list, 0); // Print the LinkedList printList(list); // Delete node at position 2 // In this case the key is present ***in the // middle*** deleteAtPosition(list, 2); // Print the LinkedList printList(list); // Delete node at position 10 // In this case the key is ***not present*** deleteAtPosition(list, 10); // Print the LinkedList printList(list); } }
LinkedList: 1 2 3 4 5 6 7 8 1 found and deleted LinkedList: 2 3 4 5 6 7 8 4 found and deleted LinkedList: 2 3 5 6 7 8 10 not found LinkedList: 2 3 5 6 7 8 0 position element deleted LinkedList: 3 5 6 7 8 2 position element deleted LinkedList: 3 5 7 8 10 position element not found LinkedList: 3 5 7 8
Publicación traducida automáticamente
Artículo escrito por RishabhPrabhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA