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);
}
}
Producción
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);
}
}
Producción
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);
}
}
Producción
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);
}
}
Producción
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);
}
}
Producción
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